Pruning rules for constrained optimisation for conditional preferences

Show simple item record

dc.contributor.author Wilson, Nic
dc.contributor.author Trabelsi, Walid
dc.contributor.editor Lee, Jimmy
dc.date.accessioned 2014-02-25T12:27:22Z
dc.date.available 2014-02-25T12:27:22Z
dc.date.copyright 2011
dc.date.issued 2011-09
dc.identifier.citation WILSON, 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.startpage 804 en
dc.identifier.endpage 818 en
dc.identifier.isbn 978-3-642-23785-0
dc.identifier.isbn 978-3-642-23786-7
dc.identifier.issn 0302-9743
dc.identifier.uri http://hdl.handle.net/10468/1412
dc.identifier.doi 10.1007/978-3-642-23786-7_60
dc.description.abstract A 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.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer Berlin Heidelberg en
dc.relation.ispartof 17th International Conference on Principles and Practice of Constraint Programming (CP 2011)
dc.relation.ispartofseries Lecture Notes in Computer Science;6876
dc.relation.uri http://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_60 en
dc.subject Conditional preferences en
dc.subject Constrained optimisation en
dc.subject Constraint Satisfaction Problem (CSP) en
dc.subject CP-net en
dc.subject.lcsh Computer science en
dc.title Pruning rules for constrained optimisation for conditional preferences en
dc.type Conference item en
dc.internal.authorurl http://research.ucc.ie/profiles/D005/nwilson en
dc.internal.authorcontactother Nic Wilson, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: n.wilson@4c.ucc.ie en
dc.internal.availability Full text available en
dc.date.updated 2012-12-20T18:13:41Z
dc.description.version Accepted Version en
dc.internal.rssid 119864831
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.internal.copyrightchecked No !!CORA!! As per LCNS copyright transfer statement, authors can archive author versions with set statement and doi. en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Perugia, Italy en
dc.internal.placepublication Heidelberg, Berlin en
dc.internal.IRISemailaddress n.wilson@ucc.ie en
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/ en


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