Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748652
Contributor : Joël Quinqueton <>
Submitted on : Monday, November 5, 2012 - 4:59:16 PM
Last modification on : Monday, July 20, 2020 - 1:06:04 PM
Document(s) archivé(s) le : Wednesday, February 6, 2013 - 3:56:14 AM

File

cpaior11.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨lirmm-00748652⟩

Share

Metrics

Record views

208

Files downloads

459