Learned Value-Ordering Heuristics for Constraint Satisfaction

Zhijun Zhang, Susan L. Epstein

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.

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

Submitted: May 3, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.