Molnár, Vince and Majzik, István (2017) Constraint Programming with Multivalued Decision Diagrams: A Saturation Approach. In: Proceedings of the 24th PhD MiniSymposium. BME MIT, Budapest, pp. 5457. ISBN 9789633132432

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 searchbased strategies enhanced with various optimizations to reduce the search space. One of such techniques involves multivalued 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 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  01 Aug 2017 08:01 
Last Modified:  01 Aug 2017 08:01 
URI:  http://real.mtak.hu/id/eprint/57683 
Actions (login required)
Edit Item 