Soft nogood store as a heuristic

Constraint satisfaction can be used to model problems such as graph coloring, scheduling, crossword generation and many others. The goal of solving a constraint satisfaction problem is to find a solution such that all variables are assigned without violating any constraints, or to prove that no solutions exist. Constraint satisfaction techniques are typically applied to problems that have no known polynomial time algorithms. Solving such problems requires exploration of a search space that is exponentially large with respect to the problem representation and many sophisticated techniques have been developed to do so efficiently. Non-trivial problems may take a significant amount of time to solve and during this time many infeasible states will be discovered; such states are known as nogoods. Nogoods are learned during search and are used to avoid revisiting already explored infeasible states, as discovering them may take a significant amount of time. Heuristics are used to guide search algorithms towards solutions, or to prove infeasibility. Some of the existing heuristics make use of nogoods learned during search to refine their guidance. I show how more heuristic guidance can be obtained from nogoods. I introduce the notion of soft nogoods and show how soft nogoods can be used as a source of heuristic guidance. Soft nogoods can be learned during search from classic nogoods and already existing soft nogoods. I describe how a set of soft nogoods can be used to estimate the amount of partial exploration of an arbitrary search space and then use this value to augment a number of existing heuristics. The accurate algorithm for computing this value is restrictively slow and so I present an approximation scheme that trades off some of its accuracy for speed. Learning all soft nogoods is impractical and to address this issue I describe learning schemes that selectively learn soft nogoods during search. I conduct an empirical evaluation of the resulting heuristics on a variety of constraint satisfaction problems to demonstrate the utility of soft nogoods for heuristic guidance.