TY - CHAP
T1 - A cost-based model and algorithms for interleaving solving and elicitation of CSPs
AU - Wilson, Nic
AU - Grimes, Diarmuid
AU - Freuder, Eugene C.
PY - 2007
Y1 - 2007
N2 - We consider Constraint Satisfaction Problems in which constraints can be initially incomplete, where it is unknown whether certain tuples satisfy the constraint or not. We assume that we can determine such an unknown tuple, i.e., find out whether this tuple is in the constraint or not, but doing so incurs a known cost, which may vary between tuples. We also assume that we know the probability of an unknown tuple satisfying a constraint. We define algorithms for this problem, based on backtracking search. Specifically, we consider a simple iterative algorithm based on a cost limit on which unknowns may be determined, and a more complex algorithm that delays determining an unknown in order to estimate better whether doing so is worthwhile. We show experimentally that the more sophisticated algorithms can greatly reduce the average cost.
AB - We consider Constraint Satisfaction Problems in which constraints can be initially incomplete, where it is unknown whether certain tuples satisfy the constraint or not. We assume that we can determine such an unknown tuple, i.e., find out whether this tuple is in the constraint or not, but doing so incurs a known cost, which may vary between tuples. We also assume that we know the probability of an unknown tuple satisfying a constraint. We define algorithms for this problem, based on backtracking search. Specifically, we consider a simple iterative algorithm based on a cost limit on which unknowns may be determined, and a more complex algorithm that delays determining an unknown in order to estimate better whether doing so is worthwhile. We show experimentally that the more sophisticated algorithms can greatly reduce the average cost.
UR - https://www.scopus.com/pages/publications/38149095043
U2 - 10.1007/978-3-540-74970-7_47
DO - 10.1007/978-3-540-74970-7_47
M3 - Chapter
AN - SCOPUS:38149095043
SN - 3540749691
SN - 9783540749691
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 666
EP - 680
BT - Principles and Practice of Constraint Programming - CP 2007 - 13th International Conference, CP 2007, Proceedings
PB - Springer Verlag
T2 - 13th International Conference on Principles and Practice of Constraint Programming, CP 2007
Y2 - 23 September 2007 through 27 September 2007
ER -