Variable Ordering Heuristics Show Promise

Promise is the ability to make choices that lead to a solution when one exists. The traditional intuition behind variable ordering heuristics is Haralick and Elliott’s fail-first principle: choose the variable such that assigning it is most likely to lead to a domain wipe-out (in AIJ 14, 1980). In contrast, the standard belief about value ordering heuristics is based on Geelen’s discussion (in ECAI’92): choose a value that is most likely to participate in a solution. It is not clear a priori that changes in variable ordering change the likelihood of finding a solution in a way that will affect overall performance significantly. In this paper we show that promise does have a meaning for variable ordering heuristics and that the level of promise of a variable ordering heuristic can be measured. In addition, we show that the promise of different variable ordering heuristics is different and that the level of promise of a variable ordering heuristic correlates with search cost for problems with many solutions.

Authors and Affiliations

1. Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Cork, Ireland

   J. Christopher Beck & Richard J. Wallace

2. Department of Computing Science, University of Glasgow, Scotland

   Patrick Prosser

Editors and Affiliations

1. Clayton School of IT, Monash University, Australia

   Mark Wallace

Reprints and permissions

© 2004 Springer-Verlag Berlin Heidelberg

Policies and ethics