# Branch and Bound Method: Integer Programming

The branch and 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 in Branch and Bound Method (Algorithm)

Step 1: First, solve the given problem as an ordinary LPP.

Step 2: Examine the optimal solution. Terminate the iterations if the optimal solution to the LPP satisfies the integer constraints. Otherwise, go to step 3.

Step 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

Step 4: Now, solve problem 1 & 2 separately.

Step 5: If for any of the sub-problems, optimal integer solution is obtained, then that problem is not further branched. Otherwise, move to step.

Share and Recommend