Identifying sources of global contention in constraint satisfaction search
Loading...
Files
Full text available
Date
2012-07
Authors
Grimes, Diarmuid
Journal Title
Journal ISSN
Volume Title
Publisher
University College Cork
Published Version
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.
Description
Keywords
Boolean satisfiability , Constraint weighting , Failure in search
Citation
Grimes, D., 2012. Identifying sources of global contention in constraint satisfaction search. PhD Thesis, University College Cork.