Skip to main content

TS

The AllDifferent constraint with precedences

Authors

Christian Bessiere, Nina Narodytska, Claude-Guy Quimper and Toby Walsh

CNRS

NICTA

Universite Laval
Quebec

Abstract

We propose AllDiffPrecedence, 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.

BibTeX Entry

  @inproceedings{Bessiere_NQW_11,
    publisher        = {Springer},
    author           = {Bessiere, Christian and Narodytska, Nina and Quimper, Claude-Guy and Walsh, Toby},
    month            = may,
    year             = {2011},
    title            = {The {AllDifferent} Constraint with Precedences},
    booktitle        = {8th International Conference on Integration of Artificial Intelligence and Operations Research
                        Techniques in Constraint Programming for Combinatorial Optimization Problems},
    pages            = {36--52},
    address          = {BERLIN}
  }

Download

Served by Apache on Linux on seL4.