Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Branch-and-Bound Solvers

 

The depth-first and breadth-first backtracking algorithms described in the preceding sections both naıvely traverse the entire solution space. However, sometimes we can determine that a given node in the solution space does not lead to the optimal solution--either because the given solution and all its successors are infeasible or because we have already found a solution that is guaranteed to be better than any successor of the given solution. In such cases, the given node and its successors need not be considered. In effect, we can prune  the solution tree, thereby reducing the number of solutions to be considered.

For example, consider the scales balancing problem described in Section gif. Consider a partial solution tex2html_wrap_inline67325 in which we have placed k weights onto the pans ( tex2html_wrap_inline67329) and, therefore, n-k weights remain to be placed. The difference between the weights of the left and right pans is given by

displaymath67321

and the sum of the weights still to be placed is

displaymath67322

Suppose that tex2html_wrap_inline67333. That is, the total weight remaining is less than the difference between the weights in the two pans. Then, the best possible solution that we can obtain without changing the positions of the weights that have already been placed is tex2html_wrap_inline67335 The quantity tex2html_wrap_inline67337 is a lower bound on the value of the objective function for all the solutions in the solution tree below the given partial solution tex2html_wrap_inline67325.

In general, during the traversal of the solution space we may have already found a complete, feasible solution for which the objective function is less than tex2html_wrap_inline67337. In that case, there is no point in considering any of the solutions below tex2html_wrap_inline67325. That is, we can prune the subtree rooted at node tex2html_wrap_inline67325 from the solution tree. A backtracking algorithm that prunes the search space in this manner is called a branch-and-bound  algorithm.




next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.