# The Alldifferent Constraint With Precedences ?

Christian Bessiere 1, Nina Narodytska 2, Claude-Guy Quimper 3and Toby Walsh 2 1 CNRS/LIRMM, Montpellier, email: bessiere@lirmm.fr 2 NICTA and University of NSW, Sydney, email:{nina.narodytska,toby.walsh}@nicta.com.au 3 Universite Laval, Qu ´ ebec, email: claude-guy.quimper@ift.ulaval.ca ´
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.

## 1 Introduction

One of the important features of constraint programming are global constraints. These capture common modelling patterns (e.g. "these jobs need to be processed on the same machine so must take place at different times"). In addition, efficient propagation algorithms are associated with global constraints for pruning the search space (e.g. "these 5 jobs have only 4 time slots between them so, by a pigeonhole argument, the problem is infeasible"). One of the oldest and most useful global constraints is the ALLDIFFERENT
constraint [1]. This specifies that a set of variables takes all different values. Several algorithms have been proposed for propagating this constraint (e.g. [2–6]). Such propagators can have a significant impact on our ability to solve problems (see, for instance,
[7]). It is not hard to provide pathological problems on which some of these propagation algorithms provide exponential savings. A number of hybrid frameworks have been proposed to combine the benefits of such propagation algorithms and OR methods like integer linear programming (see, for instance, [8]). In addition, the convex hull of a number of global constraints has been studied in detail (see, for instance, [9]).

In this paper, we consider a modelling pattern [10] that occurs in many problems involving ALLDIFFERENT constraints. In addition to the constraint that no pair of variables can take the same value, we may also have a constraint that certain pairs of variables are ordered (e.g. "these two jobs need to be processed on the same machine so must take place at different times, but the first job must be processed before the second"). We propose a new global constraint, ALLDIFFPREC that captures this pattern.

This global constraint is a specialization of the general framework that combines several ?Supported by the Australian Government's Department of Broadband, Communications and the Digital Economy and the ARC.