next up previous contents
Next: Intelligent Backtracking and nogood Up: Constructive Search Previous: Search Heuristics based on

Incomplete Constructive Search

For real industrial applications, the search space is usually too large for complete search to be possible. The branch and bound search yields better solutions with longer and longer delays until, in many cases, it fails to yield any new solutions but continues searching fruitlessly!

In cases where complete search is impractical, the heuristics guiding the search become very important. If bad heuristics are chosen the search may methodically explore some unpromising corner of the search space yielding very poor solutions which fail to drive the branch and bound search into more fruitful areas. Good heuristics depend on good constraint handling: the information returned from the constraint handlers is crucial in enabling the heuristics to focus search on promising regions. Moreover once some good choices have been made, propagation can achieve even better results supporting even better heuristics for future choices. This positive feedback produces a virtuous spiral.

Received wisdom suggests that local search techniques, based on solution repair, achieve faster convergence on good solutions than constructive search. However on several industrial applications our experience has shown the contrary. Good heuristics tailored to the application at hand has proved more effective in yielding high quality solutions than techniques based on solution repair.

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997