Branch and bound (BB)

From optimization
Jump to: navigation, search

Authors: Jiyao Gao (ChE 345 Spring 2014)

Steward: Dajun Yue, Fengqi You

Date Presented: Apr. 16, 2014

The Branch and Bound (BB or B&B) algorithm is first proposed by A. H. Land and A. G. Doig in 1960 for discrete programming. It is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. A branch and bound algorithm consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are fathomed, by using upper and lower estimated bounds of the quantity being optimized.

Contents

General Description

Basic Idea

Branch and Bound algorithm, as a method for global optimization for discrete problems, which are usually NP-hard, searches the complete space of solutions for a given problem for the optimal solution. By solving a relaxed problem of the original one, fractional solutions are recognized and for each discrete variable, B&B will do branching and creating two new nodes, thus dividing the solution space into a set of smaller subsets and obtain the relative upper and lower bound for each node. Since explicit enumeration is normally impossible due to the exponentially increasing number of potential solutions, the use of bounds for the function to be optimized combined with the value of the current best solution found enables this B&B algorithm to search only parts of the solution space implicitly.

Illustration.png

Figure 1: Illustration of the search space of B&B

Branching Strategy

According to the work of Gupta and Ravindran, Generally there are two ways to do branching:

  • Branching on the node with the smallest bound

Search all the nodes and find the one with the smallest bound and set it as the next branching node. Advantage: Generally it will inspect less subproblems and thus saves computation time. Disadvantage: Normally it will require more storage.

  • Branching on the newly created node with the smallest bound

Search the newly created nodes and find the one with the smallest bound and set it as the next branching node. Advantage: Saves storage space. Disadvantage: Require more branching computation and thus less computational efficiently.

Detailed Algorithm

The exact algorithm procedure is as below:


 {Initialization}
 LB:=-Inf
 UB:=Inf
 Store root node in waiting node list
   while waiting node list is not empty do
   {Node selection}
   Choose a node from the waiting node list
   Remove it from the waiting node list
   Solve subproblem
   if infeasible then
     Node is fathomed
   else if optimal then
     if integer solution then
       if obj > LB then
         {Better integer solution found}
         LB:=obj
         Remove nodes j from list with UBj < LB
       end if 
       else
         {Variable selection}
         Find variable xk with fractional value v
         Create node jnew with bound xk \le \llcornerv\lrcorner
         UBjnew:=obj
         Store node jnew in waiting node list
         Create node jnew with bound xk \ge \ulcornerv\urcorner
         UB_jnew:=obj
         Store node jnew in waiting node list
       end if
     else
       Stop: problem in solving subproblem
     end if
     UB=maxjUBj
   end while

The flow chart for Branch and Bound algorithm is as below:

BB.png

A Numerical Example

The original mixed integer linear programming problem is as follows:

Original.png

Because this problem is difficult to solve, so we will solve the relaxed problem instead, which is as below:

Relaxed.png

The set of feasible solution is donated as R_0, which is shown below:

R0.png

and the solution to the relaxed problem is as follows:

X.png

Based on this solution, next step we will do branching on x_3, and the resulting new solution subsets is as below:

R.png

In this way, the branch tree is as follows:

Branch.png

Conclusion

It is important to realize that mixed integer linear programs are NP-hard. Roughly speaking, this means that the effort required to solve a mixed integer linear program grows exponentially with the size of the problem. Although it is unlikely that the branch-and-bound algorithm will have to generate every single possible node, the need to explore even a small fraction of the potential number of nodes for a large problem can be resource intensive.

Meanwhile, a number of techniques can speed up the search progress of the branch-and-bound algorithm. Heuristics are used to find feasible solutions, which can improve the upper bounds on solutions of mixed integer linear programs. Cutting planes can reduce the search space and thus improve the lower bounds on solutions of mixed integer linear programs. When using cutting planes, the branch-and-bound algorithm is also called the branch-and-cut algorithm. Preprocessing can reduce problem size and improve problem solvability.

References

1. A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica 28 (3). pp. 497–520. doi:10.2307/1910129.

2. Gupta OK, Ravindran A. Branch and Bound Experiments in Convex Nonlinear Integer Programming. Management Science. 1985;31(12):1533-1546.

3. Moore, R. E. (1966). Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall. ISBN 0-13-476853-1.

4. Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0.

5. Hansen, E.R. (1992). Global Optimization using Interval Analysis. New York: Marcel Dekker.

6. T.F. Edgar, D.M. Himmelblau, L.S. Lasdon, Optimization of chemical processes. McGraw-Hill, 2001

7. Bradley, Hax, and Magnanti (Addison-Wesley, 1977). Applied Mathematical Programming.

8. R.J. Vanderbei, Linear Programming: Foundations and Extensions. Springer, 2008.

9. S. Boyd, L. Vandenberghe, Convex Optimization. Cambridge University Press, 2009

10. J. Nocedal, S. J. Wright, Numerical optimization. Springer, 1999.

11. Wikipedia page for Branch and bound