Identifying sources of global contention in constraint satisfaction search

Show simple item record

dc.contributor.advisor Wallace, Richard J.
dc.contributor.advisor Freuder, Eugene C. Grimes, Diarmuid 2012-07-30T15:19:19Z 2012-07-30T15:19:19Z 2012-07 2012-07-25
dc.identifier.citation Grimes, D., 2012. Identifying sources of global contention in constraint satisfaction search. PhD Thesis, University College Cork. en
dc.description.abstract Much 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.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher University College Cork en
dc.rights © 2012, Diarmuid Grimes en
dc.rights.uri en
dc.subject Boolean satisfiability en
dc.subject Constraint weighting en
dc.subject Failure in search en
dc.subject.lcsh Constraint programming (Computer science) en
dc.subject.lcsh Heuristic programming en
dc.subject.lcsh Computer algorithms en
dc.title Identifying sources of global contention in constraint satisfaction search en
dc.type Doctoral thesis en
dc.type.qualificationlevel Doctoral en
dc.type.qualificationname PhD (Computer Science) en
dc.internal.availability Full text available en
dc.description.version Accepted Version en
dc.contributor.funder Science Foundation Ireland en
dc.description.status Not peer reviewed en Computer Science en

Files in this item

The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record

© 2012, Diarmuid Grimes Except where otherwise noted, this item's license is described as © 2012, Diarmuid Grimes
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