The Alldifferent Constraint with Precedences - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

The Alldifferent Constraint with Precedences

Résumé

We propose ALLDIFFPREC, a new global constraint that combines together an ALLDIFFERENT constraint with precedence constraints that strictly order given pairs of variables. We identify a number of applications for this global constraint including instruction scheduling and symmetry breaking. We give an efficient propagation algorithm that enforces bounds consistency on this global constraint. We show how to implement this propagator using a decomposition that extends the bounds consistency enforcing decomposition proposed for the ALLDIFFERENT constraint. Finally, we prove that enforcing domain consistency on this global constraint is NP-hard in general.
Fichier principal
Vignette du fichier
cpaior11.pdf (219.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00748652 , version 1 (05-11-2012)

Identifiants

  • HAL Id : lirmm-00748652 , version 1

Citer

Nina Narodytska, Christian Bessiere, Claude-Guy Quimper, Toby Walsh. The Alldifferent Constraint with Precedences. CPAIOR'11: International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming, Berlin, Germany. pp.36-52. ⟨lirmm-00748652⟩
130 Consultations
264 Téléchargements

Partager

Gmail Facebook X LinkedIn More