abstract

A binary decision diagram (BDD) is a graph-based representation of a boolean function. BDDs were recently used as a propagation tool for solving multiple all-different constraints, in place of traditional domain propagation. This paper extends this work to "among" constraints, which are of central importance in sequencing and scheduling problems. Limited-width BDDs provide a relaxation of the feasible set that results in dramatic reduction of the search tree. Computational tests show substantial speedups relative to standard domain propagation. This is joint work with Samid Hoda and Willem-Jan van Hoeve.