Constraint Programming Using Multi-Valued Decision Diagrams
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract
We mainly focuses on the implementation of a solver for Constraint Satisfaction Prob- lems (CSP) using Multi-Valued Decision Diagrams (MDDs). The input to the solver is a constraint problem, modeled using the MiniZinc language. MEDDLY (Multi-terminal and Edge-valued Decision Diagram LibrarY) is used to find the possible solution space for a given constraint problem. The implemented solver also includes support for various global constraints (e.g. all_different, increasing, among). Capability to solve maximization and minimization problems is also added to the solver. The size of the intermediate MDD and the running time for any constraint problem is affected by the order in which various constraints are propagated. Work is done towards implementation of various strategies for constraint ordering. Eight different strategies are implemented and experiments are run to compare the performance output of each strategy.