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

• DOI: 10.24963/ijcai.2018/192
• Publication Date: 2018-07-05T01:49:10Z
• Authors: Hélène Verhaeghe; Christophe Lecoutre; Pierre Schaus
• Keywords: Bitwise operation; Table (database)

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 diagrams is non-deterministic.We show that it easy and efficient to transform any table (set tuples) into an sMDD.We also introduce new filtering algorithm, Compact-MDD, which based on bitwise operations, can be applied both MDDs sMDDs.Our experimental results practical interest our approach, terms compression speed.