TL;DR
This paper introduces sMDD, a novel data structure for representing combinatorial constraints that offers better compression than traditional Multi-Valued Decision Diagrams (MDDs). They also present Compact-MDD (CMDD), an efficient filtering algorithm that leverages bitwise operations and works with both MDDs and sMDDs, achieving performance close to state-of-the-art table-based methods.
What Problem Does This Paper Address?
Constraint Programming (CP) is a powerful technique for solving combinatorial problems. A key aspect of CP is constraint propagation, which prunes the search space by removing inconsistent variable assignments. For table constraints (which explicitly list allowed tuples), MDDs offer a more compact representation than raw tables, especially when there's significant redundancy. However, generating optimal MDDs is NP-hard, and existing MDD-based filtering algorithms can be slower than specialized table-based methods. This paper aims to bridge this gap by proposing a more compressible diagram structure (sMDD) and a general, efficient filtering algorithm (CMDD) that can leverage this structure.
Methods
The paper introduces two main innovations:
- sMDD (semi-MDD): This is a variation of MDDs that relaxes the "out-determinism" property (where each node must have unique outgoing arc labels) for nodes in the middle layers of the diagram. This relaxation allows for potentially greater compression. The construction of an sMDD from a table involves splitting the table into prefix and suffix parts, building corresponding trees, and then connecting them with an intermediate variable. This process, called
sReduce, is described as having a similar complexity to existing MDD reduction algorithms. - Compact-MDD (CMDD): This is a new filtering algorithm designed to enforce Generalized Arc Consistency (GAC) on constraints represented by MDDs or sMDDs. CMDD uses reversible sparse bit-sets to efficiently track valid arcs and performs filtering in two passes: a downward pass and an upward pass. It borrows principles from existing algorithms like Compact-Table (CT) and MDD4R, particularly in its use of bitwise operations for efficient computation and its handling of variable domain changes.
Datasets
The paper evaluates their approach on 4,111 XCSP3 instances that contain only table constraints. No new benchmarks were introduced.
Key Insights and Ideas
- Compression vs. Structure: The core idea is that by relaxing strict out-determinism in the middle layers of a decision diagram (creating an sMDD), one can achieve better compression (fewer nodes) compared to standard MDDs, even if the number of arcs might slightly increase.
- Bitwise Operations for Efficiency: The
Compact-MDDalgorithm's effectiveness stems from its heavy reliance on bitwise operations. This allows for very fast manipulation and intersection of sets of valid arcs, making the filtering process efficient. - Bridging the Gap: CMDD aims to make decision diagram-based filtering competitive with specialized table-based methods by combining the compression benefits of sMDDs with a highly optimized filtering algorithm.
- General Applicability: CMDD is designed to work on any MVD (including MDDs and sMDDs), making it a versatile filtering technique.
Key Results
- sMDD Compression: Experimental results show that sMDDs significantly reduce the number of nodes compared to MDDs generated by standard methods (e.g., more than an 8x reduction for 70% of tables).
- CMDD Performance: The
Compact-MDDalgorithm, especially when used with sMDDs (CMDDs), performs comparably to or better than existing MDD-based filtering algorithms (MDD4R). - Competitiveness with Table Methods: While table-based methods (like CT) are generally faster, CMDDs significantly reduces the performance gap, solving 40% of instances within a factor of 2 of CT's time.
- High Compression Advantage: For instances where decision diagrams offer high compression, CMDD on sMDDs can be the fastest approach, outperforming even table-based methods.
Limitations and Future Work
- MDD Generation Complexity: While sMDDs offer better compression, the process of generating the optimal ordering for MDDs (and by extension, sMDDs) remains NP-hard.
- Generalizing sMDDs: The authors plan to investigate if sMDDs can be used to represent constraints beyond simple tables, such as those involving unary expressions.
- Extending CMDD: Future work may involve adapting the CMDD algorithm to handle these more complex constraint types.
Summary updated