Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-sets

Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-sets

Hélène Verhaeghe, Christophe Lecoutre, Pierre Schaus

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1383-1389. https://doi.org/10.24963/ijcai.2018/192

Multi-Valued Decision Diagrams (MDDs) are instrumental in modeling combinatorial problems with Constraint Programming.In this paper, we propose a related data structure called sMDD (semi-MDD) where the central layer of the diagrams is non-deterministic.We show that it is easy and efficient to transform any table (set of tuples) into an sMDD.We also introduce a new filtering algorithm, called Compact-MDD, which is based on bitwise operations, and can be applied to both MDDs and sMDDs.Our experimental results show the practical interest of our approach, both in terms of compression and filtering speed.
Keywords:
Constraints and SAT: Constraint Satisfaction
Constraints and SAT: Global Constraints
Constraints and SAT: Modeling;Formulation