The Difference All-Difference Makes

Abstract

We perform a comprehensive theoretical and experimental analysis of the use of all-different constraints. We prove that generalizedarcconsistencyon such constraints lies between neighborhoodinverseconsistencyand, under a simplerestriction, path inverse consistency on thebinaryrepresentationoftheproblem.By generalizingtheargumentsof Kondrak and van Beek, weprovethatasearchalgorithmthat maintainsgeneralizedarc-consistency on all-different constraintsdominatesasearch algorithmthatmaintainsarc-consistencyonthebinaryrepresentation. Ourexperimentsshowthe practicalvalueofachievingthesehighlevelsof consistency. For example, wecansolvealmost allbenchmarkquasigroupcompletionproblems 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.