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

Show simple item record Wilson, Nic Grimes, Diarmuid Freuder, Eugene C. 2013-04-24T11:52:57Z 2013-04-24T11:52:57Z 2010-01
dc.identifier.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 en
dc.identifier.volume 15 en
dc.identifier.issued 4 en
dc.identifier.startpage 540 en
dc.identifier.endpage 573 en
dc.identifier.issn 1383-7133
dc.identifier.doi 10.1007/s10601-010-9099-7
dc.description.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. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer en
dc.rights © Springer Science+Business Media, LLC 2010. The final publication is available at en
dc.subject Uncertain constraints en
dc.subject Incomplete CSPs en
dc.subject Interactive CSPs en
dc.subject Open constraints en
dc.subject Constraint elicitation en
dc.subject Preferences en
dc.subject Consistency en
dc.title Interleaving solving and elicitation of constraint satisfaction problems based on expected cost en
dc.type Article (peer-reviewed) en
dc.internal.authorurl en
dc.internal.authorcontactother Nic Wilson, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: en
dc.internal.availability Full text available en 2012-12-20T17:25:07Z
dc.description.version Accepted Version en
dc.internal.rssid 70046793
dc.internal.rssid 280163173
dc.internal.wokid 000280893400005
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Constraints en
dc.internal.copyrightchecked No. CORA - ROMEO. en
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Technology and Innovation Development Award (TIDA)/05/IN.1/I886 TIDA 09/IE/Costraint Baset Energy Cost Efficient Scheduling/
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/08/IN.1/I1912/IE/The Development of Artificial intelligence Approaches for Preferences in Combinational Problems/

Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement