Integer Programming

Branch & Bound Method

The branch & bound method can be used to solve problems containing a few integer valued variables. It can be applied to both mixed & pure integer programming problems. This method partitions the area of feasible solution into smaller parts until an optimal solution is obtained.

If the number of variables is large, or if the LP solution to the problem is not optimal, then don't use the Branch & Bound method, because the number of iterations required to solve such a problem may be too large.

The method, in outline, is:

Steps

1. First, solve the given problem as an ordinary LPP.
2. Examine the optimal solution. Terminate the iterations if the optimal solution to the LPP satisfies the integer constraints. Otherwise, go to step 3.
3. Divide the problem into two parts.
   Problem 1: xk £ [t]
   max. z = cx
   subject to
   ax £ b
   xk £ [t]
   x ³ 0
   
   Problem 2: xk ³ [t] + 1
   max. z = cx
   subject to
   ax £ b
   xk ³ [t] + 1
   x ³ 0
   
   where [t] is the largest integer.

   "Nothing is particularly hard if you divide it into small jobs." -Henry Ford

4. Now, solve problem 1 & 2 separately.
5. If for any of the sub-problems, optimal integer solution is obtained, then that problem is not further branched. Otherwise, move to step 3.