Learning from Failure in Constraint Satisfaction Search

Contents

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs), etc. 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 paper we present a method for learning from search using restarts, in order to identify these critical variables in a given constraint satisfaction problem, prior to solving. Our method is based on the weighted-degree heuristic introduced by Boussemart et al. and is 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 minimising the overhead of these restarts/probes. We show that random probing of the search space can boost the heuristics power by improving early decisions in search. We also provide an in-depth analysis of the effects of constraint weighting.