Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries - Université de Montpellier
Communication Dans Un Congrès Année : 2004

Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries

Andrew Sadler
  • Fonction : Auteur

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.
Fichier principal
Vignette du fichier
CP04.pdf (250.68 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01742383 , version 1 (24-03-2018)

Identifiants

  • HAL Id : hal-01742383 , version 1

Citer

Andrew Sadler, Carmen Gervet. Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries. CP'04 Tenth International Conference on Principles and Practice of Constraint Programming, 2004, Toronto, Canada. ⟨hal-01742383⟩
149 Consultations
174 Téléchargements

Partager

More