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.
Cite
Text
Stergiou and Walsh. "The Difference All-Difference Makes." International Joint Conference on Artificial Intelligence, 1999.Markdown
[Stergiou and Walsh. "The Difference All-Difference Makes." International Joint Conference on Artificial Intelligence, 1999.](https://mlanthology.org/ijcai/1999/stergiou1999ijcai-difference/)BibTeX
@inproceedings{stergiou1999ijcai-difference,
title = {{The Difference All-Difference Makes}},
author = {Stergiou, Kostas and Walsh, Toby},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1999},
pages = {414-419},
url = {https://mlanthology.org/ijcai/1999/stergiou1999ijcai-difference/}
}