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

Simple item page
dc.contributor.authorWilson, Nic
dc.contributor.authorGrimes, Diarmuid
dc.contributor.authorFreuder, Eugene C.
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2013-04-24T11:52:57Z
dc.date.available2013-04-24T11:52:57Z
dc.date.issued2010-01
dc.date.updated2012-12-20T17:25:07Z
dc.description.abstractWe 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.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationWilson, 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-7en
dc.identifier.doi10.1007/s10601-010-9099-7
dc.identifier.endpage573en
dc.identifier.issn1383-7133
dc.identifier.issued4en
dc.identifier.journaltitleConstraintsen
dc.identifier.startpage540en
dc.identifier.urihttps://hdl.handle.net/10468/1083
dc.identifier.volume15en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.projectinfo: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.projectinfo: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/
dc.relation.urihttp://link.springer.com/article/10.1007%2Fs10601-010-9099-7
dc.rights© Springer Science+Business Media, LLC 2010. The final publication is available at link.springer.com.en
dc.subjectUncertain constraintsen
dc.subjectIncomplete CSPsen
dc.subjectInteractive CSPsen
dc.subjectOpen constraintsen
dc.subjectConstraint elicitationen
dc.subjectPreferencesen
dc.subjectConsistencyen
dc.titleInterleaving solving and elicitation of constraint satisfaction problems based on expected costen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Wilson-Grimes-Freuder-2010-for-website.pdf
Size:
456.8 KB
Format:
Adobe Portable Document Format
Description:
Accepted Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles
Insight Centre for Data Analytics - Journal Articles