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


Download (496kB) | Preview


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.

Item Type: Book Section
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: MTMT SWORD
Date Deposited: 01 Aug 2017 08:01
Last Modified: 01 Aug 2017 08:01

Actions (login required)

Edit Item Edit Item