Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1364-1364.
Abstract
We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalized view of local consistency in semiring-based constraint satisfaction problems (SCSPs), we define constraint hierarchy k-consistency (CH-k-C) and give a CH2-C enforcement algorithm. We demonstrate how the CH-2-C algorithm can be seamlessly integrated into the ordinary branch-and-bound algorithm to make it a finite domain CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other finite domain CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.
@inproceedings{ijcai2003p199,
title = {Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search},
author = {Bistarelli, Stefano and Codognet, Philippe and Hui, Kin Chuen and Lee, Jimmy Ho-Man},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1364--1364},
year = {2003},
url = {https://ijcai.org/proceedings/2003/199},
}
TY - CPAPER TI - Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search AU - Bistarelli, Stefano AU - Codognet, Philippe AU - Hui, Kin Chuen AU - Lee, Jimmy Ho-Man T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1364 EP - 1364 UR - https://ijcai.org/proceedings/2003/199 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
