Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search
Abstract
We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalised view of local consistency in semiring-based constraint satisfaction problems, we define constraint hierarchy k-consistency (CH-k-C) and give a CH-2-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 (FD) CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other FD CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.
Cite
Text
Bistarelli et al. "Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search." International Joint Conference on Artificial Intelligence, 2003. doi:10.1080/09528130802667690Markdown
[Bistarelli et al. "Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search." International Joint Conference on Artificial Intelligence, 2003.](https://mlanthology.org/ijcai/2003/bistarelli2003ijcai-solving/) doi:10.1080/09528130802667690BibTeX
@inproceedings{bistarelli2003ijcai-solving,
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 = {International Joint Conference on Artificial Intelligence},
year = {2003},
pages = {1364-1365},
doi = {10.1080/09528130802667690},
url = {https://mlanthology.org/ijcai/2003/bistarelli2003ijcai-solving/}
}