Integer Programming Problem (IPP)
A LPP in which all or some of the decision variable are constrained to assume non-negative integer
value is called IPP.
Maximize 𝑍 = 3𝑥1 + 4𝑥2
Subject to, 7𝑥1 + 16𝑥2 ≤ 52
3𝑥1 − 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0 𝑎𝑛𝑑 𝑥1 , 𝑥2 𝑎𝑟𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠.
Types of IPP
(i) Pure IPP
Maximize 𝑍 = 3𝑥1 + 4𝑥2
Subject to, 7𝑥1 + 16𝑥2 ≤ 52
3𝑥1 − 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0 𝑎𝑛𝑑 𝑥1 , 𝑥2 𝑎𝑟𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠.
(ii) Mixed IPP
Maximize 𝑍 = 3𝑥1 + 4𝑥2
Subject to, 7𝑥1 + 16𝑥2 ≤ 52
3𝑥1 − 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0 𝑎𝑛𝑑 𝑥2 𝑖𝑠 𝑖𝑛𝑡𝑒𝑔𝑒𝑟.
(iii) Zero-One IPP
Maximize 𝑍 = 3𝑥1 + 4𝑥2
Subject to, 7𝑥1 + 16𝑥2 ≤ 52
3𝑥1 − 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0 𝑎𝑛𝑑 𝑥1 , 𝑥2 𝜖 0,1.
Method of IPP
There are two method use to solve IPP
(i) Gomory cutting plane method
(ii) Branch and Bound method
Integer Programming Problem (IPP) Example
Page 1 of 12
Q. Find the optimum integer solution to the following LPP
Maximize 𝑍 = 𝑥1 + 𝑥2
Subject to, 3𝑥1 + 2𝑥2 ≤ 5
𝑥2 ≤ 2
𝑥1 , 𝑥2 ≥ 0 𝑎𝑛𝑑 𝑥1 , 𝑥2 𝑎𝑟𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠.
Solution:
By introducing slack variable 𝑆1 , 𝑆2
The standard form of LPP becomes,
Maximize 𝑍 = 𝑥1 + 𝑥2 + 0. 𝑆1 + 0. 𝑆2
Subject to, 3𝑥1 + 2𝑥2 + 𝑆1 = 5
𝑥2 + 𝑆2 = 2
The initial basic feasible solution is given by, 𝑆1 = 5, 𝑆2 = 2
Initial Simplex table,
𝐶𝑗 1 1 0 0 Min Ratio
𝑋𝐵
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑆1 𝑆2 , 𝑥1 (𝑘𝑒𝑦 𝑐𝑜𝑙𝑢𝑚) >
𝑥1
0
0 𝑆1 5 3 2 1 0 5
3
0 𝑆2 2 0 1 0 1 -
𝑍𝑗 − 𝐶𝑗 -1 -1 0 0
𝑍𝑗 − 𝐶𝑗 = 𝐶𝐵 𝑋𝑗 − 𝐶𝑗
2nd Simplex Table
𝐶𝑗 1 1 0 0 Min Ratio
𝑋𝐵
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑆1 𝑆2 , 𝑥2 (𝑘𝑒𝑦 𝑐𝑜𝑙𝑢𝑚) >
𝑥 2
0
1 𝑥1 5 1 2 1 0 5
3 3 3 3 = 2.5
2
3
0 𝑆2 2* 0 1** 0 1 2
=2
1
𝑍𝑗 − 𝐶𝑗 0 1 1 0
−
3 3
Page 2 of 12
*=
1st
nd
2 5 3
2 0
Therefore,
2×3−5×0 6
2∗= = =2
3 3
Similarly
1×3−2×0 3
1 ∗∗ = = =1
3 3
3rd Simplex Table
𝐶𝑗 1 1 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑆1 𝑆2
1 𝑥1 1 1 0 1 2
−
3 3 3
1 𝑥2 2 0 1 0 1
𝑍𝑗 − 𝐶𝑗 0 0 1 1
3 3
Since all
𝑍𝑗 − 𝐶𝑗 ≥ 0
So, optimal solution is obtained, given by
1
𝑥1 = 𝑎𝑛𝑑 𝑥2 = 2
3
To obtain an optimum integer solution, we have to add Gomorian constraints.
1
𝑥1 = 𝑎𝑛𝑑 𝑥2 = 2
3
1 1
𝑀𝑎𝑥 ( , 0 ) =
3 3
Page 3 of 12
2
Since 𝑥1 is the source row, expressing the negative fraction (− 3) as a sum of negative integer and
positive fraction.
2 1
− = −1 +
3 3
Since 𝑥1 is the source row, we have
1 1 2
= 𝑥1 + 𝑆1 − 𝑆2
3 3 3
1 1 𝑆2
⇒ = 𝑥1 + 𝑆1 − 𝑆2 +
3 3 3
The fractional cut constraints is given by,
𝑆1 𝑆2 1
+ ≥
3 3 3
𝑆1 𝑆2 1
⇒− − ≤−
3 3 3
𝑆1 𝑆2 1
⇒− − + 𝐺1 = −
3 3 3
Where 𝐺1 is Gomory slack.
Adding this above constraints at the bottom of optimum simplex table.
𝐶𝑗 1 1 0 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝐺1
1 𝑥1 1 1 0 1 2 0
−
3 3 3
1 𝑥2 2 0 1 0 1 0
0 𝐺1 1 0 0 1 1 1
− − −
3 3 3
𝑍𝑗 − 𝐶𝑗 0 0 1 1 0
3 3
𝑍𝑗 − 𝐶𝑗 = 𝐶𝐵 𝑋𝑗 − 𝐶𝑗
We apply dual simplex method.
𝑍𝑗 − 𝐶𝑗
Max Ratio ( ; 𝐺1 < 0)
𝐺1
Max Ratio (−, −, −1, −1, −)
We choose 𝑆1 as entering variable,
Page 4 of 12
𝐶𝑗 1 1 0 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝐺1
1 𝑥1 0 1 0 0 2 1
−
3
1 𝑥2 2 0 1 0 1 0
0 𝑆1 1 0 0 1 1 -3
𝑍𝑗 − 𝐶𝑗 0 0 0 0 1
Since all
𝑍𝑗 − 𝐶𝑗 ≥ 0
And
𝑋𝐵 ≥ 0
Also all restricted variable 𝑥1 𝑎𝑛𝑑 𝑥2 are integers.
Hence an optimum integer solution is obtained.
So, optimal solution is obtained, given by
𝑥1 = 0 𝑎𝑛𝑑 𝑥2 = 2
Max Z = 2
(Answer)
Gomory’s Fractional Cut Algorithm
Step1: Convert minimization IPP into equivalent maximization IPP ignore the integrality
conditions.
Step2: Introduce slack and/or surplus variables if necessary to convert the given LPP in its standard
from and obtain the optimal solution of the given LPP using simplex method.
Step3: Test the integrality of the optimum solution
(i) if all 𝑥𝐵𝑖 ≥ 0 and are integer, an optimum integer solution is obtained.
(ii) if all 𝑥𝐵𝑖 ≥ 0 and at least one 𝑥𝐵𝑖 is not integer, then go to the next step.
Step 4: Rewrite each 𝑥𝐵𝑖 as 𝑥𝐵𝑖 = [𝑥𝐵𝑖 ] + 𝑓𝑖 where 𝑥𝐵𝑖 is the integral part of 𝑥𝐵𝑖 and 𝑓𝑖 is the
positive fractional part of 𝑥𝐵𝑖 , choose the largest fractional of 𝑥𝐵𝑖 . If there is a tie, select arbitrarily.
Let max( 𝑓𝑖 ) = 𝑓𝑘 , corresponding to 𝑥𝐵𝑘 (the kth row is called the ‘source row’)
Page 5 of 12
Step 5: Express each negative fraction, if any, in the source row of the optimum simplex table as
the sum of a negative integers and a non-negative fraction.
Step6: Find the fractional cut constraint (Gomorian constraint)
From the source row
𝑛
∑ 𝑎𝑘𝑗 𝑥𝑗 = 𝑥𝐵𝑖
𝑗=1
𝑛
𝑖. 𝑒. ∑ ([𝑎𝑘𝑗 ] + 𝑓𝑘𝑗 ) 𝑥𝑗 = [𝑥𝐵𝑘 ] + 𝑓𝑘
𝑗=1
𝑛 𝑛
𝑖𝑛 𝑡ℎ𝑒 𝑓𝑜𝑟𝑚 ∑ 𝑓𝑘𝑗 . 𝑥𝑗 ≥ 𝑓𝑘 − ∑ 𝑥𝑘𝑗 . 𝑥𝑗 ≤ −𝑓𝑘
𝑗=1 𝑗=1
𝑛
𝑜𝑟, ∑ 𝑓𝑘𝑗 . 𝑥𝑗 + 𝐺1 = −𝑓𝑘
𝑗=1
Where 𝐺1 is the Gomorian slack.
Step7: add the fractional cut constraint obtained in step (6) at the bottom of the simplex table
obtained in step (2). Find new feasible optimum solution using dual simplex method.
Step8: Go to step (3) and repeat the procedure until an optimum integer solution is obtained.
Gomory’s Cutting Plane Method
Q. Find the optimum integer solution to the following LPP
Maximize 𝑍 = 4𝑥1 + 6𝑥2 + 2𝑥3
Subject to, 4𝑥1 − 4𝑥2 ≤ 5
−𝑥1 + 6𝑥2 ≤ 5
−𝑥1 + 𝑥2 + 𝑥3 ≤ 5
𝑥1 , 𝑥2 , 𝑥3 ≥ 0 𝑎𝑛𝑑 𝑥1 , 𝑥3 𝑎𝑟𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠.
Solution:
Introducing slack variables 𝑆1 , 𝑆2 , 𝑆3 the standard form of LPP is,
Maximize 𝑍 = 4𝑥1 + 6𝑥2 + 2𝑥3 +0𝑆1 + 0𝑆2 + 0𝑆3
Subject to, 4𝑥1 − 4𝑥2 + 𝑆1 = 5
−𝑥1 + 6𝑥2 + 𝑆2 = 5
−𝑥1 + 𝑥2 + 𝑥3 + 𝑆3 = 5
𝑥1 , 𝑥2 , 𝑥3 , 𝑆1 , 𝑆2 , 𝑆3 ≥ 0
Page 6 of 12
Initial basic feasible solution by,
𝑆1 = 5, 𝑆2 = 5, 𝑆3 = 5
Ignoring the integer condition, and solving the problem using simplex method to obtain optimum
solution.
Initial Simplex table
𝐶𝑗 4 6 2 0 0 0 Min Ratio
𝑋𝐵
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 , 𝑥2 (𝑘𝑒𝑦 𝑐𝑜𝑙𝑢𝑚) >
𝑥2
0
0 𝑆1 5 4 -4 0 1 0 0 -
5
0 𝑆2 5 -1 6 0 0 1 0 =0.833
6
0 𝑆3 5 -1 1 1 0 0 1 5
=5
1
𝑍𝑗 − 𝐶𝑗 -4 -6 -2 0 0 0
𝑍𝑗 − 𝐶𝑗 = (𝐶𝐵 𝑋𝑗 ) − 𝐶𝑗
2nd Simplex Table
𝐶𝑗 4 6 2 0 0 0 Min Ratio
𝑋𝐵
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 , 𝑥1 (𝑘𝑒𝑦 𝑐𝑜𝑙𝑢𝑚) >
𝑥1
0
0 𝑆1 25 10 0 0 1 2 0 5
3 3 3 2
6 𝑥2 5 1 1 0 0 1 0 −
−
6 6 6
0 𝑆3 25 5 0 1 0 1 1 −
− −
6 6 6
𝑍𝑗 − 𝐶𝑗 -5 0 -2 0 1 0
𝑍𝑗 − 𝐶𝑗 = (𝐶𝐵 𝑋𝑗 ) − 𝐶𝑗
Page 7 of 12
3rd Simplex Table
𝐶𝑗 4 6 2 0 0 0 Min Ratio
𝑋𝐵
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 , 𝑥1 (𝑘𝑒𝑦 𝑐𝑜𝑙𝑢𝑚) >
𝑥1
0
4 𝑥1 5 1 0 0 3 1 0 −
2 10 5
6 𝑥2 5 0 1 0 1 1 0 −
4 20 5
0 𝑆3 25 0 0 1 1 0 1 125
4 4 6
𝑍𝑗 − 𝐶𝑗 0 0 -2 3 2 0
2
𝑍𝑗 − 𝐶𝑗 = (𝐶𝐵 𝑋𝑗 ) − 𝐶𝑗
4th Simplex Table
𝐶𝑗 4 6 2 0 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3
4 𝑥1 5 1 0 0 3 1 0
2 10 5
6 𝑥2 5 0 1 0 1 1 0
4 20 5
2 𝑥3 25 0 0 1 1 0 1
4 4
𝑍𝑗 − 𝐶𝑗 0 0 0 2 2 2
Since all
𝑍𝑗 − 𝐶𝑗 ≥ 0
So, solution is optimum but the integer constrained variables 𝑥1 𝑎𝑛𝑑 𝑥3 are non-integer.
Now,
5 1
𝑥1 = = 2+
2 2
𝑎𝑛𝑑
25 1
𝑥3 = =6+
4 4
1 1 1
𝑀𝑎𝑥𝑖𝑚𝑢𝑚 ( , )=
2 4 2
Page 8 of 12
The source row is first row.
We have,
5 3 1
= 𝑥1 + 𝑆1 + 𝑆2
2 10 5
1 3 1
⟹ 2+ = 𝑥1 + 𝑆1 + 𝑆2
2 10 5
The fractional cut (Gomorian) Constraint is given by
3 1 1
𝑆1 + 𝑆2 ≥
10 5 2
3 1 1
⟹− 𝑆1 − 𝑆2 ≤ −
10 5 2
3 1 1
⟹− 𝑆1 − 𝑆2 + 𝐺1 = −
10 5 2
Where 𝐺1 is Gomorian slack. Now introducing this new constraint at the bottom of the above
simplex table.
𝐶𝑗 4 6 2 0 0 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 𝐺1
4 𝑥1 5 1 0 0 3 1 0
2 10 5
6 𝑥2 5 0 1 0 1 1 0
4 20 5
2 𝑥3 25 0 0 1 1 0 1
4 4
0 𝐺1 1 0 0 0 3 1 0 1
− − −
2 10 5
𝑍𝑗 − 𝐶𝑗 0 0 0 2 2 2 0
𝑍𝑗 − 𝐶𝑗 = (𝐶𝐵 𝑋𝑗 ) − 𝐶𝑗
Solving the above table using dual simplex method to obtain integer optimum solution.
We apply dual simplex method.
𝑍𝑗 − 𝐶𝑗
Max Ratio ( ; 𝐺1 < 0)
𝐺1
Page 9 of 12
2 2 20 20
Max Ratio (−, −, −, , , −, −) = Max Ratio (− , −10) = −
3 1 3 3
− 10 −
5
Which corresponds to 𝑆1 , so we choose 𝑆1 as entering variable,
𝐶𝑗 4 6 2 0 0 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 𝐺1
4 𝑥1 2 1 0 0 0 0 0 1
6 𝑥2 7 0 1 0 0 1 0 1
6 6 6
2 𝑥3 35 0 0 1 0 1 1 5
−
6 6 6
0 𝑆1 5 0 0 0 1 2 0 10
−
3 3 3
𝑍𝑗 − 𝐶𝑗 0 0 0 0 2 2 20
3 3
𝑍𝑗 − 𝐶𝑗 = (𝐶𝐵 𝑋𝑗 ) − 𝐶𝑗
Since all
𝑍𝑗 − 𝐶𝑗 ≥ 0 𝑎𝑛𝑑 𝑎𝑙𝑙 𝑋𝐵 ≥ 0
35
But 𝑥3 = is non-integer. Therefore, we add another Gomorian Constraint.
6
Now,
𝑥1 = 2
𝑎𝑛𝑑
35 5
𝑥3 = =5+
6 6
5 5
𝑀𝑎𝑥𝑖𝑚𝑢𝑚 ( 0, ) =
6 6
The source row is third row.
We have,
35 1 5
= 𝑥3 + (− ) 𝑆2 + 𝑆3 + 𝐺1
6 6 6
1
Expressing the negative fraction (− 6) as a sum of negative integer and positive fraction.
Page 10 of 12
1 5
− = −1 +
6 6
35 5 5
= 𝑥3 − 𝑆2 + 𝑆2 + 𝑆3 + 𝐺1
6 6 6
5 5 5
⟹ 5+ = 𝑥3 − 𝑆2 + 𝑆2 + 𝑆3 + 𝐺1
6 6 6
The fractional cut (Gomorian) Constraint is given by
5 5 5
𝑆2 + 𝐺1 ≥
6 6 6
5 5 5
⟹ − 𝑆2 − 𝐺1 ≤ −
6 6 6
5 5 5
⟹ − 𝑆2 − 𝐺1 + 𝐺2 = −
6 6 6
Where 𝐺2 is Gomorian slack. Now introducing this new constraint at the bottom of the above table.
𝐶𝑗 4 6 2 0 0 0 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 𝐺1 𝐺2
4 𝑥1 2 1 0 0 0 0 0 1 0
6 𝑥2 7 0 1 0 0 1 0 1 0
6 6 6
2 𝑥3 35 0 0 1 0 1 1 5 0
−
6 6 6
0 𝑆1 5 0 0 0 1 2 0 10 0
−
3 3 3
0 𝐺2 5 0 0 0 0 5 0 5 1
− − −
6 6 6
𝑍𝑗 − 𝐶𝑗 0 0 0 0 2 2 20 0
3 3
Solving the above table using dual simplex method to obtain integer optimum solution.
We apply dual simplex method.
𝑍𝑗 − 𝐶𝑗
Max Ratio ( ; 𝐺2 < 0)
𝐺2
Page 11 of 12
2 20
3 4 4
Max Ratio (−, −, −, , −, 3 , −) = Max Ratio (− , −8) = −
5 5 5 5
−6 −6
Which corresponds to 𝑆2 , so we choose 𝑆2 as entering variable,
𝐶𝑗 4 6 2 0 0 0 0 0
𝐶𝐵 B 𝑋𝐵 𝑥1 𝑥2 𝑥3 𝑆1 𝑆2 𝑆3 𝐺1 𝐺2
4 𝑥1 2 1 0 0 0 0 0 1 0
6 𝑥2 1 0 1 0 0 0 0 0 1
5
2 𝑥3 6 0 0 1 0 0 1 1 1
−
5
0 𝑆1 1 0 0 0 1 0 0 -4 4
5
0 𝑆2 1 0 0 0 0 1 0 1 6
−
5
𝑍𝑗 − 𝐶𝑗 0 0 0 0 0 2 6 4
5
Since all
𝑍𝑗 − 𝐶𝑗 ≥ 0 𝑎𝑛𝑑 𝑎𝑙𝑙 𝑋𝐵 ≥ 0
And restricted variables 𝑥1 𝑎𝑛𝑑 𝑥3 are integer.
Hence an optimum integer solution is obtained, the optimum integer solution is
𝑥1 = 2
𝑥2 = 1 𝑎𝑛𝑑
𝑥3 = 6
𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑍 = 26
Page 12 of 12