Branch and bound (BB)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

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.

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 $x$k with fractional value $v$
Create node jnew with bound $x$k $\le$ $\llcorner$ $v$ $\lrcorner$
UBjnew:=obj
Store node jnew in waiting node list
Create node jnew with bound $x$k $\ge$ $\ulcorner$ $v$ $\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:

A Numerical Example

The original mixed integer linear programming problem is as follows:

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

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

and the solution to the relaxed problem is as follows:

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

In this way, the branch tree is as follows:

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.