Lexicographically-ordered constraint satisfaction problems

Simple item page
dc.contributor.authorFreuder, Eugene C.
dc.contributor.authorHeffernan, Robert
dc.contributor.authorWallace, Richard J.
dc.contributor.authorWilson, Nic
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2013-04-30T16:53:29Z
dc.date.available2013-04-30T16:53:29Z
dc.date.copyright2010
dc.date.issued2010-01
dc.date.updated2012-12-20T17:29:31Z
dc.description.abstractWe 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.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationFreuder, EC; Heffernan, R; Wallace, RJ; Wilson, N; (2010) 'Lexicographically-ordered constraint satisfaction problems'. Constraints, 15 (1):1-28. doi: 10.1007/s10601-009-9069-0en
dc.identifier.doi10.1007/s10601-009-9069-0
dc.identifier.endpage28en
dc.identifier.issued1en
dc.identifier.journaltitleConstraintsen
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/1105
dc.identifier.volume15en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/00/PI.1/C075/IE/Constraint Computation: Automation and Application/
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.urihttp://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-0en
dc.subjectConstraint satisfactionen
dc.subjectPreferenceen
dc.subjectLexicographic orderen
dc.subjectSoft constrainten
dc.subjectComplete searchen
dc.subjectCP-netsen
dc.subjectPreferenceen
dc.subjectOptimizationen
dc.subjectSearchen
dc.subject.lcshComputer science.en
dc.titleLexicographically-ordered constraint satisfaction problemsen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
FreuderHWW-2010.pdf
Size:
529.58 KB
Format:
Adobe Portable Document Format
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