Trying Harder to Fail First
Research Report 97.45, School of Computer Studies, University of Leeds,
November 1997.
Barbara M Smith and Stuart A Grant
Abstract
Variable ordering heuristics can have a profound effect on the performance
of backtracking search algorithms for constraint satisfaction problems.
The smallest-remaining-domain heuristic is a commonly-used dynamic variable
ordering heuristic, used in conjunction with algorithms such as
forward checking which look ahead at the effects of each variable
instantiation on those variables not yet instantiated. This heuristic has
been explained as an implementation of the fail-first principle, stated by
Haralick and Elliott, i.e. that the next variable selected should be the one
which is most likely to result in an immediate failure.
We calculate the probability that a variable will fail when using
the forward checking algorithm to solve a class of binary CSPs.
We derive a
series of heuristics, starting with smallest-remaining-domain,
based on increasingly accurate estimates of this
probability, and predict
that if the fail-first principle is sound, the more accurate the estimate
the better the performance should
be. We describe experiments applying these heuristics, in conjunction
with the forward checking algorithm, to a
large set of randomly-generated problems from the same class.
Our predictions are not borne out by the experimental results:
putting more effort into estimating the
probability does not in general pay off. Our results thus
refute the fail-first principle and show that the success of
smallest-remaining-domain and related heuristics must be
explained in some other way.
Back to "Barbara Smith
- Publications on Constraint Programming"