An Empirical Study of Dynamic Variable Ordering Heuristics for the
Constraint Satisfaction Problem
Research Report 96.05, School of Computer Studies, University of Leeds,
February 1996.
Ian P Gent, Ewan MacIntyre, Patrick Prosser, Barbara M Smith & Toby Walsh
Abstract
The constraint satisfaction community has developed a number of
heuristics for variable ordering during backtracking search. For
example, in conjunction with algorithms which check forwards,
the Fail-First (FF) and Brelaz (Bz) heuristics are cheap to evaluate
and are generally considered to be very effective. Recent work to
understand phase transitions in NP-complete problem classes enables us
to compare such heuristics over a large range of different kinds of
problems. Furthermore, we are now able to start to understand the
reasons for the success, and therefore also the failure, of
heuristics, and to introduce new heuristics which achieve the
successes and avoid the failures. In this paper, we present a
comparison of the Bz and FF heuristics in forward checking algorithms
applied to randomly-generated binary CSP's. We also introduce
new and very general heuristics and present an extensive study
of these. These new heuristics are usually as good as or better than
Bz and FF, and we identify problem classes where our new heuristics
can be orders of magnitude better. The result is a deeper
understanding of what helps heuristics to succeed or fail on hard
random problems in the context of forward checking, and the
identification of promising new heuristics worthy of further
investigation.
Back to "Barbara Smith
- Publications on Constraint Programming"