Loading
Notes
Study Reminders
Support
Text Version

Integer Programming

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

The Structure follows a particular format. It is easy to do, it has some calculations involved and if you do it in the proper
manner, it will give you the proper result.
So, where and in which cases do you find a structured problem? We gave you the
example of a production problem that is, I have these, these resources, this is my profit
for the product I two products are there, these are the profits from the two products and
these are the resources available. So, which product I should manufacture and in how
much quantity? So, this is a structured problem.
The next problem that we gave you is Rajdhani is moving at a particular speed and the
next train is starting 15 minutes late, it has to maintain a particular distance. So, at what
speed should that train run or vice versa the next train is running at a particular speed, so,
what is the distance between the Rajdhani and the next express train. So, basically these
are examples of structured problems.
When does it become a semi-structured problem? Take the example of Rajdhani.
Rajdhani has left the station, another normal express train is running 15 minutes after
that Rajdhani and just after 15 minutes, a Duronto express is travelling which has the
same speed as Rajdhani. Now, what is happening here? Now the second train that is the
train at the middle, the normal express train that particular train is keeping on stopping at
signals. These are unscheduled stops.
So, what is happening? The gap between the normal express train and the Duronto
express which is just behind the gap is slowly lessening. So, what will happen? Duronto
has to slow down again and that will lead to Duronto express getting late. So, how do
you solve this problem? Now, this is a semi structured problem.
And what is an unstructured problem? Unstructured problem as we mentioned,
unstructured problem is new we have to find out we can take help of different
mathematical tools and techniques, but we have to find out some sort of a unique
solution to the unstructured problems ok. Now, so that was unstructured, semi structured
and structured problems we gave you the brief differentiation.
Next we came up to what do you mean by a model? Model is the mathematical
representation of a prototype of what is happening in the reality, ok. It is a prototype of
what is happening in the reality. We have model aircrafts; ok.
Now, this model is a mathematical representation for our usage, it is a mathematical
representation; that means, if you are working with a big real life problem, if you can
first make it into a model and solve the model first see how the model is behaving that
will give you indications whether you are missing out anything whether you are keeping
anything which is not relevant. So, you see and test with the model and once you are
convinced, then you go into the real world and apply that ok. So, model is basically a
mathematical representation of a representative set of what is happening in the reality.
So, this part we have covered. Then we came to solution techniques.
Now, in solution techniques in modeling, we have optimization, heuristics and
simulation. In optimization techniques what we do is, we try to optimize given the
limited resources or the constraints that we have and here we have three types; linear
programming, integer programming and non-linear programming.
Now, linear programming we have covered in the previous lecture. Today we will do
integer programming. Non-linear programming, we will not cover in this module
because we will do enough applications of non-linear programming as we proceed with
the other modules. Similarly, if you see we will not do simulation also here, we will do it
in a separate module, and we will deal with one full module for simulation only ok. So,
today we will take up integer programming as an optimization technique; ok.
Now, what is basically an integer programming? Now, what is an integer? Integer is a
whole number positive, negative or zero right. Integer is a whole number right. Now you
see the linear programming problems that we solved the solution had come in some
places in decimals ok; solution has come in decimals. Production we came up with
540.28 that is not possible. We cannot manufacture 540.28 units. So, ideally it is
integers, it is a whole number; ok.
So, integer programming deals with when situations will be like we have to have whole
numbers in the model ok. So, that is what integer programming is; ok. So, let us proceed
with integer programming today; right.

(Refer Slide Time: 07:32)

(Refer Slide Time: 07:33)

Integer programming: in integer programming, some or all of the variables must be an
integer that is a whole number or zero. In integer programming, some or all the variables
must be an integer that is a whole number or zero. Thus, some variables can have
fractions, but some variables will have to have a condition that it is a whole number ok.
Some can have 0 and yet some can have 0-1 values only that is either 0 or 1 values like
for example.

Now, what do you mean? This looks to be a jargon for the time being that what is this,
what is that ok. Say you are planning a vacation right. You are planning a vacation to
some place now you are planning a vacation to some place and you have choices, you
have three choices. Planning a vacation to place 1, place 2 and place 3 and definitely you
can go to only one place because your holiday is limited.
You can choose only one place. So, if you choose place 1, place 2 and place 3
automatically gets cancelled out; ok. So, it is a 0-1 problem that is either place 1 is
selected or it is not selected. Go to the last, look at the last bullet point and yet some can
have a 0-1 value; ok, some can have 0-1 values only that is either 0 or 1. So, if you
choose to tourist destination 1 so, either you choose it or you do not choose it. If you do
not choose it, it is a 0, if you choose it, it is a 1. So, this is called as a 0-1 problem.
And also if you see, if you choose tourist say if you can choose only one, if you choose
only tourist destination 1 then, tourist destination 2 becomes zero, tourist destination 3
becomes 0 because you can go to only one place, you have already selected your
destination it is like studying.
You have chosen instead you have the; you had the option based on the marks that you
have obtained in your examination, you had the option to take admission into three
institutions. Now, if you take admission into institution 1, institution 2 and 3 you cannot
take admission. So, either you take admission that is 1 or you do not take admission that
is 0 ok. In some cases, it will be like 0-1 for all means if you take admission in 1, all the
others become 0 because you cannot take admission there. So, this is called as a 0-1
problem ok. So, this is a 0-1 problem.

(Refer Slide Time: 10:15)

Now, some linear programming problem; now look at this very-very carefully. Some I
am reading it out because it is self-explanatory. Some linear programming problems are
actually integer problems. For example, if we are solving how many S and D type bags
we will produce? This was example one of module 2, 3rd lecture that is just today we are
in the 5th lecture of this module so, 3rd lecture of this model.
So, this so, we remember standard bags and deluxe bags that we were manufacturing. So,
if we were solving how many standard S and delux D type bags we will produce. The
solution came in as 254.28 S bags. But we cannot have a fraction. So, rounding off was
necessary, we, when we could manufacture 254 bags and then, we did sensitivity
analysis that is within what range we can continue. So, rounding off was necessary.

(Refer Slide Time: 11:25)

Wherever let us I am just reading out because this is simple, but important. Wherever
simple rounding off helps, we should try to avoid the use of integer programming I am
sorry there should be a correction here we should try to have just a second we should try
to avoid the use of integer programming as it is harder to solve. Wherever simple
rounding off helps we should try to avoid the use of integer programming as it is harder
to solve.
(Refer Slide Time: 12:06)

We understand that, this linear programming problem is actually an integer problem
because it has to be a whole number, we cannot manufacture fraction of a bag. It has to
be a whole number, but we use simple linear programming because we know that we can
round it off. It is not it will not make that much of a difference; ok.
But if it was a warehouse, if it was a multiplex and we were having 254.29 that fraction
if we round it off to 255; that means, lot of extra cost. If it is an over bridge railway over
bridge, roundly one more extra bridge means lot of cost. So, in some cases, you need to
have integer programming, but in some cases, you can do with simple linear
programming that is what these two slides mean; ok. I am repeating wherever simple
rounding off helps, we should try to avoid the use of integer programming as it is harder
to solve.
(Refer Slide Time: 13:11)

So, what do you mean by integer programming? Let us take an example max 2 x 1 plus 3
x 2 subject to this is just this is just an arbitrary one so, do not try to solve this, we do not
know whether it is solvable; ok. So, it is just an arbitrary equation that I wrote down.
Max 2 x 1 plus 3 x 2 subject to x1 plus x2 less than equal to 2; two third x1 plus 4 x 2
less than equal to 3 where x 1, x 2 is integer means whatever solution we get, we will get
the solution as a whole number. You will get the solution as a whole number.

If we remove the last constraint, that is x 1, x 2 is integer this becomes a simple linear
programming problem; ok; this becomes a simple linear programming problem.
(Refer Slide Time: 14:15)

Now here, I have something to say that is this one just give me a second this one this two
third x 1, you will say that, but we have a fraction here, this is not an integer now this
may not be integer, this can be a fraction because I am requiring 2 third of a resource,
that I cannot make a whole number.
I have a 1 kg of rice to manufacture muri or some other chura or something. I require two
third kg of rice so; I cannot make it a whole number. What this says is the solution that
you get for x 1 and x 2 these two will be whole number; these two will be whole number
that is what it says. The solution that we this x 1, x 2 integer means the solution that we
generate that should be whole number. Problem formulation can come in fraction, but
solution will be in whole number that is what we mean by x 1, x 2 is integer. So, this is
this is what we want to say; yeah.
Now, next we come to 0-1 integer programming problems. We just gave you an example
of 0-1 integer programming problems that is, I have a vacation; I have a vacation either I
go to some place or I do not go right. So, if I go, it is 1, if I do not go it is 0 right. So,
these are called as a 0-1 problem. I may not go, I can go these are called as a 0-1
problem; right.

I want to buy an apartment. Do I have the I want to buy an apartment beside a river.
Sorry let me just erase this yeah. I want to buy an apartment beside the river yeah in
Mumbai ok, but I do not know this is my dream, but my workplace is somewhere else.
So, either I buy; so, either I buy or I do not buy right. Either I do not or I buy. Either I
can get it or I do not get it. So, if I do not get it is 0, if I buy it is 1; if I do not get it is 0,
if I get it is 1 ok. So, these are some examples of a 0-1 integer programming problem.
Yeah just give me a second let me erase yeah. So, so these are these are examples of a 0-
1 problem.
Now, if you see again, we are mentioning 0-1 integer programming problem: structured
problem whether to open a centre in a particular area, I have some land; do I use that
land to open a shopping mall? Ok. Semi structured problem will be you already have that
is a 0-1; 0-1 problem do I open a shopping mall or do I not open a shopping mall. Semi
structured problem you already have a facility I do not want to shut it off so, what do I
do now? I do not want to shut it off. Look at the second problem, you already have a
facility I do not want to shut it off. So, what do I do? Ok so, these are all examples of 0-1
problems; yeah.
(Refer Slide Time: 19:27)

Now, one example. Let us take an integer programming example this will help us. A
company now let us listen very carefully we will; we will be able to do this integer
programming problem.

A company has the following warehouses A, B and C ok. Markets are D, E, F and G. So,
the warehouses may be Delhi, Mumbai, Kolkata, the markets are Delhi, Mumbai,
Kolkata, Madras, and may be Pune and Bangalore ok. So, the company has the following
warehouses A, B, C markets are D, E, F, G, H.
Now, there is a market to sell for the product and there is a demand in the market. What
are the demands? 200, 300, 400, 500, 600 these are the demands 2, 3, 4, 5, 6. I am sorry
2, 3, 4, 5, 6 the demands are 2 200, 300, 400, 500, 600. 200 for D, 300 for E, 400 for F,
500 for G and 600 for H right. So, demand of the markets are these.
Market demand is this, but how much can the warehouse hold? Warehouse has to keep
the product then only they will go to the market. So, warehouse capacities are 1000,
1500; 1000, 1500, 1200. So, A is for 1000, B is for 1500 and C is for 1200 ok. Fixed cost
of the warehouses are 5000, 10000 and 15000 respectively. Because warehouse has a
fixed cost, it has a rent it has so many other units and the cost table is given in the next
slide; yeah.
(Refer Slide Time: 21:28)

What do you mean by that? Whatever we have said is given here. What did we say? The
demand for the cities are given here D was 200; E D is the demand for the city. Demand
for the city markets were D, E, F, G, H, warehouses were these A, B and C and each
warehouse had a capacity of 1000, 1500 and 1200 remember? These were already given
to me and the cost of these warehouses were 5000, 1000, 10000 sorry yeah cost of these

warehouses warehouse A was 5000, 10000 and 15000 this is the fixed cost So, this may
be the warehouse rent; this may be the warehouse rent. So, these were the; these were the
parameters which were already given in the previous slide.
Now what do we; what are these 2, 3, 4, 2, 3, 4, 5, 3, 2, 7, 5, 1, 3? These are the
transportation cost for moving one unit of product from warehouse A to market D,
transportation cost of moving one unit of product from warehouse A to market E, from
warehouse A to market F these are the transportation cost for moving one unit of the
product.
Question is so, what is the question? The question is which of these warehouses I should
keep? So, question is which warehouse I should keep and how much to transport from
which warehouse? Which warehouse I should keep and how much to transport from
which warehouse? Ok; right. What is the core issue in this? So, what I will do is, I will
erase them.
(Refer Slide Time: 24:29)

What is the core issue in this problem? What do we want to get here; sorry yeah; what do
you want to get here? What is our objective as a business owner? As a business owner,
my objective is what? Minimize. What to minimize? Minimize total cost. Total cost is
equal to fixed cost of these warehouses, fixed cost of these warehouses plus variable cost
of transportation; ok. These cost will change according to output moved this is the cost
of transportation per unit of output; right.

So, these cost will change agreed. So, this is my model minimize total cost that is fixed
cost plus variable cost agreed? What are the constraints? Constraints are A can hold
10000 units at the most, B can hold B means warehouse B can have 1500 units at the
most and warehouse C can have 1200 units at the most. D has a demand this is one that
is the supply constraint. What is the demand constraint?
D has a demand of 200 so, even if you send them 400 they will not be able to sell. E has
a demand of 300 even if you send them 600 they will not be able to sell. F has a demand
of 400, G has 500, H has 600 ok. So, my first so, my objective is to minimize cost and
this these are my supply constraint: constraint 1, constraint 2, constraint 3, these are my
demand constraints 4, 5, 6, 7, 8.
What are the other constraints? The other constraints are warehouse A this is the cost,
this is the capacity, this is the cost. Now look at it very carefully, what is the total
demand total demand in the market? 200 plus 300 plus 400 plus 500 plus 600 is equal to
2000. If I open any two warehouses AB, BC, AC any two combination of warehouses,
my demand is met. These two any two warehouses can store my total demand. So, I need
not have all three warehouses. Any two warehouse can store the total demand. So, I need
not have all two all three warehouses.
So, every warehouse has a chance or an opportunity or situation to remain open or to
shut down right. Every warehouse has a chance or situation to remain open or to shut
down. So, warehouse A has the option to remain open or to be closed, warehouse B has
the option to remain open or to remain closed and warehouse C can remain open can
remain closed right. This is called as a 0-1 problem; clear.

(Refer Slide Time: 28:44)

So, let us go to the next slide. So, if you model it these this is my; this is my model. I
know it is difficult to see on the screen font size is less so, what I have done is this model
I have broken into 2-3 lines and I am showing in the next slides.
(Refer Slide Time: 29:02)

This is my objective function; all I do not know how much products we will move from
which warehouse to which market; ok.

(Refer Slide Time: 29:25)

So, I do not know how much how many products we will move from A to D. Quantity I
do not know cost I know 2 rupees per unit, cost is 2 rupees per unit, but quantity I do not
know. So, x 1 quantity moves from warehouse A to market D, x 2 moves x 3, x 4 and it
continues. So, what is my total cost? Variable cost this is my fixed cost, this is my fix
this portion is my fixed cost. My variable cost is 2 x 1 plus 3 x 2 plus 4 x 3 plus 5 x 4
plus 3 x 5 plus 3 x 6 plus 1 x 7 in this way it continues up to x 15.
So, if you see now, this continues up to x 15 variable cost plus let us go back 5000 is the
fixed cost when? Only if warehouse A is open. We need two warehouses I just showed
you because my total demand was 2000 units; total demand was 2000 units and my
supply if I look at it two warehouses are enough to meet the storage requirement.
So, 5000 is the cost of this warehouse provided it is open right. So, what we will do? Just
like we did 2 x 1 here what we will do? 5000 y 1 ok. So, it will be 5000 y 1 and where y
1 can be only 0 or 1 right agreed? Where y 1 can be only 0 or 1 that is it is either open or
it is close ok. So, this is basically what we have mentioned here 5000 y 1, y 2, y3; ok.

(Refer Slide Time: 31:31)

And just go here at the end, if you go straight y 1 can be greater than 0 so sorry ah y 1
can be greater than equal to 0 less than equal to 1 and it is an integer; that means, it has
to be a whole number. So, y 1 can basically only be 0 and 1, y 2 can only be 0 and 1, y 3
can only be 0 and 1 agreed.
(Refer Slide Time: 32:00)

What are the other constraints? My supply let us go back x 1 plus x 2; x 1 plus x 2 plus x
3 plus x 4 plus x 5 this total quantity is less than equal to 1000 capacity I cannot store
more than my capacity right, x 1 quantity I have to move to market D, x 2 to E, x 3 to F,

x 4 to G, x 5 to H. So, I cannot this total cannot be more than 1000 right. So, x 1, x 2, x
3, x 4, x 5 is less than equal to less than equal to 1000. 1000 y 1 why? Because y1 is
what? 0 or 1 means I can only supply provided it is 1, that is provided it is open right that
is y; y 1. You can only supply provided it is open; right.
So, in this way my supply constraints and these are my demand constraints; right; ok. So,
just look at this number, x 1, x 6, x 11 so, x 1 plus x 6 plus x 11 is equal to 200 this is the
market demand; ok.
(Refer Slide Time: 33:57)

Now this so, we broke up this problem just for easy viewing so, but if you look at it, this
is the entire problem your objective function, the supply constraint, the demand
constraint and the integer constraint.

(Refer Slide Time: 34:01)

So, if you solve it, if we use LiPS, we find that the minimum cost is 21100. The LiPS
model is anyway given. So, if you; if you want you can download the software and copy
paste this model and see how it is behaving what results are coming, you will see that
this result is shown exactly in this manner.
(Refer Slide Time: 34:22)

And this is the movement, x 1 what was x 1? X 1was warehouse A to market D we
should move 100 units. What was x3 warehouse A to market F right D, E, F, G, H right
we should move 400 units, x 4 D, F, G right 500 units and ultimately we see that y 1 is

open and y 2 is open, y 3 value is 0; that means, it is closed. So, this is how we do integer
programming; this is one application of integer programming that we will need when we
do the materials management part of this module. I just wanted to show it to you here to
tell you how this integer programming works; ok