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

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

IJCAI 2018 pp. 1383-1389

doi:10.24963/IJCAI.2018/192 /ijcai/2018/verhaeghe2018ijcai-compact/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Verhaeghe et al. "Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-Sets." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/192

Markdown

[Verhaeghe et al. "Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-Sets." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/verhaeghe2018ijcai-compact/) doi:10.24963/IJCAI.2018/192

BibTeX

@inproceedings{verhaeghe2018ijcai-compact,
  title     = {{Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-Sets}},
  author    = {Verhaeghe, Hélène and Lecoutre, Christophe and Schaus, Pierre},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {1383-1389},
  doi       = {10.24963/IJCAI.2018/192},
  url       = {https://mlanthology.org/ijcai/2018/verhaeghe2018ijcai-compact/}
}