Abstract
Multi-Valued Decision Diagrams (MDDs) offer a powerful way to represent table constraints in Constraint Programming (CP) by compressing allowed value combinations into directed acyclic graphs. However, traditional MDD operations often scale poorly with large domain sizes. This paper introduces high-performance algorithms, including the pReduce reduction method and a generic APPLY framework, designed to handle domains with over 10,000 values. Experimental results show that these optimized MDD operations can outperform specialized, dedicated propagators for constraints like regular and knapsack, providing a flexible and efficient alternative for complex modeling tasks.
Introduction
In Constraint Programming, "Table constraints" are a fundamental tool for defining valid assignments by explicitly listing allowed tuples. While expressive, these tables can grow exponentially in size. MDDs provide a compact alternative, but their standard manipulation algorithms often have a time complexity tied to the domain size ($d$). In domains where $d$ is large—such as natural language processing with vocabularies of 10,000+ words—standard MDD operations become computationally prohibitive. This research aims to bridge this efficiency gap, making MDDs a viable, general-purpose tool for modeling complex constraints without the overhead of developing specialized propagators for every new problem.
Methods
The authors propose several key algorithmic improvements to enhance MDD scalability:
pReduce(Improved Reduction): Traditional reduction algorithms merge equivalent nodes but often scale with $O(d)$. The authors introducepReduce, which utilizes a "pack" system to process nodes layer-by-layer. By grouping nodes based on shared neighbor prefixes and iteratively splitting these packs, the algorithm identifies equivalent nodes with a complexity of $O(n + m + d)$, where $m$ is the number of actual neighbors. This makes it significantly faster for sparse graphs in large domains.- Generic
APPLYFunction: A unified framework is provided for binary operations on MDDs, such as Union, Intersection, and Difference. This allows users to build complex constraints by combining simpler MDD components. - Complement Operations: To efficiently handle "negative" constraints (forbidding specific patterns), the authors introduce a "wild-card node" technique for computing MDD complements.
- Integration with MDD4R: The system leverages the MDD4R algorithm to maintain arc consistency efficiently on these reduced graphs during the search process.
Key Results and Insights
The algorithms were evaluated against several benchmarks, including phrase generation and the MiniZinc Challenge.
- Significant Speedups: On crossword and random table problems,
pReducewas 5x to 10x faster than previous state-of-the-art tools likemddify. - Massive Scalability: The approach successfully handled MDD intersections involving millions of nodes and hundreds of millions of arcs with a domain size of 10,000. Memory usage remained under 10GB, whereas previous methods exceeded 64GB.
- Outperforming Dedicated Propagators: For the
regularconstraint, the MDD-based approach was 2x to 5x faster than standard dedicated implementations. - Universal Modeling: The results suggest that MDDs can serve as a "universal language" for constraints. Because the MDD is kept in a minimal, reduced state, the resulting propagation can be more efficient than dedicated algorithms that do not perform such aggressive minimization.
Conclusion
This research demonstrates that with optimized algorithms, MDDs can handle the massive domains required by real-world applications while remaining competitive with specialized constraint propagators. While the initial creation of an MDD still incurs some overhead, the subsequent gains in solving speed and modeling flexibility are substantial. Future work will explore further optimizations in MDD construction and the use of dynamic variable ordering to further enhance performance.
Summary updated