Early and efficient identification of useless constraint propagation for alldifferent constraints

Constraint propagation and backtracking are two basic techniques for solving constraint satisfaction problems (CSPs). During the search for a solution, the variable and value pairs that do not belong to any solution can be discarded by constraint propagation to ensure generalized arc consistency to avoid the fruitless search. However, constraint propagation is frequently invoked with little effect on many CSPs. Much effort has been devoted to predicting when to invoke constraint propagation for solving a CSP. However, no effective approach has been developed for the alldifferent constraint. Here we present a novel theorem for identifying the edges in a value graph of the alldifferent constraint whose removal can lead to useless constraint propagation. We prove that if an alternating cycle exists for a prospectively removable edge that represents a variable-value assignment, the edge (and the assignment) can be discarded without constraint propagation. Based on this theorem, we developed a novel optimization technique for early detection of useless constraint propagation which can be incorporated in any existing algorithm for the alldifferent constraint. Our implementation of the new method achieved speedup by a factor of 1 to 5 over the state-of-art approaches on 93 benchmark problem instances in 8 domains. Besides, the new algorithm is scalable well and runs increasingly faster than the existing methods on larger problems.