Using MDDs to solve problems via their decompositions

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.