Semester of Graduation
First Major Professor
Master of Science (MS)
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.
Gupta, Nitesh, "Constraint Programming Using Multi-Valued Decision Diagrams" (2019). Creative Components. 184.