Lexicographically-ordered constraint satisfaction problems

CORA will be unavailable from 08:00- 09:00 for regular maintenance on Tuesday, 28th May 2019. Apologies for any inconvenience this may cause.

Show simple item record

dc.contributor.author Freuder, Eugene C.
dc.contributor.author Heffernan, Robert
dc.contributor.author Wallace, Richard J.
dc.contributor.author Wilson, Nic
dc.date.accessioned 2013-04-30T16:53:29Z
dc.date.available 2013-04-30T16:53:29Z
dc.date.copyright 2010
dc.date.issued 2010-01
dc.identifier.citation Freuder, EC; Heffernan, R; Wallace, RJ; Wilson, N; (2010) 'Lexicographically-ordered constraint satisfaction problems'. Constraints, 15 (1):1-28. doi: 10.1007/s10601-009-9069-0 en
dc.identifier.volume 15 en
dc.identifier.issued 1 en
dc.identifier.startpage 1 en
dc.identifier.endpage 28 en
dc.identifier.uri http://hdl.handle.net/10468/1105
dc.identifier.doi 10.1007/s10601-009-9069-0
dc.description.abstract We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character, these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of heuristics that follow the preference order (lexical variable and value ordering). We describe relations between lexicographic CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter. We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms: a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including some for which the basic lexically ordered search is infeasible in practice. en
dc.description.sponsorship Science Foundation Ireland (00/PI.1/C075); Science Foundation Ireland (05/IN/1886.) en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer en
dc.relation.uri http://link.springer.com/article/10.1007%2Fs10601-009-9069-0
dc.rights © Springer Science + Business Media, LLC 2009. The final publication is available at http://link.springer.com/article/10.1007%2Fs10601-009-9069-0 en
dc.subject Constraint satisfaction en
dc.subject Preference en
dc.subject Lexicographic order en
dc.subject Soft constraint en
dc.subject Complete search en
dc.subject CP-nets en
dc.subject Preference en
dc.subject Optimization en
dc.subject Search en
dc.subject.lcsh Computer science. en
dc.title Lexicographically-ordered constraint satisfaction problems en
dc.type Article (peer-reviewed) 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-20T17:29:31Z
dc.description.version Accepted Version en
dc.internal.rssid 43334565
dc.internal.wokid 000273744400001
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Constraints en
dc.internal.copyrightchecked No en
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress n.wilson@ucc.ie 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