In the quest of the best form of local consistency for Weighted CSP
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 239-243.
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 (FDA C) 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.
@inproceedings{ijcai2003p35,
title = {In the quest of the best form of local consistency for Weighted CSP},
author = {Larrosa, Javier and Schiex, Thomas},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {239--243},
year = {2003},
url = {https://ijcai.org/proceedings/2003/35},
}
TY - CPAPER TI - In the quest of the best form of local consistency for Weighted CSP AU - Larrosa, Javier AU - Schiex, Thomas T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 239 EP - 243 UR - https://ijcai.org/proceedings/2003/35 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
