Constraint Programming with Multi-valued Decision Diagrams: A Saturation Approach

Molnár, Vince and Majzik, István (2017) Constraint Programming with Multi-valued Decision Diagrams: A Saturation Approach. In: Proceedings of the 24th PhD Mini-Symposium. BME MIT, Budapest, pp. 54-57. ISBN 978-963-313-243-2

Preview

Text Minisymposium2017_Molnar_PDFA.pdf Download (496kB) | Preview

Abstract

Constraint programming is a declarative way of modeling and solving optimization and satisfiability problems over finite domains. Traditional solvers use search-based strategies enhanced with various optimizations to reduce the search space. One of such techniques involves multi-valued decision diagrams (MDD) to maintain a superset of potential solutions, gradually discarding combinations of values that fail to satisfy some constraint. Instead of the relaxed MDDs representing a superset, we propose to use exact MDDs to compute the set of solutions directly without search, compactly encoding all the solutions instead of enumerating them. Our solution relies on the main idea of the saturation algorithm used in model checking to reduce the required computational cost. Preliminary results show that this strategy can keep the size of intermediate MDDs small during the computation.

Actions (login required)

Edit Item