Pruning rules for constrained optimisation for conditional preferences

Simple item page
dc.contributor.authorWilson, Nic
dc.contributor.authorTrabelsi, Walid
dc.contributor.editorLee, Jimmy
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2014-02-25T12:27:22Z
dc.date.available2014-02-25T12:27:22Z
dc.date.copyright2011
dc.date.issued2011-09
dc.date.updated2012-12-20T18:13:41Z
dc.description.abstractA depth-first search algorithm can be used to find optimal solutions of a Constraint Satisfaction Problem (CSP) with respect to a set of conditional preferences statements (e.g., a CP-net). This involves checking at each leaf node if the corresponding solution of the CSP is dominated by any of the optimal solutions found so far; if not, then we add this solution to the set of optimal solutions. This kind of algorithm can clearly be computationally expensive if the number of solutions is large. At a node N of the search tree, with associated assignment b to a subset of the variables B, it may happen that, for some previously found solution a, either (a) a dominates all extensions of b; or (b) a does not dominate any extension of b. The algorithm can be significantly improved if we can find sufficient conditions for (a) and (b) that can be efficiently checked. In case (a), we can backtrack since we need not continue the search below N; in case (b), α does not need to be considered in any node below the current node N. We derive a sufficient condition for (b), and three sufficient conditions for (a). Our experimental testing indicates that this can make a major difference to the efficiency of constrained optimisation for conditional preference theories including CP-nets.en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationWILSON, N., TRABELSI, W. 2011. Pruning rules for constrained optimisation for conditional preferences. In: LEE, J. (ed.) Principles and Practice of Constraint Programming - CP 2011. Perugia, Italy, 12-16 Sep. Berlin, Heidelberg: Springer, pp 804-818.en
dc.identifier.doi10.1007/978-3-642-23786-7_60
dc.identifier.endpage818en
dc.identifier.isbn978-3-642-23785-0
dc.identifier.isbn978-3-642-23786-7
dc.identifier.issn0302-9743
dc.identifier.startpage804en
dc.identifier.urihttps://hdl.handle.net/10468/1412
dc.language.isoenen
dc.publisherSpringer Berlin Heidelbergen
dc.relation.ispartof17th International Conference on Principles and Practice of Constraint Programming (CP 2011)
dc.relation.ispartofseriesLecture Notes in Computer Science;6876
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/en
dc.relation.urihttp://link.springer.com/chapter/10.1007%2F978-3-642-23786-7_60
dc.rights© 2011, Springer-Verlag GmbH Berlin Heidelberg. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-23786-7_60en
dc.subjectConditional preferencesen
dc.subjectConstrained optimisationen
dc.subjectConstraint Satisfaction Problem (CSP)en
dc.subjectCP-neten
dc.subject.lcshComputer scienceen
dc.titlePruning rules for constrained optimisation for conditional preferencesen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Pruning_rules_for_CP-11.pdf
Size:
335.21 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 - Conference Items
Insight Centre for Data Analytics - Conference Items