Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries
Résumé
Finite set constraints represent a natural choice to model configuration design problems using set cardinality and disjointness, covering or partition constraints 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 techniques. 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 particular case of the n-ary disjoint constraint disjoint([X 1 ,. .. , X n ], [c 1 ,. .. , c n ]) for a family of pairwise disjoint sets X i of fixed cardinality c i. 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 dual FD representation based on the Generalized Cardinality Constraint.
Domaines
Intelligence artificielle [cs.AI]Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...