The Alldifferent Constraint with Precedences

Abstract : 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.
Type de document :
Communication dans un congrès
CPAIOR'11: International Conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming, Berlin, Germany. pp.36-52, 2011
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748652
Contributeur : Joël Quinqueton <>
Soumis le : lundi 5 novembre 2012 - 16:59:16
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : mercredi 6 février 2013 - 03:56:14

Fichier

cpaior11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00748652, version 1

Collections

Citation

Nina Narodytska, Christian Bessière, 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, 2011. 〈lirmm-00748652〉

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

237