Multi-valued decision diagrams (MDDs) have emerged as an effective technology for solving combinatorial optimization problems. We focus here on the use of decision diagrams in the context of constraint programming and offer two parts: 1) an overview of MDD-based constraint programming, and 2) a description and demonstration of the Haddock system to specify and compile MDD-propagators within a constraint programming solver.

MDD-based constraint propagation was first introduced by Andersen et al. in 2007. They introduced the concept of relaxed decision diagrams as a mechanism to enhance the propagation of information between constraints: Instead of using a domain store, they proposed using an ‘MDD store’ to represent and communicate more structural relationships between variables. As a consequence, the search tree size can be dramatically reduced. Since then, many papers have further studied the use of decision diagrams in constraint programming, as well as in other related areas such as mathematical programming. The first part of this tutorial will describe the core concepts of MDD-based constraint propagation and provide examples on global constraints such as AllDifferent, Among, and Disjunctive.

The second part describes the system Haddock. It provides a specification language and implementation architecture for automatic decision diagram compilation. Haddock provides the rules for refining (splitting) and filtering (propagating) MDD abstractions. The language allows to specify heuristics to guide the compilation process. Haddock allows the user to declare multiple MDDs within a CP model, each associated with a suitable set of constraints, and automatically integrates the MDD propagators into the constraint propagation fixpoint computation. We will give an overview, provide examples on constraints such as Among, Gcc, and (weighted) Sum, and describe examples. Participants are invited to download the Haddock to practice during the tutorial.