Efficient Operations On MDDs for Building Constraint Programming Models

Guillaume Perez, Jean-Charles RéginIJCAI 2015

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:

  1. pReduce (Improved Reduction): Traditional reduction algorithms merge equivalent nodes but often scale with $O(d)$. The authors introduce pReduce, 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.
  2. Generic APPLY Function: 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.
  3. Complement Operations: To efficiently handle "negative" constraints (forbidding specific patterns), the authors introduce a "wild-card node" technique for computing MDD complements.
  4. Integration with MDD4R: The system leverages the MDD4R algorithm to maintain arc consistency efficiently on these reduced graphs during the search process.
Comparison of an MDD before and after the reduction process using the proposed pReduce algorithm. The 'before' state includes a wild-card node (w2) used in intermediate operations.

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, pReduce was 5x to 10x faster than previous state-of-the-art tools like mddify.
  • 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 regular constraint, 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

BibTeX
@inproceedings{perez2015efficient,
  author = {Guillaume Perez and Jean-Charles Régin},
  title = {{Efficient Operations On MDDs for Building Constraint Programming Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure