In Search of the Best Constraint Satisfaction Search

Abstract

We present the results of an empirical study of several constraint satisfaction search algorithms and heuristics. Using a random problem generator that allows us to create instances with given characteristics, we show how the relative performance of various search methods varies with the number of variables, the tightness of the constraints, and the sparseness of the constraint graph. A version of backjumping using a dynamic variable ordering heuristic is shown to be extremely effective on a wide range of problems. We conducted our experiments with problem instances drawn from the 50% satisfiable range. 1. Introduction We are interested in studying the behavior of algorithms and heuristics that can solve large and hard constraint satisfaction problems via systematic search. Our approach is to focus on the average-case behavior of several search algorithms, all variations of backtracking search, by analyzing their performance over a large number of randomly generated proble...