A Fast and Simple Algorithm for Bounds Consistency of the AllDifferent Constraint
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 245-249.
Abstract
In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint propagation. Previous studies have demonstrated that designing special purpose constraint propagators for commonly occurring constraints can significantly improve the efficiency of a constraint programming approach. In this paper we present a fast, simple algorithm for bounds consistency propagation of the alldifferent constraint. The algorithm has the same worst case behavior as the previous best algorithm but is much faster in practice. Using a variety of benchmark and random problems, we show that our algorithm outperforms existing bounds consistency algorithms and also outperforms-on problems with an easily identifiable property-state-ofthe-art commercial implementations of propagators for stronger forms of local consistency.
@inproceedings{ijcai2003p36,
title = {A Fast and Simple Algorithm for Bounds Consistency of the AllDifferent Constraint},
author = {López-Ortiz, Alejandro and Quimper, Claude-Guy and Tromp, John and van Beek, Peter},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {245--249},
year = {2003},
url = {https://ijcai.org/proceedings/2003/36},
}
TY - CPAPER TI - A Fast and Simple Algorithm for Bounds Consistency of the AllDifferent Constraint AU - López-Ortiz, Alejandro AU - Quimper, Claude-Guy AU - Tromp, John AU - van Beek, Peter T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 245 EP - 249 UR - https://ijcai.org/proceedings/2003/36 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
