Learning to Identify Global Bottlenecks in Constraint Satisfaction Search

All Papers

Using information from failures to guide subsequent search is an important technique for solving combinatorial problems in domains such as boolean satisfiability (SAT) and constraint satisfaction problems (CSPs). The information learnt can take various forms such as fine-grained information in the form of no-goods and explanations in CSPs and clause learning in SAT, or coarse-grained information in the form of constraint weighting in CSPs and clause weighting in SAT. In this paper we focus on CSPs, using constraint weighting with restarts in order to identify global bottlenecks in a problem. This information is then used by a "weighted-degree" heuristic to guide complete search, with the belief that instantiating these elements first will reduce the overall search effort required to either find a solution or prove the problem insoluble. We introduce two restarting strategies. ln WTDI (WeighTeD Information gathering) the weighted-degree heuristic itself is used with restarts; in RNDI (RaNDom Information gathering) random variable selection is combined with constraint weighting and restarts. For problems with clearly defined sources of global contention both approaches were superior to complete search with the original weighted degree heuristic. However when these "globally" difficult elements became more subtle, RNDI outperformed WTDI.