Reformulating Global Constraints: The SLIDE and REGULAR Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Reformulating Global Constraints: The SLIDE and REGULAR Constraints

Résumé

Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, Slide and Regular. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of Slide and Regular can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints.
Fichier principal
Vignette du fichier
sara07.pdf (264.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00195913 , version 1 (12-10-2019)

Identifiants

  • HAL Id : lirmm-00195913 , version 1

Citer

Christian Bessiere, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Claude-Guy Quimper, et al.. Reformulating Global Constraints: The SLIDE and REGULAR Constraints. SARA: Symposium on Abstraction, Reformulation, and Approximation, Jun 2007, Whistler, Canada. pp.80-92. ⟨lirmm-00195913⟩
197 Consultations
113 Téléchargements

Partager

Gmail Facebook X LinkedIn More