Monash University
Browse

Using MDDs to solve problems via their decompositions

Download (379.33 kB)
report
posted on 2022-07-25, 00:20 authored by J Schimpf
Multivalued Decision Diagrams (MDDs) are directed acyclic graphs that can be used to represent relations in a compact way. In finite-domain Constraint Programming, constraints can be represented in extension, i.e. by their truth tables, which can be encoded as MDDs. Recently, an algorithm has been proposed for efficiently computing Generalised Arc Consistency on the basis of such an MDD representation. In this report we investigate several ideas for how to exploit these new tools for solving hard constraint satisfaction and optimization problems. Our general approach consists in working on a number of subproblems separately, representing the results as MDDs, and using these MDDs to gain efficiency in the solution of the problem as a whole.

History

Technical report number

2010/257

Year of publication

2010

Usage metrics

    Monash Information Technology Technical Reports

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC