Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries - Université de Montpellier Accéder directement au contenu
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⟩
140 Consultations
153 Téléchargements

Partager

Gmail Facebook X LinkedIn More