Constraint Programming Using Multi-Valued Decision Diagrams

Thumbnail Image
Date
2019-01-01
Authors
Gupta, Nitesh
Major Professor
Gianfranco Ciardo
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.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
creative component
Comments
Rights Statement
Copyright
Tue Jan 01 00:00:00 UTC 2019
Funding
Supplemental Resources
Source