Generic Global Constraints based on MDDs
  Constraint Programming (CP) has been successfully applied to both constraint
satisfaction and constraint optimization problems. A wide variety of
specialized global constraints provide critical assistance in achieving a good
model that can take advantage of the structure of the problem in the search for
a solution. However, a key outstanding issue is the representation of 'ad-hoc'
constraints that do not have an inherent combinatorial nature, and hence are
not modeled well using narrowly specialized global constraints. We attempt to
address this issue by considering a hybrid of search and compilation.
Specifically we suggest the use of Reduced Ordered Multi-Valued Decision
Diagrams (ROMDDs) as the supporting data structure for a generic global
constraint. We give an algorithm for maintaining generalized arc consistency
(GAC) on this constraint that amortizes the cost of the GAC computation over a
root-to-leaf path in the search tree without requiring asymptotically more
space than used for the MDD. Furthermore we present an approach for
incrementally maintaining the reduced property of the MDD during the search,
and show how this can be used for providing domain entailment detection.
Finally we discuss how to apply our approach to other similar data structures
such as AOMDDs and Case DAGs. The technique used can be seen as an extension of
the GAC algorithm for the regular language constraint on finite length input.
