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.