Degree Type
Creative Component
Semester of Graduation
Spring 2019
Department
Computer Science
First Major Professor
Gianfranco Ciardo
Degree(s)
Master of Science (MS)
Major(s)
Computer Science
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.
Copyright Owner
Gupta, Nitesh
Copyright Year
2019
File Format
Recommended Citation
Gupta, Nitesh, "Constraint Programming Using Multi-Valued Decision Diagrams" (2019). Creative Components. 184.
https://lib.dr.iastate.edu/creativecomponents/184