Solving finite domain constraint hierarchies by local consistency and tree search

被引：3

作者：

Bistarelli, Stefano ^{[1
,2
]}

Codognet, Philippe ^{[3
]}

Hui, H. K. C. ^{[4
]}

Lee, J. H. M. ^{[4
]}

机构：

[1] CNR, Ist Informat & Telemat, I-56100 Pisa, Italy

[2] Univ G DAnnunzio, Dipartimento Sci, Pescara, Italy

[3] Univ Paris 06, Dept Comp Sci, Paris, France

[4] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Hong Kong, Peoples R China

来源：

JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE | 2009年 / 21卷 / 04期

关键词：

constraint hierarchies; soft constraints; local consistency;

D O I：

10.1080/09528130802667690

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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.

引用

页码：233 / 257

页数：25