Integer Programming - MNIT Jaipur - Taha et al

Adopted from Taha and other sources

1. Integer Programming
Adopted from Tahaand other sources

2. Integer programming


3. NoModel Type Decision variables
1Linear Programming (LP) Can take continuous value.
2Integer Linear Programming (ILP)At least one variable is integer valued.
In integer optimization, at least one variable is restricted to integer
values. But the decision variables can be linear and / or nonlinear.
We will consider only linear variables.
Linear Optimization Classification
Within ILP, we can have either “all integer” or “mixed integer” model.
A variable restricted to 0 or 1 values is called a binary variable.

4. Maximize
x
1+ 8x
2= Z
Subject to
x
1&x
2≥ 0
x
1 ≤ 2.0
x
1 + 10x
2≤ 20.5
What if x
1and x
2must be integers?
We can try four closest points.
(1, 2), (2, 2) are
infeasible.
At (1, 1), Z = 9 . At (2,
1) , Z = 10
Optimal may not be a corner point
3
2
1
1 2 3 4 X
1
LP optimal: Z = 16.80 x
1=
2.00, x
2= 1.85
x
1= 0.00, x
2
= 2.05
Integer optimal:(0,2),
Z = 16!
LP example

5. A simple LP example
Maximize 7x
1+ 11x
2= Z
Subject to
x
1&x
2≥ 0
x
1+ x
2≤ 6
18x
1+ 34x
2≤ 154
Optimal LP:x
1= 3.125, x
2= 2.875 with Z = 53.5
Optimal ILP:x
1= 1, x
2= 4 with Z = 51
9
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 9
There is no efficient procedure
(like Simplex) available to find
the optimal solution.
Many approaches: Start with LP.
1.Cutting Plane: Add one
constraint at a time till you get
an optimal solution.
2.Branch and Bound: If the
current solution is not integer,
split the problem into two
problems (with one constraint
added to each) and solve again.
Repeat till you get integer
optimal solution. Solver uses
this approach.
3.….

6. ILP: B&B Maximize 7x
1+ 11x
2= Z
Subject to
x
1&x
2≥ 0
x
1+ x
2≤ 6
18x
1+ 34x
2≤ 154
LP:Z = 53.5.
(3.125, 2.875)
9
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 9
Start with the LP solution.
Add two branches with extra
constraints if there is a non-
integer value and solve the
two sub-problems.
x
2≤ 2
Z = 50.
(4, 2)
Z = 53.222
(2.889, 3)
Feasible! No need
to expand this
branch. This is a
lower bound.
Add two
branches

7. Root node
LP:Z = 53.5
(3.125, 2.875)
Branch and bound methodology
Z = 50
(4, 2)
Z = 52.222
(2.889, 3)
x
1≥ 3
Infeasible!Z = 52.176
(2, 3.47059)
Z = 51.
(1, 4)
Z = 47.
(2, 3)
Optimum!
B & B methodology can
be applied to many other
problems besides ILP.

8. Capital Budgeting
Project P
1
P
2
P
3
P
4
P
5
NPV 101716814
Expenditure 4896803264
Assume budget (B) = 176 million
rupees. Which projects should we
select to maximize Net Present
Value (NPV)?
Maximize 10 y
1 + 17 y
2+ 16 y
3 + 8 y
4+14 y
5
Subject to: 48 y
1 + 96 y
2+ 80 y
3 + 32 y
4+64 y
5 ≤ 176
y
1 , y
2, y
3 , y
4, y
5 all binary (0 or 1).

9. Capital
Budgeting
Any problems with the model?

10. Binary Variables & Logical Relationships
In many models, one or more constraints involving binary variables can be added to
satisfy desired logical relationship.
Suppose we have several projects P
1, P
2, P
3, etc. and we define binary variables Y
1, Y
2,
Y
3, etc.
Y
1= 0 means project P
1is not selected
Y
2= 1 means project P
2is selected and so on.
Suppose the logical relation is: Select P
2or P
5or both.
We need to add constraint(s) such that when the relationship is satisfied, all constraints
must be met and when the relationship is not satisfied, at least one of the constraint
must fail.
We need only one constraint. Y
2+Y
51.

11. Relationship/Constraint(s)Explanation
If only P
2is selected, Y
2= 1.
If only P
5is selected, Y
5= 1.
If P
2, P
5selected, Y
2+Y
5= 2 but when both are not
selected, Y
2+Y
5= 0 and the constraint is not
satisfied.
Select P
2or P
5, or both.
Y
2+ Y
5≥ 1
Select at most one project from
P
3, P
4, P
5.
Y
3+ Y
4+ Y
5≤ 1
If 0 or 1 projects are selected, the constraint is
satisfied.
If two are selected, Y
3+Y
4+Y
5will be equal to 2 and
the constraint is not satisfied. Same if you select all
three.
If P
5is selected, then P
4must be
as well.
Y
4-Y
50
If P
5is selected, Y
5= 1 then Y
4must also be 1. If
Y
5=0, Y
4can be 0 or 1.
If Y
5=1 and Y
4= 0, the constraint is not satisfied.

12. 12
Linking Constraints and Fixed Costs
Suppose we purchase x units of a product at unit cost C. For sending the purchase order,
there is a fixed cost F. So the total purchase cost will be (F + C
x).
To correct this, we introduce a binary variable y and add a new constraint as follows.
Minimize F
y+ C
x
Subject to: x ≤ M
ywhere M is a large number.
y = 0 or 1
Note that when x = 0, y can be 0 or 1 according to the first constraint and minimization
will force it to zero.
When x > 0, y will be forced to a value of 1.
If this value is included in the objective function, then we will end up with fixed cost F
even when x = 0. This should not happen. There should be no fixed cost when we don’t
buy.

13. Fixed-Charge Problem
??????
�??????
�=ቊ
��+??????�??????�??????�>0
0 ??????�=0
Where,
??????
�is variable cost per unit,
�
�is fixed cost.
The objective criterion then becomes:
??????�����??????????????????=෍
??????=1
??????
??????
�??????
�
Because of discontinuity at the origin, Z becomes untractable from
the analytic stand point.

16. Job-Shop Scheduling
Problem


17. 

18. 

19. 

20. 

21. 

22. 

23. The concept of the cutting will first be illustrated by an example.
Consider the integer linear programming problem
Maximize z = 7x
1+ 9x
2
Subject to
-x
1+ 3x
2≤ 6
7x
1+ x
2≤ 35
x
1,x
2are nonnegative integers
The optimal continuous solution (ignoring the integrality condition) is
shown graphically. This is given by z = 63, x
1=9/2, x
2= 7/2 which
is non-integer.
CUTTING PLANE ALGORITHMS

24. Integer programming, MA-4020-
Operational Research 24
Cuttingplanealgorithm:
Thegeneralprocedureforcuttingplanemethodisas
follows:
Step1:findtheoriginalLPsolution(usingthesimplex
method)ignoringtheintegerconstraint.
Step2:ifthesolutionisintegerstop.Otherwise,
constructa“cut”derivedfromtherowthathasa
nonintegervariablewiththelargestfractional
valueandaddtothecurrentfinaltableau.Ifthere
isatieselectanyrowarbitrarily.
Step3:solvetheaugmentedLPproblem,andreturn
tostep2.

25. a [a] f=a-[a]
3/2 1 ½
-7/3 -3 2/3
-1 -1 0
-2/5 -1 3/5

26. Integer programming, MA-4020-
Operational Research 26
Consider the following problem .
Maximize Z=7x
1+ 9x
2
subject to: 7x
1+ x
235
◦ -x
1+ 3x
26
◦ x
1, x
2are non negative integers.

27. 0
1
2
3
4
5
6
7
8
0 1 2 3 4 5 6 7
fr
secondary
constraints
primary
constraints
(9/2,7/2); Z = 63
(4,3); Z= 55
X2
X1

28. Basic x
1 x
2 x
3 x
4 S
1 R.H.S.
Z 0 0 28/11 15/11 0 63
x
2 0 1 7/22 1/22 0 7/2
x
1 1 0 -1/22 3/22 0 9/2
S
1 0 0 -7/22 -1/22 1 -1/2

29. Basic x
1 x
2 x
3 x
4 S
1 Solution
Z 0 0 0 1 8 59
x
2 0 1 0 0 1 3
x
1 1 0 0 1/7 -1/7 32/7
x
3 0 0 1 1/7 -22/7 11/7

30. Sincethesolutionisstillnon-integer,anewcutis
constructed.Thex
1-equationiswrittenas
whichgivesthecut

31. Basicx
1 x
2 x
3 x
4 S
1 S
2 R.H.S.
Z 0 0 0 1 8 0 59
x
2 0 1 0 0 1 0 3
x
1 1 0 0 1/7 -1/7 0 32/7
x
3 0 0 1 1/7 -22/70 11/7
S
2 0 0 0 -1/7 -6/7 1 -4/7

32. Basic x
1 x
2 x
3 x
4 S
1 S
2 Solution
z 0 0 0 0 2 7 55
x
2 0 1 0 0 1 0 3
x
1 1 0 0 0 -1 1 4
x
3 0 0 1 0 -4 1 1
x
4 0 0 0 1 6 -7 4

33. Can be expressed in terms of x1 and x2 only by using the appropriate
substitution as follows:
or
Which is equivalent to
Similarly for the second cut,
The equivalent terms in case of x
1& x
2