AllDifferent swMATH ID: 8967 Software Authors: Christian Bessiere, Nina Narodytska, Claude-Guy Quimper, Toby Walsh Description: The AllDifferent Constraint with Precedences. 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. Homepage: http://link.springer.com/chapter/10.1007%2F978-3-642-21311-3_6 Keywords: constraint-programming; global constraints; { t AtMostNValue}; shift minimisation personnel task scheduling problem Related Software: Algorithm 457; ptsplib; AtMostNValue; Choco; SDPLR; CSDP; MulticoreBSP; BSPedupack; GitHub; Gecode; BSPonMPI Cited in: 4 Publications all top 5 Cited by 11 Authors 1 Banković, Milan 1 Bessiere, Christian 1 de Framond, Félix 1 Fages, Jean-Guillaume 1 Lallouet, Arnaud 1 Lapègue, Tanguy 1 Narodytska, Nina 1 Petitet, Antoine 1 Quimper, Claude-Guy 1 Suijlen, Wijnand 1 Walsh, Toby Cited in 2 Serials 1 Artificial Intelligence 1 Logical Methods in Computer Science Cited in 2 Fields 4 Computer science (68-XX) 4 Operations research, mathematical programming (90-XX) Citations by Year