In the Quest of the Best Form of Local Consistency for Weighted CSP
Abstract
The weighted CSP (WCSP) framework is a soft constraint framework with a wide range of applications. In this paper, we consider the problem of maintaining local consistency during search for solving WCSP. We first refine the notions of directional arc consistency (DAC) and full directional arc consistency (FDAC) introduced in [Cooper, 2003] for binary WCSP, define algorithms that enforce these properties and study their complexities. We then consider algorithms that maintain either arc consistency (AC), DAC or FDAC during search. The efficiency of these algorithms is empirically studied. It appears that despite its high theoretical cost, the strongest FDAC property is the best choice. 1
Cite
Text
Larrosa and Schiex. "In the Quest of the Best Form of Local Consistency for Weighted CSP." International Joint Conference on Artificial Intelligence, 2003.Markdown
[Larrosa and Schiex. "In the Quest of the Best Form of Local Consistency for Weighted CSP." International Joint Conference on Artificial Intelligence, 2003.](https://mlanthology.org/ijcai/2003/larrosa2003ijcai-quest/)BibTeX
@inproceedings{larrosa2003ijcai-quest,
title = {{In the Quest of the Best Form of Local Consistency for Weighted CSP}},
author = {Larrosa, Javier and Schiex, Thomas},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2003},
pages = {239-244},
url = {https://mlanthology.org/ijcai/2003/larrosa2003ijcai-quest/}
}