Engineering Optimization: Theory and Practice, Fourth Edition

10.6 Branch-and-Bound Method 611

It can be seen that a node can be fathomed if any of the following conditions
are true:

1.The continuous solution is an integer feasible solution.

2.The problem does not have a continuous feasible solution.

3.The optimal value of the continuous problem is larger than the current upper

bound.

The algorithm continues to select a node for further branching until all the nodes have
been fathomed. At that stage, the particular fathomed node that has the integer feasible
solution with the lowest value of the objective function gives the optimum solution of
the original nonlinear integer programming problem.

Example 10.3 Solve the following LP problem using the branch-and-bound method:

Maximizef= 3 x 1 + 4 x 2

subject to (E 1 )

7 x 1 + 11 x 2 ≤ 88 , 3 x 1 −x 2 ≤ 21 , x 1 ≥ 0 , x 2 ≥ 0

xi= ntegeri , i= 1 , 2 (E 2 )

SOLUTION The various steps of the procedure are illustrated using graphical method.

Step 1: First the problem is solved as a continuous variable problem [without Eq.(E 2 )]
to obtain:

Problem(E 1 ) Fig. 10:. 2 ;(x 1 ∗= 5. 5 ,x 2 ∗= 4. 5 ,f∗= 43. 5 )

Step 2: The branching process, with integer bounds onx 1 , yields the problems:

Maximizef= 3 x 1 + 4 x 2

subject to (E 3 )

7 x 1 + 11 x 2 ≤ 88 , 3 x 1 −x 2 ≤ 21 , x 1 ≤ 5 , x 2 ≥ 0

and

Maximizef= 3 x 1 + 4 x 2

subject to (E 4 )

7 x 1 + 11 x 2 ≤ 88 , 3 x 1 −x 2 ≤ 21 , x 1 ≥ 6 , x 2 ≥ 0

The solutions of problems (E 3 ) and (E 4 ) are given by

Problem(E 3 ) Fig. 10:. 4 ;(x 1 ∗= 5 ,x 2 ∗= 4. 8182 , f∗= 43. 2727 )

Problem(E 4 ) Fig. 10:. 5 ; no feasible solution exists.