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.

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.

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.