Experimental evaluation of modern variable selection strategies in Constraint Satisfaction Problems
Thanasis Balafoutis, Kostas Stergiou · 2008
Constraint programming is a powerful technique for solving combinatorial search problems that draws on a wide range of methods from artificial intelligence and computer science. Constraint solvers search the solution space either systematically, as with backtracking or branch and bound algorithms, or use forms of local search which may be incomplete. Systematic methods typically interleave search and inference. A key factor that can dramatically reduce the search space is the criterion under which we decide which variable will be the next to be instantiated. Numerous heuristics have been proposed for this purpose in the literature. Recent years have seen the emergence of new and powerful methods for choosing variables during CSP search. Some of these methods exploit information about failures gathered throughout search and recorded in the form of constraint weights, while others measure the importance/impact of variable assignments for reducing the search space. In this paper we experimentally evaluate the most recent and powerful variable ordering heuristics, and new variants of them, over a wide range of academic, random and real world problems. Results demonstrate that heuristics based on failures are in general faster. To be precise, heuristic dom/wdeg and its variants are the dominant heuristics in most instances tried. 1