Interleaving solving and elicitation of constraint satisfaction problems based on expected cost

Wilson, Nic; Grimes, Diarmuid; Freuder, Eugene C.

Interleaving solving and elicitation of constraint satisfaction problems based on expected cost

Files

Wilson-Grimes-Freuder-2010-for-website.pdf(456.8 KB)

Accepted Version

Date

2010-01

Authors

Wilson, Nic

Grimes, Diarmuid

Freuder, Eugene C.

Publisher

Springer

Published Version

10.1007/s10601-010-9099-7

Abstract

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 the satisfaction of 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 the unknowns that 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.

Keywords

Uncertain constraints , Incomplete CSPs , Interactive CSPs , Open constraints , Constraint elicitation , Preferences , Consistency

Citation

Wilson, N., Grimes, D. and Freuder, E. C. (2010) 'Interleaving solving and elicitation of constraint satisfaction problems based on expected cost', Constraints, 15(4), pp. 540-573. doi: 10.1007/s10601-010-9099-7