Enhancing Set Constraint Solvers with Lexicographic Bounds - Université de Montpellier
Article Dans Une Revue Journal of Heuristics Année : 2008

Enhancing Set Constraint Solvers with Lexicographic Bounds

Andrew Sadler
  • Fonction : Auteur

Résumé

Since their beginning in constraint programming, set solvers have been applied to a wide range of combinatorial search problems, such as bin-packing, set partitioning, circuit design, and Combinatorial Design Problems. In this paper we present and evaluate a new means towards improving the practical reasoning power of Finite Set (FS) constraint solvers to better address such set problems with a particular attention to the challenging symmetrical set problems often cast as Combinato-rial Design Problems (CDPs). While CDPs find a natural formulation in the language of sets, in constraint programming literature, alternative models are often used due to a lack of efficiency of traditional FS solvers. We first identify the main structural components of CDPs that render their modeling suitable to set languages but their solving a technical challenge. Our new prototype solver extends the traditional subset variable domain with lexicographic bounds that better approximate a set domain by satisfying the cardinality restrictions applied to the variable , and allow for active symmetry breaking using ordering constraints. Our contribution includes the formal and practical framework of the new solver implemented on top of a traditional set solver, and an empirical evaluation on benchmark CDPs.
Fichier principal
Vignette du fichier
JHeur.pdf (395.4 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

Andrew Sadler, Carmen Gervet. Enhancing Set Constraint Solvers with Lexicographic Bounds. Journal of Heuristics, 2008, ⟨10.1007/s10732-007-9028-0⟩. ⟨hal-01742387⟩
105 Consultations
138 Téléchargements

Altmetric

Partager

More