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

File Format

PDF

Share

COinS