Global Filtering for the Disjointness Constraint on Fixed Cardinality Sets
Andrew Sadler, Carmen Gervet · 2004
Finite set constraints represent a natural choice to model configuration de-sign problems using set cardinality and disjointness, covering or partition con-straints over (families of) set variables. Such constraints are available in most set-based constraint languages, often in the form of n-ary decomposable constraints. The corresponding filtering algorithms make use of local bound consistency tech-niques. In this paper we show that when the set cardinality constraints are handled together with the n-ary constraints, and set variable domains are specified by set intervals, efficient global filtering algorithms can be derived. We consider the par-ticular case of the n-ary disjoint constraint disjoint([X1,...,Xn], [c1,...,cn]) for a family of pairwise disjoint sets Xi of fixed cardinality ci. We present a set of conditions and inference rules to infer Bounds Consistency (BC), together with an efficient global filtering algorithm. We also explain why this level of pruning cannot be achieved with a common FD formulation based on the alldiff constraint, enriched with lexicographic ordering constraints; but is actually equivalent to a