Succeed-first or Fail-first: A Case Study in Variable and Value Ordering

Research Report 96.26, School of Computer Studies, University of Leeds, September 1996.
Barbara M Smith

Abstract

It is well known that appropriate variable and value ordering heuristics are often crucial when solving constraint satisfaction problems. A variable ordering heuristic which is often recommended, and is often successful, is based on the `fail-first' principle: choose next the variable with the smallest remaining domain. General-purpose value ordering heuristics are less common, but it has been argued that a value which has least effect on future choices should be chosen, a kind of `succeed-first' strategy.

This paper considers variable and value ordering heuristics for the car sequencing problem. A number of cars are to be made on a production line: each of them may require one or more options which are installed at different stations on the line. The option stations have lower capacity than the rest of the production line, e.g. a station may be able to cope with at most one car out of every two. The cars are to be arranged in sequence so that these capacities are not exceeded.

The choice of variable and value ordering heuristics has a dramatic effect on solution time for this problem. However, the fail-first variable ordering heuristic does not give good results: and in fact it is shown that dynamic variable ordering is unsuitable for this problem. Similarly, succeed-first value ordering does not work, and an ordering based on fail-first is a better choice. Reasons why conventional wisdom fails in this case, and could be expected to fail in similar cases, are identified.

Back to "Barbara Smith - Publications on Constraint Programming"