2011/03/19 by Christian Bessière, Bessiere, Christian, Nina Narodytska +5
Computer Science · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Logic, programming, and type systems #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1103.3745
openalex publication_date 2011/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.