Integer Linear programming problem
(P) Max./ Min. c1x1 c2 x2 cn xn
subject to
a11x1 a12 x2 ... a1n xn , ,= b1
a21x1 a22 x2 ... a2n xn , ,= b2
a31x1 a32 x2 ... a3n xn , ,= b3 (1)
am1x1 am2 x2 ... amn xn , ,= bm
x1, x2 ,.., xn 0 and integers
Two methods:
Cutting plane method
Branch and bound method.
Cutting plane method:
Simplex method
Gomory’s constraint
Dual simplex method
P1: Solve the following integer LP problem
Minimize Z= 2x1+3x2
subject
x1+x2 ≥6 ; 7x1+x2 ≥ 14 ;
x1, x2 ≥ 0 and integers.
Soln: Consider the following LP problem
Minimize Z= 2x1+3x2
subject
x1+x2 ≥6 ; 7x1+x2 ≥ 14; x1, x2 ≥ 0.
Now, consider the following maximize type LP problem for the given minimize type LP
problem:
Maximize P = -2x1-3x2
subject
x1+x2 ≥6 ; 7x1+x2 ≥ 14 ; x1, x2 ≥ 0.
This implies that
Maximize P = -2x1-3x2
subject
-x1-x2 ≤ -6 ; -7x1-x2 ≤ -14;
x1, x2 ≥ 0.
Now, the standard form:
Maximize P = -2x1-3x2
subject
-x1-x2 +x3 = -6 ;
-7x1-x2 +x4 = -14;
x1, x2 , x3, x4 ≥ 0
where x3 and x4 are slack variables.
Now, the initial basic solution:
x3 = -6 and x4= -14.
Initial table:
C -2 -3 0 0
CBV BV x1 x2 x3 x4 Soln Ratio
0 x3 -1 -1 1 0 -6 6
0 x4 -7 -1 0 1 -14 2
Zj-Cj 2 3 0 0 0
Ratio -2/7 -3 - -
Min.{ -14,-6} = -14. Max.{ -2/7, -3}= -2/7
Entering variable-x1 and leaving variable-x4
First iteration table:
C -2 -3 0 0
CBV BV x1 x2 x3 x4 Soln Ratio
0 x3 0 -6/7 1 -1/7 -4 28
-2 x1 1 1/7 0 -1/7 2
Zj-Cj 0 19/7 0 2/7
Ratio -19/6 -2
Entering variable-x4 and leaving variable-x3
Second iteration table
C -2 -3 0 0
CBV BV x1 x2 x3 x4 Soln Ratio
0 x4 0 -6 -7 1 28
-2 x1 1 1 -1 0 6
Zj-Cj 0 1 2 0 -12
Ratio
Solution to the LP problem:
x1=6 , x2=0 and Min.Z= - Max.P= 12.
Since the values of x1 and x2 are integers, the optimal solution to the given
integer LP problem is x1=6 , x2=0 and Min.Z= 12.
P2: Using cutting plane method, solve the following integer L P problem
Maximize Z= 5x1+8x2
subject to
x1+2x2≤ 8 ; 4x1+x2≤ 10, x1 , x2 ≥ 0 and integers.
Soln:
The LP problem corresponding to the given Integer LP problem.
Maximize Z= 5x1+8x2
subject to
x1+2x2≤ 8 ; 4x1+x2≤ 10, x1 , x2 ≥ 0 .
The Std. form of the LP problem corresponding to the given Integer LP problem.
Maximize Z= 5x1+8x2+0x3+0x4
subject to
x1+2x2 +x3 = 8 ;
4x1+x2+ x4 = 10,
x1 , x2, x3, x4 ≥ 0 .
where x3 and x4 are slack variables.
Now, the initial basic feasible solution:
x3= 8 and x4 =10 .
Initial table
C 5 8 0 0
CBV BV x1 x2 x3 x4 Soln Ratio
0 x3 1 2 1 0 8 8/2=4
0 x4 4 1 0 1 10 10/1=10
Zj-Cj -5 -8 0 0 0
Entering variable – x2 and Leaving variable –x3.
First iteration table
C 5 8 0 0
CBV BV x1 x2 x3 x4 Soln Ratio
8 x2 1/2 1 1/2 0 4 8
0 x4 7/2 0 -1/2 1 6 12/7
Zj-Cj -1 0 4 0 32
Entering variable – x1 and Leaving variable –x4
Second iteration table
C 5 8 0 0
CBV BV x1 x2 x3 x4 Soln Ratio
8 x2 0 1 4/7 -1/7 22/7
5 x1 1 0 -1/7 2/7 12/7
Zj-Cj 0 0 27/7 2/7 236/7
Since Zj-Cj ≥ 0, for all j, the current table is optimal. We stop the process.
Optimal solution soln:
x1=12/7 , x2=22/7 and Max. Z= 236/7.
Since x1 and x2 are not integer, it is not optimal solution to the given problem.
Now, x1 = 1+5/7
x2 = 3+1/7
Since fractional part of x1 is high, select x1.
Now, we have
x1+0x2+(-1/7)x3+(2/7)x4=12/7
x1+0x2+(-1+6/7)x3+(2/7)x4=1+5/7
Gomory’s constraint:
(6/7)x3+(2/7)x4 ≥ 5/7
That is, -(6/7)x3-(2/7)x4 ≤ -5/7
This implies that
-(6/7)x3-(2/7)x4 +x5 = -5/7
where x5 is a slack variable.
Adding the Gomory’s constraint to the optimal table
Initial table (DSM) for integer soln:
C 5 8 0 0 0
CBV BV x1 x2 x3 x4 x5 Soln
8 x2 0 1 4/7 -1/7 0 22/7
5 x1 1 0 -1/7 2/7 0 12/7
0 x5 0 0 -6/7 -2/7 1 -5/7 x
Zj-Cj 0 0 27/7 2/7 0 236/7
Ratio - - -27/6 -1 -
Entering variable-x4 and Leaving variable x5
First iteration table for integer soln:
C 5 8 0 0 0
CBV BV x1 x2 x3 x4 x5 Soln
8 x2 0 1 1 0 -1/2 7/2
5 x1 1 0 -1 0 1 1
0 x4 0 0 3 1 -7/2 5/2
Zj-Cj 0 0 3 0 66/2
Since x2 is not integer, it is not optimal solution to the given problem.
Now, x2 = 3+1/2
Now, we have
0x1+x2+x3+0x4+(-1/2)x5=7/2
0x1+x2+x3+ (-1+1/2)x5 =3+1/2
Gomory’s constraint:
(1/2)x5 ≥ 1/2
That is, -(1/2)x5 ≤ -1/2
This implies that
-(1/2)x5 +x6 = -1/2
where x6 is a slack variable.
Adding the Gomory’s constraint to the optimal table :
Second Iteration table (DSM) for integer soln:
C 5 8 0 0 0 0
CBV BV x1 x2 x3 x4 x5 x6 Soln
8 x2 0 1 1 0 -1/2 0 7/2
5 x1 1 0 -1 0 1 0 1
0 x4 0 0 3 1 -7/2 0 5/2
0 x6 0 0 0 0 -1/2 1 -1/2 X
Zj-Cj 0 0 3 0 1 0 66/2
Ratio - - - - -2 -
Entering variable-x5 and Leaving variables-x6
Third iteration table:
C 5 8 0 0 0 0
CBV BV x1 x2 x3 x4 x5 x6 Soln
8 x2 0 1 1 0 0 -1 4
5 x1 1 0 -1 0 0 2 0
0 x4 0 0 3 1 0 -7 6
0 x5 0 0 0 0 1 -2 1
Zj-Cj 0 0 3 0 1 0 32
Since the values of x1 and x2 are integers, this is the optimal solution . We stop the computation.
The optimal solution of the given problem:
x1=0, x2 = 4 and Max.Z=32
