The Difference All-Difference Makes

Abstract

We perform a comprehensive theoretical and experimental analysis of the use of all-different constraints. We prove that generalized arc-consistency on such constraints lies between neighborhood inverse consistency and, under a simple restriction, path inverse consistency on the binary representation of the problem. By generalizing the arguments of Kondrak and van Beek, we prove that a search algorithm that maintains generalized arc-consistency on all-different constraints dominates a search algorithm that maintains arc-consistency on the binary representation. Our experiments show the practical value of achieving these high levels of consistency. For example, we can solve almost all benchmark quasigroup completion problems up to order 25 with just a few branches of search. These results demonstrate the benefits of using non-binary constraints like all-different to identify structure in problems.