Experimental studies of variable selection strategies based on constraint weights

Variable ordering heuristics that sample information before or during search in order to inform subsequent decisions have shown better performance and greater robustness than standard heuristics. One such strategy, the “weighted degree heuristic,” is based on weighting constraints according to their involvement in failure during search. A more recent approach uses “random probing” with restarting to gain information less subject to sampling bias. To date, these approaches have not been carefully analysed experimentally. In the present work, several important findings are presented, including a better delineation of the class of events that is sampled, an analysis of the importance of informed choices at the beginning of search, and a demonstration that random probing identifies sources of global contention effectively even when these are not clearly demarcated. These experiments show how empirical analysis can clarify subtle issues in the analysis of heuristic procedures for difficult search problems.