Lecture
on
Integer Programming
By
Dr. D. B. Naik (Ph.D. - Mech. Engg.)
Professor, Training & Placement
Sardar Vallabhbhai National Institute
of Technology, Surat
Integer Programming
(An Optimization Technique)
A.
All Integer Programming
B.
Mixed Integer Programming
C.
0-1 Integer Programming
(A) All Integer Programming Problem
n
Optimize ([Link] Min.)Z c j x j (1)
j 1
a
j 1
ij
x j (, , )bi ; i 1,2...m (2)
x j 0 & Integers j 1,2...n (3)
Methods to solve
All Integer Programming Problem
1. Branch & Bound Method
2.
Gomorys Cutting Plane Method
1.
Branch & Bound Method
Prob. - 1 Min Z = 4x1 + 3x2
Subjected to :
3x1 + 2x2 20
x1 4
x2 2
x1 , x2 0 & Integers
x2
x1 5
10
P1
P1 (5.33, 2, 27.32)
x1 6
P2
P3
8
6
4
P1 (5.33, 2, 27.32)
Z = 12
10
x1
x2
x1 5
10
P1
P1 (5.33, 2, 27.32)
x1 6
P2
P3
8
6
4
P1 (5.33, 2, 27.32)
Z = 12
10
x1
x2
x1 5
10
P2
P1
P1 (5.33, 2, 27.32)
x1 6
(5, 2.5, 27.5)
P3
8
6
4
P2 (5, 2.5, 27.5)
2
Z = 12
10
x1
x2
x1 5
10
P1
P1 (5.33, 2, 27.32)
x1 6
P2
P3
8
6
4
P1 (5.33, 2, 27.32)
Z = 12
10
x1
x2
x1 5
10
P2
P1
P1 (5.33, 2, 27.32)
x1 6
P3
(5, 2.5, 27.5)
6, 2, 30
6
4
P3 6, 2, 30
2
Z = 12
10
x1
x1 5
P2
x2 2
P1
P1 (5.33, 2, 27.32)
x1 6
P3
(5, 2.5, 27.5)
x2 3
6, 2, 30
P4
P5
x2
x1 5
10
P2
P1
P1 (5.33, 2, 27.32)
x1 6
(5, 2.5, 27.5)
P3
6, 2, 30
6
4
P2 (5, 2.5, 27.5)
P4 Infeasible
Z = 12
10
x1
x2
x1 5
10
P2
P1
P1 (5.33, 2, 27.32)
x1 6
(5, 2.5, 27.5)
P3
6, 2, 30
6
4
P2 (5, 2.5, 27.5)
2
Z = 12
10
x1
x2
x1 5
10
P2
P1
P1 (5.33, 2, 27.32)
x1 6
(5, 2.5, 27.5)
P3
6, 2, 30
6
4
P5 (4.66, 3, 27.66)
2
Z = 12
10
x1
P1
x1 5
x2 2
P4 Infeasible
P2
P1 (5.33, 2, 27.32)
(5, 2.5, 27.5)
x2 3
x1 6
P3
6, 2, 30
P5 (4.66, 3, 27.66) P5
x1 4
P6
x1 5
P7
x2
x1 5
10
P2
P1
P1 (5.33, 2, 27.32)
x1 6
(5, 2.5, 27.5)
P3
6, 2, 30
6
4
P5 (4.66, 3, 27.66)
2
Z = 12
10
x1
x2
x1 5
10
P1
P1 (5.33, 2, 27.32)
x1 6
P2 (5, 2.5, 27.5)
P3
6, 2, 30
8
P4 Infeasible
x1 4
6
4
P5 (4.66, 3, 27.66)
x1 5
P6
P7
P5 (4.66, 3, 27.66)
2
Z = 12
10
x1
x2
P1
x1 5
10
P1 (5.33, 2, 27.32)
x1 6
P2 (5, 2.5, 27.5)
P3
6, 2, 30
8
P4 Infeasible
x1 4
6
4
P6
P6 4, 4, 28
P5 (4.66, 3, 27.66)
x1 5
4, 4, 28
P7
2
Z = 12
10
x1
x2
x1 5
10
P2
P1
P1 (5.33, 2, 27.32)
x1 6
(5, 2.5, 27.5)
P3
6, 2, 30
6
4
P5 (4.66, 3, 27.66)
2
Z = 12
10
x1
x2
P1
x1 5
10
P1 (5.33, 2, 27.32)
x1 6
P2 (5, 2.5, 27.5)
P3
6, 2, 30
8
P4 Infeasible
x1 4
P6
P5 (4.66, 3, 27.66)
x1 5
4, 4, 28
P7
2
Z = 12
10
x1
x2
P1
x1 5
10
P1 (5.33, 2, 27.32)
x1 6
P2 (5, 2.5, 27.5)
P3
6, 2, 30
8
P4 Infeasible
x1 4
P6
P5 (4.66, 3, 27.66)
x1 5
4, 4, 28
P7
5, 3, 29
P7 5, 3, 29
2
Z = 12
10
x1
P1
x1 5
x2 2
P2
P1 (5.33, 2, 27.32)
x1 6
P3
(5, 2.5, 27.5)
x2 3
P4 Infeasible
6, 2, 30
P5 (4.66, 3, 27.66) P5
x1 4
P6 4, 4, 28
Opt. soln.
P6
x1 5
P7 5, 3, 29
P7
Prob. - 2
Min Z = x1 + 3x2 S/t 2x1 3x2 4 ; x1 2x2 8 ;
2x1 + x2 8 ; x1 , x2 0 and integers
x1 3
(3, 2, 9) P2
Optimal
Infeasible
P1 (3.5, 1, 6.5)
x1 4
x1 1
P6
P3
(4, 1.33, 8)
x1 2
P7
(4, 2, 10)
Optimal Solution is :
(1) x1 = 3, x2 = 2, z = 9
Prob. - 3
Max Z = 12x1 + 15x2
S/t
2x1 + 5x2 10
; 4x1 + 3x2 12
x1 , x2 0 and integers
P1 (2.14, 1.14, 42.85)
x1 3
x1 2
(2, 1.2, 42)
x2 1
(2, 1, 39)
P2
P4
Optimal Solution is :
(1) x1 = 2, x2 = 1, z = 39
x2 2
P5
P3
(0, 2, 30)
(3, 0, 36)
Prob. - 4
Min Z = x1 + 4x2
2x1 + x2 8
S/t
; x1 + 2x2 6
x1 , x2 0 and integers
P1 (3.33, 1.33, 8.66)
x1 4
x1 3
(3, 1.5, 9)
x2 1
Infeasible
P2
P4
Optimal Solution is :
(1) x1 = 2, x2 = 2, z = 10
x2 2
P5
P3
(2, 2, 10)
Infeasible
Assignments for Branch & Bound Method :
(1) Max Z = x1 + 2x2
S/t 7x1 + 6x2 42 ; x2 4.5 ; x1 , x2 0 & integers
(2) Max Z = 3x1 + 4x2
S/t 3x1 + 2x2 8 ; x1 + 4x2 10 ; x1,x2 0 & integers
(3) Max Z = 3x1 + 5x2
S/t x1 + 4x2 9 ; 2 x1 + x2 11, x1, x2 0 & integers
(4) Min Z = x1 + 4x2
S/t 2x1 + x2 8 ; x1 + 2x2 6
x1,x2 0 & integers.
2. Gomorys Cutting Plane Method
Max Z = 3x1 + 5x2
Subjected to :
x1 + 4x2 9
2x1 + 3x2 11
x1 , x2 0 & Integers
Final Tableau
ci
xi
3
x1
5
x2
0
w1
0
w2
x2
2/5 -1/5
x1
-3/5 4/5
7/5
17/5
1/5 7/5
86/5
RHS
1 x2 + (2/5) w1 + (-1/5) w2 = 7/5
1 x1 + (-3/5) w1 + (4/5) w2 = 17/5
In general : xi (aij ) x j Ri
1 x2 + (2/5) w1 + (-1/5) w2 = 7/5
In general : xi (aij ) x j Ri
aij = Iij + fij
Ri = IRi + fRi
2.3 = 2 + 0.3
0.7 = 0 + 0.7
-0.4 = -1 + 0.6
-1.3 = -2 + 0.7
where 0 < fij < 1
where 0 < fRi < 1
xi (aij ) x j Ri
xi Ri (aij ) x j
xi ( I Ri f Ri ) ( Iij fij ) x j
xi I Ri f Ri Iij
[ xi I Ri Iij
x j fij x j
x j ] f Ri fij x j
[ Integer] f R fij x j
i
f R fij x j 0
i
0 f Ri 1
f Ri fij x j 0
0 f Ri 1
f Ri fij x j
f
f
ij
ij
xj
f Ri
x j f Ri
This is called as Gomorys constraint.
fij
x j w f Ri
Now 1 x2 + (2/5) w1 + (-1/5) w2 = 7/5
As
fij
x j w f Ri
Gomorys constraint will be :
[(2/5) w1 + (4/5) w2] + w3 = (2/5)
ci
xi
3
x1
5
x2
x2
x1
w3
0
w1
0
w2
0
w3
RHS
2/5 -1/5
-3/5 4/5
-2/5 -4/5
7/5
17/5
-2/5
1/5
86/5
7/5
(-1/2) (-7/4)
3
x1
5
x2
0
w1
0
w2
0
w3
ci
xi
x2
x1
1
4
w1
1
0
Hence Optimal Solution is
x1 = 4, x2 = 1, z = 17
1/2
RHS
17
To get Gomorys constraint in terms of
decision variables :
Gomorys constraint is :
fij
x j f Ri
Hence, [(2/5) w1 + (4/5) w2] (2/5)
(2/5) w1 (4/5) w2 (2/5)
Placing w1 & w2 with respect to
original constraints in terms of decision
variables :
(2/5) w1 (4/5) w2 (2/5)
(2/5) [ 9 x1 4x2 ] (4/5) [ 11 2x1 3x2 ] (2/5)
(2/5) * 9 + (2/5)x1 + (8/5)x2 (4/5) * 11 + (8/5)x1 + (12/5)x2 (2/5)
2x1 + 4x2 (2/5) + (18/5) + (44/5)
2x1 + 4x2 (60/5) = 12
x1 + 2x2 = 6
Assignments for Cutting Plane Method:
(1) Max Z = x1 + 2x2
S/t 7x1 + 6x2 42 ; x2 4.5 ; x1 , x2 0 & integers
(2) Max Z = 3x1 + 4x2
S/t 3x1 + 2x2 8 ; x1 + 4x2 10 ; x1,x2 0 & integers
(3) Max Z = 3x1 + 5x2
S/t x1 + 4x2 9 ; 2 x1 + x2 11, x1, x2 0 & integers
(4) Max Z = x1 + 3x2
S/t 2x1 - 3x2 4 ; -x1 + 2x2 7 ; 3x1 + x2 9 ;
x1,x2 0 & integers.
Thank you
For any Query or suggestion :
Contact :
Dr. D. B. Naik
Professor, Training & Placement
Sardar Vallabhbhai National Institute
of Technology, Surat
Ichchhanath, Surat 395 007
Email : dbnaik_svr@[Link]
Phone No. 0261-2255225 (O)
