Learned Value-Ordering Heuristics for Constraint Satisfaction

Contents

In global search for a solution to a constraint satisfaction problem, a value-ordering heuristic predicts which values are most likely to be part of a solution. When such a heuristic uses look-ahead, it often incurs a substantial computational cost. We propose an alternative approach, survivors-first, that gives rise to a family of dynamic value-ordering heuristics that are generic, adaptive, inexpensive to compute, and easy to implement. Survivors-first prefers values that are most often observed to survive propagation during search. This paper explores two algorithms, and several modifications to them, that learn to identify and recommend survivors. Empirical results show that these value-ordering heuristics greatly enhance the performance of several traditional variable-ordering heuristics on a variety of challenging problems.