Integer Linear Programming: Branch and Bound Method Operation
Research:
Example:
For Graphical Method:
Max Z=8x1 +5x2
Subject to, 9x1+5x2 ≤ 45
x1+x2 ≤ 6
x1,x2 ≥ 0 and x1,x2 integers.
Solution:
From the given constrains, we can write
For 9x1+5x2 = 45………………(1)
(x1,x2) = (0,9) & (5,0)
For x1+x2 = 6…………………….(2)
(x1,x2) =( 0,6 ) & ( 6,0 )
For point B,
Multiplying (2) by 9 then subtracting from (1)
-4x2 = -9 => x2 = 2.25 and x1 = 3.75
Max Z=8x1 +5x2
For A (0, 6), Z= 30
For B (3.75, 2.25), Z = 41.25
For C (5, 0), Z=40
So, Max Z = 41.25 (For B)
Where x1 = 3.75 and x2 = 2.25 which are not integers.
Now branching this problem:
Here x1 > x2 and x1 = 3.75
So x1 ≤3 and x1 ≥ 4
Sub problem-1
Max Z=8x1 +5x2
Subject to, 9x1+5x2 ≤ 45
x1+x2 ≤ 6
x1 ≤ 3
x1,x2 ≥ 0 and x1,x2 integers.
Sub problem-2
Max Z=8x1 +5x2
Subject to, 9x1+5x2 ≤ 45
x1+x2 ≤ 6
x1 ≥ 4
x1,x2 ≥ 0 and x1,x2 integers.
Graphical Representation of Sub Problems:
Sub Problem-1:
Here, For A, Z= 30
For B, Z= 39
For C, Z= 24
So, Max Z = 39 ( For B)
x1 = 3, & x2 = 3
Those Values are integers.
Sub Problem-2:
Here, For A, B, C
Max Z = 41 (For B)
Where x1 = 4, & x2 = 1.8
x2 is not integer.
Again, x2 ≤ 1 and x2 ≥ 2
Sub Problem-3:
Max Z=8x1 +5x2
Subject to, 9x1+5x2 ≤ 45
x1+x2 ≤ 6
x1 ≥ 4
x2 ≤ 1
Graph for Sub Problem-3
Here, Max Z= 40.5
Where, x1 = 4.44 & x2 = 1 ( x1 is not integer).
Again branching:
Sub Problem-4:
Max Z=8x1 +5x2
Subject to, 9x1+5x2 ≤ 45
x1+x2 ≤ 6
x1 ≥ 4
x2 ≥ 2
Graph for sub Problem-4
There is no common area. So, infeasible solution exists.
For intersecting point ( 4, 0 ).
Max Z = 42
x1 ≤ 4, x1 ≥ 5
Sub Problem-5:
Max Z=8x1 +5x2
Subject to, 9x1+5x2 ≤ 45
x1+x2 ≤ 6
x1 ≥ 4
x2 ≤ 1
x1 ≤ 4
For ( 4,1)
Max Z =37
x1 = 4, & x2 = 1. Those are integers.
Sub Problem-6:
Max Z=8x1 +5x2
Subject to, 9x1+5x2 ≤ 45
x1+x2 ≤ 6
x1 ≥ 4
x2 ≤ 1
x1 ≥ 5
For (5,0) ,
Max Z= 40
x1 = 5, & x2 = 0. There is no Common area.
So the solution is infeasible.
From Sub Problem 1 and 5
Max Z=39
So the solution is optimal. Where, x1 = 3, x2 = 3.
The branch and bound procedure for the given problem is shown in the following figure:
Z= 41.25
x1 = 3.75, x2 = 2.25
x1≤3 x1≥4
Z= 39 Z= 41
x1 = 3, x2 = 3 x1 = 4, x2 = 1.8
x1≤1 x1≥2
Z= 40.5
Infeasible
x1 = 4.44, x2 = 1
x1≤4
x1≥5
Z= 37
Infeasible
x1 = 4, x2 = 1
