Identifying sources of global contention in constraint satisfaction search

Simple item page
dc.contributor.advisorWallace, Richard J.
dc.contributor.advisorFreuder, Eugene C.
dc.contributor.authorGrimes, Diarmuid
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2012-07-30T15:19:19Z
dc.date.available2012-07-30T15:19:19Z
dc.date.issued2012-07
dc.date.submitted2012-07-25
dc.description.abstractMuch work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine-grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this work we present two methods for learning from search using restarts, in order to identify these critical variables prior to solving. Both methods are based on the conflict-directed heuristic (weighted-degree heuristic) introduced by Boussemart et al. and are aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimizing the overhead of these restarts. We further examine the impact of different sampling strategies and different measurements of contention, and assess different restarting strategies for the heuristic. Finally, two applications for constraint weighting are considered in detail: dynamic constraint satisfaction problems and unary resource scheduling problems.en
dc.description.statusNot peer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationGrimes, D., 2012. Identifying sources of global contention in constraint satisfaction search. PhD Thesis, University College Cork.en
dc.identifier.urihttps://hdl.handle.net/10468/646
dc.language.isoenen
dc.publisherUniversity College Corken
dc.rights© 2012, Diarmuid Grimesen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/en
dc.subjectBoolean satisfiabilityen
dc.subjectConstraint weightingen
dc.subjectFailure in searchen
dc.subject.lcshConstraint programming (Computer science)en
dc.subject.lcshHeuristic programmingen
dc.subject.lcshComputer algorithmsen
dc.titleIdentifying sources of global contention in constraint satisfaction searchen
dc.typeDoctoral thesisen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD (Computer Science)en
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
GrimesD_PhD2012.pdf
Size:
5.57 MB
Format:
Adobe Portable Document Format
Description:
Full text available
Download
Thumbnail Image
Name:
DiarmuidGrimesPhD_Abstract.pdf
Size:
61.8 KB
Format:
Adobe Portable Document Format
Description:
Abstract
License bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
license.txt
Size:
5.75 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Thumbnail Image
Name:
DJGrimesLicense.pdf
Size:
803.98 KB
Format:
Adobe Portable Document Format
Description:
License
Collections
Doctoral Theses
College of Science, Engineering and Food Science - Doctoral Theses
Computer Science - Doctoral Theses