next up previous contents
Next: Depth-First Search and Backtracking Up: Constructive Search Previous: Constructive Search

Branch and Bound

In the preceding sections we have encountered two optimisation procedures, the finite domain procedure minimize and the MIP procedure optimize. Both optimisation procedures implement an algorithm called branch and bound, which posts a new constraint, each time it finds a solution, that the cost of future solutions must be better than the cost of the current best solution. Eventually the new constraint will be unsatisfiable, and the algorithm will have proved that it has found the optimum.

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