A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint

A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint

Xizhe Zhang, Qian Li, Weixiong Zhang

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1398-1403. https://doi.org/10.24963/ijcai.2018/194

The alldifferent constraint is an essential ingredient of most Constraints Satisfaction Problems (CSPs). It has been known that the generalized arc consistency (GAC) of alldifferent constraints can be reduced to the maximum matching problem in a value graph. The redundant edges, which do not appear in any maximum matching of the value graph, can and should be removed from the graph. The existing methods attempt to identify these redundant edges by computing the strongly connected components after finding a maximum matching for the graph. Here, we present a novel theorem for identification of the redundant edges. We show that some of the redundant edges can be immediately detected after finding a maximum matching. Based on this theoretical result, we present an efficient algorithm for processing alldifferent constraints. Experimental results on real problems show that our new algorithm significantly outperforms the-state-of-art approaches.
Keywords:
Constraints and SAT: Constraint Satisfaction
Constraints and SAT: Global Constraints
Constraints and SAT: Constraints: Solvers and Tools