Okay, so this is Discrete Optimization 
and Mixed Integer Program. 
We'll talk about MIP. 
So, this is one of these magical tools 
that we have in optimization, so it's 
going to be very different from what you 
have seen so far. 
And this is a tool, when it works, it's 
really amazing. 
And sometimes it works, sometimes it 
doesn't, but you will see it's really a 
magical tool. 
so what I'm going to do in this lecture 
is give you a basic introduction to Mixed 
Integer, Mix Integer Program, okay? 
We call them MIP, okay. 
I'll talk about MIP all the time today. 
And then we talk about branch and bound, 
which is the basic technique to actually 
solve them, okay. 
Basic introduction. 
This is a big field. 
What I want to give you is the feeling 
about what this is about okay? 
So, this is, this is an integer program. 
So, what you have to think is that it is 
like linear program. 
Okay? 
So, like linear programming. 
The only difference is that the variable 
here, have all to be integers. 
Okay? 
So, we still have, you know, an objective 
function that we are minimizing. 
And we have n variables and m 
constraints. 
Okay? 
So, you see the, you know you see the end 
variables, you see the end constraint. 
All these constraints are inequalities 
okay? 
So, the variables are constraints to be 
non negative okay? 
Again okay? 
And then we have these additional 
constraints that they have to be integer 
values okay? 
And this difference, this makes a huge 
difference in practice of course. 
Okay? 
So, we'll talk about the mixed integer 
program when not all the variables have 
to be integers. 
Some of them can and some, some are and 
some aren't, okay? 
And that's essentially a mixed integer 
program. 
So, we have some values that are like in 
linear programming. 
They can take you know, rational values, 
real numbers. 
Are and then some of them are going to be 
integers. 
Okay, so and that's why you call mixed, 
mixture of two variables. 
Okay, but once again, a big you know, a 
big, big thing to mention here is that 
the constraints are linear, they're 
qualities and of course we're minimizing. 
Of course all the techniques that I've 
shown you for linear programming are 
still working, right? 
Maximizing is easy to do. 
You minimize the negation. 
Writing equations or you know, 
inequalities or equations, and, and you 
know, equations are inequalities. 
Are going to be done exactly like we did 
for linear problems. 
And of course if you want a variable 
which can take negative value, you can 
always use a different set we have done 
before. 
Okay? 
So, most of the same technique, but what 
is key is that the constraints and the 
objective function are linear. 
But now, some of the variables can be 
integers. 
Okay? 
So, the difference between having integer 
variables or not having integer variable 
is big, right? 
So, that's the gap between being 
polynomial and NP complete, okay? 
So, this is a huge difference, as soon as 
you introduce this, this, this integer 
variables okay? 
So, so the, the, the entire complexity of 
the problem changes and for most people 
in industry sometimes, it's a big, it's a 
big difference right? 
They say, oh but it should be easier 
there are fewer integers than there are 
real numbers but no having integers is 
what makes this problem really complex. 
Okay? 
So, this is an example that we have seen 
before. 
Right? 
The knapsack example. 
This is, this is a mixed integer program. 
Okay? 
So, we have a linear objective function, 
the variable xi are constrained to be 0 
and 1. 
And they have to be integer value. 
Want to take the item or not. 
Okay? 
You know it's not a fraction value. 
And of course we had this linear 
inequality. 
Okay? 
So, that's the most simple in a sense. 
Mixed integer program that we have okay? 
So, what we're going to do now is look at 
warehouse location we see this problem 
before when we do local search. 
And what we going to do is develop the 
mid program for it. 
So, I'm going to go over what the problem 
is again and then we see how we design. 
And mid program, actually we'll come back 
several time to this problem, okay? 
So, what we had there is that we have 
various locations where we can open a, a 
warehouse, okay? 
So, when we open a, a warehouse in a 
particular location, we say we open that 
warehouse. 
If we don't put it there it's basically, 
basically say that it's closed. 
Okay? 
And then we have a bunch of customers 
have, you know, around you know, all over 
the place. 
Okay? 
And the goal is actually to choose which 
warehouses to open so that you can serve 
all the customers. 
And every one of the customer. 
Is,will be allocated to exactly one 
warehouse okay? 
Now what you want to minimize is the cost 
of opening these warehouses and 
maintaining them, that's the fixed cost 
for every warehouse, warehouse. 
And then you have the transportation cost 
from the customers to the warehouse okay? 
So, you will want to minimize the sum of 
these two things okay? 
So that's the problem okay. 
So, this one solution where you open one 
warehouse and you serve all the customers 
with that warehouse okay? 
This is another solution where we open 
two warehouses okay? 
And the customer are served you know, in 
the way which is depicted here. 
But once again you know I want to focus, 
I, I want to mention the fact that every 
one customer is assigned to exactly one 
warehouse. 
Okay? 
And this is another solution with two 
warehouses. 
It's a different customer allocation. 
Okay? 
So, now the question is can we find a MIP 
model okay? 
For warehouse location. 
Okay? 
And so once again, it's [UNKNOWN] 
constraint programs. 
It's going to be easy, right? 
So, the only three things that we have to 
do is find what are the decision 
variables. 
And then we have to express linear 
constraints, because we are in a MIP 
context in terms of this decision 
variable. 
And then express the objective function, 
which is also to be linear. 
Okay? 
So, can we find that for warehouse 
location? 
Okay, and obviously the answer is yes. 
Otherwise I wouldn't be talking about 
this problem, right. 
So, what are the decision variables? 
Okay? 
So, in this particular case we are 
going to use two types of decision 
variables. 
Okay? 
So, the first type is going to basically 
be associated with every warehouse. 
Okay? 
So right, so this is what we want at the 
end, we want to know. 
You know, which warehouse is to be open 
okay? 
How many and where, okay? 
So, we'll have a decision variable xw for 
every warehouse w. 
And that variable is going to be one, if 
that warehouse is open, okay? 
So, that means that we're building the 
warehouse at that location, okay? 
It's zero if we just don't build the 
warehouse at that location, okay? 
So, that's the first type of variables 
that's going to tell us where to build 
these warehouses. 
And how many. 
Okay? 
Now, we need a second thing, right? 
So, we need for every customers to know 
which you know, warehouse it's going to 
be allocated to. 
So, we are going to use a second set of 
variable, which we call the Y variables 
here. 
Okay? 
And Ywc is going to be equal to 1. 
If customer c is basically served by 
warehouse w okay? 
And zero otherwise. 
Zero would mean, okay custo, warehouse w 
doesn't serve customer c. 
Okay? 
So, once again two types of variables. 
Whether we open a warehouse or not that's 
the x variables and the y variables is 
going to tell me for a pair of customer's 
warehouse are these two guys connected? 
You know, is this warehouse serving that 
customer? 
Okay?. 
So, now we the decision variables the 
only thing that we have to do now is 
express the constraints okay? 
So, what are the constraints okay? 
So think about it. 
What are the constraints in this 
particular setting, okay?. 
Now there is one constraint which is 
really important that we don't want to 
miss is that we can serve a customer with 
a warehouse. 
Only if that warehouse is open. 
Right? 
So, we don't to connect a customer to a 
warehouse that doesn't exist. 
Right? 
So, that's a very simple constraint. 
Okay? 
But it's very important. 
Otherwise you know, we don't, we wouldn't 
have a solution. 
And the second one is that we want to 
make sure that the customer is served by 
exactly one warehouse. 
Okay? 
So, so we have to make sure that the 
customer is served. 
But it can only be served by one 
warehouse. 
Okay? 
And so, essentially that's the second 
constraint, the second type of constraint 
that we have to express. 
Okay? 
Now, we have to express these constraints 
as linear constraints. 
Okay? 
And that's what this slide is showing 
you. 
Okay?. 
So, the first constraint telling you that 
you know, a warehouse is to be opened to 
serve a customer, is a simple inequality 
with two, the two, the two types of 
variables okay? 
So, we are basically saying that, why the 
value c has to be smaller or equal to xw, 
what does that mean okay? 
So, if we close the warehouse, so that 
means that xw, if we close warehouse w so 
that we don't build a warehouse, that 
means xw is 0 right? 
If xw is 0 then it's for, you know y you 
know, wc is going to be forced to be 0, 
we can't actually you know, serve that 
customer with that warehouse. 
That's part of what we want, right? 
And if, if xw is 1, that basically means 
that the warehouse is open, we can use 
it. 
But that doesn't mean that we have to 
allocate customer c to that warehouse, 
but we can. 
Okay? 
So, that value is going to be 1, which 
basically means that the variable you 
know, ywc it's free, it can take value 0 
it can take value 1. 
That's the meaning of that constraint. 
Okay? 
So, in a sense we are encoding you know, 
the relationship between these decisions 
using an inequality in this particular 
case. 
And this works well because these two 
variables take 0, 1 values and we come 
back to the fact that in a MIP a lot of 
the decision variables are going to be 
0,1. 
Okay? 
The second constraint that you see there, 
is basically telling us that a customer 
should be served by exactly one 
warehouse. 
And what we're going to do is, we're 
going to look at one customer, we're 
going to look at all the possible 
warehouse. 
And we're going to make sure that the sum 
of the variables that are basically 
denoting whether that warehouse is 
serving that customer, is equal to 1. 
And that's what you see there, okay? 
So, you see a sum for all the warehouses. 
And then you see the variable ywc okay? 
So, that basically means is y actu, is w 
actually serving customer c? 
Okay? 
So, it's the sum of all these guys and 
they have to sum to 1. 
Okay? 
Once again, these guys are 0, 1 so that 
basically means that one of these 
warehouses is going to serve that 
customer. 
Okay? 
So, beautiful we have a model, if we can 
express the objective function. 
The objective function now is the sum of 
the fixed costs and the transportation 
cost. 
Okay? 
It's reasonably easy to state. 
What you do, this is essentially the 
fixed part, okay? 
So, what we are doing is the sum for all 
the warehouse of the fixed cost of the 
warehouse, okay, times whether the 
warehouse is open or not. 
So, if the warehouse is closed, there is 
no cost. 
If the warehouse is open will, you know, 
incur a cost of cw. 
Okay? 
And then the second, the second aspect 
here is basically the transportation 
cost. 
We look at the pair wc, and if, and if, 
you know, w is serving c, that variable y 
is going to be 1. 
So, we want to incur the transportation 
cost. 
twc okay? 
So, that's we have to do, of course with 
the variable y is 0 then essentially 
there is no cost incurred. 
You know, these things are not connected. 
Okay? 
So now, so this is the transportation 
costs okay? 
So fixed costs, transportation costs. 
We have the objective function and we 
have the entire model okay? 
So, this is the entire MIP model for 
warehouse location. 
Okay? 
Objective function, fixed cost, variable 
cost. 
Okay? 
Then we have the constraints here, that 
basically state that you know, you can 
serve a customer with a warehouse. 
If the warehouse is, if, you can serve a 
customer with a warehouse if the 
warehouse is open. 
Then you have to serve exactly 1 customer 
uh, [INAUDIBLE] a customer exactly once, 
so you look at all the warehouse exactly 
one should serve that customer. 
And then usually these two types of 
variables have to be 0 and 1. 
Okay? 
We open up a warehouse or we don't, we 
serve you know, the warehouse w serve 
customer c or not. 
Okay? 
And that's the entire model. 
Okay? 
So, so its interesting when you look at 
these models that the variables here are 
0, 1. 
Okay? 
And I'm going to come back to that, but 
we could have another essential model. 
We could think of you know, instead of 
having all these 0, 1 variables, ywc for 
all the warehouses, why don't I have 
simply a variable yc. 
Which denotes the, the, the warehouse 
that is serving customer c, okay? 
Now this is a question for you, okay? 
So think, you know, use, you know, try to 
build a MIP model using a decision 
variable which is yc, okay? 
And see what the challenges are. 
It's a very, it's a very interesting 
exercise try to see what is going to be 
tough if you use these decision 
variables, instead of those 0, 1 
variables that I showed you, okay? 
So, so to think [UNKNOWN] is that in 
general, MIP models love 0, 1 variables, 
okay? 
So, you'll see a huge amount of 0, 1 
variables in MIP model. 
You'll see typically very few integer 
variables, okay? 
The integer variables are typically 
going to be 0 and 1. 
So, you know, it's like you know, MIP 
models like to have decision which are 
actually yes or no, okay? 
So, very different from constraint 
programming model in that sense, okay? 
But the good point is that once you have 
the 0, 1 variables expressing linear 
constraints, is typically very simple, 
okay? 
So, in a sense you know, you use these 
very simple 0, 1 variables and then all 
the constrains. 
Are you know, simple to state in general. 
Okay? 
So, so sometimes they have many indices, 
but they are easier to state, they are 
easy to state okay? 
So, it doesn't mean that you know 
modeling in MIP is easy. 
And we'll see some of these issues later 
on so, there're are still many, many 
possible models you can design. 
You know, what are the basic, what are 
the basic decision variables that you are 
going to use? 
What are the constraints? 
What are the objectives? 
Everything that we said for constraint 
programming is still valid. 
Finding a good model is not necessarily 
easy, okay? 
And so, we'll see some of these things 
in, in a moment, actually, or the next 
lecture. 
Okay, so now we have a beautiful MIP 
model, how do we solve them? 
Now this has been an active research area 
for many, many decades, and it's still a 
very active research area, it's a 
fascinating area, okay? 
And so, one of the basic techniques to 
solve MIP problems okay? 
Is to use branch and bound. 
Okay? 
Remember, branch and bound, we saw that 
you know, first lecture you have, or 
second lecture, with bounding, and 
branching. 
Okay, bounding is what, is finding an 
optimistic evaluation of the, of the 
objective function. 
Optimistic, optimistic relaxation, we 
love relaxing, right? 
And then branching is when, you know, is 
basically splitting the problem into sub 
problems, and then apply the same 
algorithm on the sub products. 
Okay? 
So this is the basic two steps. 
Now what is nice about MIP models is that 
they have a very, very natural 
relaxation, okay? 
Which is linear programming. 
And that's why we talked about linear 
programming so much. 
We have this linear relaxation that we 
can use as the bonding of as the bonding 
part of MIP models, of branch and bond 
for MIP. 
Okay? 
So, the key idea is that you going to 
remove the integrality constraints, and 
you have a relaxation, okay? 
So, this is the only thing that you do, 
right? 
You look at this big MIP model. 
If you remove the integrality 
constraints, what do you have? 
You have a linear program. 
You can solve that very fast, and that's 
what we going to do, okay? 
So, the bounding path, the optimistic 
relaxation, is going to be basically 
relaxing the integer constraints. 
You wrap your largest set of values that 
the variable can take, so it's a 
relaxation. 
Okay? 
So, so basically the branch and bound for 
MIP models is going to be solving the 
linear relaxation. 
Okay? 
At a particular node, you're going to do 
that, you're going to look at that node. 
You're going to say, oh, I want to solve 
the linear relaxation. 
And if the linear relaxation is worse 
than the best solutions you have found so 
far, you can prune that node, that, that 
node away, okay? 
It basically means that the associated 
sub problems to that node is provably 
sub-optimal. 
You can get rid of it. 
Okay? 
So, if not, okay, so if the, you, you are 
basically looking at this linear 
relaxation more closely, and you are 
looking to see if it has all integer 
values, which can happen, right? 
And if that happens, that means that in 
this large space of solutions, you know, 
the linear programming relaxation, it 
throws in an integer value for all of 
these variables. 
And that means that you know, obviously 
it's a solution to the overall MIP 
problem, well to, for that node, right? 
And so, essentially you have found a 
feasible solution and you can obtain the 
best solution you have found so far, 
okay? 
Now if none of these two things apply 
then you need to branch, okay? 
And the interesting thing about MIP 
models, is that they are going to use the 
linear relaxation to drive or to branch 
in general. 
Okay? 
And so there are many ways to do this, 
okay so I'm just going to mention one 
here. 
But this is also a very active area. 
How you branch, what do you use, how do 
you use, do you use the objective 
function? 
Do you use the constraints, and so on. 
But this is the simplest scheme that is 
using the linear relaxation. 
So, what you're going to do is you're 
going to look at this relaxation, and you 
know that, you know, some of the integer 
variables have a fractional value, and 
they should not. 
Okay? 
So, what you're going to do is take one 
of those, okay, which has, let's say, x 
which has a fractional value f. 
And what you're going to do is create two 
set problems. 
Okay? 
One of them is going to be saying that x 
has to be small or equal to the integer 
which is the smallest, the largest 
integer which is smaller than f. 
Okay? 
So, that's the floor of, of f and okay 
and that's one of the sub problems, okay? 
And the other sub problem is going to see 
that x is greater than the seal of f, 
that's the smallest integer which is 
larger than f. 
Okay? 
So, these are two sub problems you can 
add to the, to the set of constraints 
that you have and then you repeat the 
branch and bound. 
Okay? 
So, the key point here, if you remember 
constraint programming. 
Constraint programming was obsessed with 
constraints, okay? 
And was basically branching on the, you 
know, using feasibility information. 
Here we are obsessed with the objective. 
We are getting these, good, you know, 
well, hopefully good. 
Relaxation of the objective optimistic 
evaluation of the objective. 
And then what we use is we use this 
linear relaxation which is like ooh, you 
know, this is like a very good solution, 
okay? 
But it's not feasible, and trying to use 
that for branching, okay? 
So, in a sense we are branching using 
optimality information, okay? 
So, summarizing what I just said. 
Okay, so we are basically focusing on the 
objective here. 
Okay, once again I'm exaggerating, of 
course the MIP system in practice. 
We'll also focus on some other 
constraint, but it's good to exaggerate 
to, you know, drive the point home here. 
So, we are basically focusing on the 
objective and the relaxation gives you an 
optimistic bound all the best value that 
the MIP can ever get. 
Okay? 
The pruning is based obviously on the 
objective and sub-optimality. 
Okay? 
So, when you detect the linear relaxation 
is not higher than the best solutions 
you've found, not better than the best 
solution you've found so far, you just 
prune it away, okay? 
And obviously the relaxation has been 
obtained by relaxing the integer 
integrality constraints okay? 
And we have a global view of all the 
constraints, you know. 
So, in constraint programming all the 
constraints were acting, you know 
independently. 
Here we relax all the integrality 
constraints, but when we look at the 
constraints, we look at them globally. 
Okay, so we have this linear program, 
which basically look at the constraints 
globally, but they just have removed the 
integrality constraints. 
Okay? 
So, in the Knapsack, in a sense, so when 
you look at the relaxation, what we did, 
this is basically the MIP model for the 
knapsack. 
And the relaxation is only looking at 
this, you know, 0,1 that you see there, 
and basically replacing them by the fact 
that oh, it doesn't have to take the 
values 0. 
One, it can take any value between 0 and 
1. 
Okay? 
That's the linear relaxation and we can 
do that for any MIP model right? 
So we just remove these integrality 
constraints okay? 
Now, so in the case of the Knapsack, the 
linear relaxation is the same as the 
greedy approach that I've shown you 
right? 
Order the item by the most value per 
weight okay, and select them in that 
order okay? 
Until you get a fractional value and you 
take that fractional value. 
to, to, to get a relaxation. 
So, that's what the linear programming 
relaxation is going to do. 
So, I'm going to talk a lot about this 
linear programming relaxation the next 
couple of, of classes. 
It's a beast and, you know, you see it's, 
it's, it has very interesting behavior. 
Okay? 
Now when we branch, we branch with a 
fractional value, and essentially in this 
particular case of the Knapsack, the 
fractional value is going to be the most. 
You know the, the item with the, the 
largest ratio that we can't actually fit 
in the item. 
We fit all of the items which are more 
valuable per weight, right, better ratio. 
Okay? 
And then we are basically looking at that 
last item that we would want to put into 
the Knapsack, but we could only put in a 
fraction of it. 
That's essentially, you know, the, the 
item we're going to branch on, because 
this is the only item which will have a 
fractional value, okay? 
Now, the question that I have for you, 
for you to think of at this point, is 
that ooh, you know, we're going to take 
two things. 
These are 0,1 variables, right? 
So, he's going to be, so that, that the, 
when we round the fraction downwards or 
upwards, what you are going to get is 
essentially 0 on one side and 1 on the 
other side. 
So, we are going to not take the item or 
take the item. 
So, when we don't take the item, can you 
think of what the linear relaxation is 
going to do, okay? 
So, lot of the games in MIP is going to 
figure out what these [INAUDIBLE] linear 
relaxation is going to do. 
And it's very capricious, you'll see. 
Okay? 
So, in a sense here, you know, what I'm 
asking you, is that if we don't take the 
item, what's going to happen. 
Okay, or if we take the item what's going 
to happen to this linear relaxation, can 
you figure that out? 
Okay? 
So in a sense, the question that I'm 
asking you is, ooh which value is 
going to become fractional if you don't 
take the item? 
Okay, think about it. 
I decide not to take the item. 
All the items that were more valuable, 
what's going to happen to them? 
Well, you're going to still take them. 
And then what you're going to have is a 
fractional value for one or more, well, 
yeah, one or more items, later on. 
Okay? 
So that's what's going to happen. 
If you don't take the item. 
If you take the item, what's happening? 
Ooh, before you couldn't put this item in 
the Knapsack. 
No you decided, I want to take that item. 
So, that means that some of the items 
that were before, you won't be able to 
put inside the Knapsack, okay? 
And so the, there is going to be a 
fractional value for an item that was 
more value that's now going to be, that's 
now going to be fractional okay? 
So, this is the kind of reasoning that 
sometimes you need to think about, you 
know, what is the linear relaxation 
doing. 
Because that will give you insight on how 
to actually improve your models, okay? 
So, this is a very simple illustration 
because this is a really, really simple 
example but it's going to drive two 
points home, okay? 
And, and, you know, you'll see them. 
So, once again, so we had basically these 
three, you know, this knapsack with three 
items, okay? 
So, the value of the item is Vi, the 
weight of the item is Wi, your item 1, 2 
,3. 
Okay? 
So, most valuable item is item 3. 
Okay, 35 divided by 3 is pretty good. 
Okay? 
Above 10. 
Okay? 
So, a 45 divided by 5 is what is 9 and 48 
divided by 8 is some, it's around 6 
right? 
And so therefore, you know this is the 
most valuable item that is the next one 
and this is the least valuable item from 
the weights, you know value ratio. 
Okay? 
So, at the top of the, at the top of the 
tree at the root node, what you have is a 
value of 92 and that value of 92 is 
basically obtained by selecting item. 
Well, I think we can let the linear 
relaxation do this and this is what the 
linear relaxation does okay? 
So, the linear relaxation is going to 
take, you know, value, value one for x1, 
I'm taking item 1, I'm taking item 3. 
Okay? 
So, these are the two, you know, items 
with the best ratio. 
And then I take only a fraction on the 
second item, because I can't put the 
entire item in okay? 
And you know once again this is 5 and 3 
this is 8 you know I can only take a 
quarter of that guy. 
And this is all you get you know, this 
this value because you, you, you sum 45 
and 35 that's 80 and then a quarter of 48 
that's 12 that's the value of the linear 
relaxation. 
So, this linear relaxing is basically 
giving you this solution and that 
particular value. 
Okay? 
What are we going to do? 
Okay? 
I told you. 
We look at this thing and we look, ooh, 
what is the fractional value? 
And in this particular case, it's item x2 
okay? 
So, we're going to branch on x2, and 
we're going to create two sub-problems, 
okay? 
One where x2 is 0 and one where x2 is 1. 
Okay? 
What happens if x2 is 1, is 0, okay? 
So, that's the node that you see over 
there. 
Okay? 
Now the linear relaxation is 80 okay, you 
can select only item 1 and 3. 
Okay? 
So, we solved the linear relaxation at 
that node, and what do we obtain? 
You know, x1 is equal to 1, x2 is equal 
to 0, x3 is equal to 1. 
That's the linear relaxation. 
The linear relaxation here is finding, 
you know, an integral solution. 
We know that we don't have to branch 
anymore. 
We are fine, okay, this is the best we 
would be able to do. 
It's all integral okay, so we don't have 
to branch anymore. 
It's done, okay? 
So, the linear relaxation here is telling 
you when to stop branching in a sense, 
okay? 
So, we have found a solution we evaluated 
okay? 
The other thing that we wanted to do, is 
basically you know, choose x2 is equal to 
1, okay? 
So we basically fix the value of x2 to 1. 
We solve the linear relaxation again, and 
the linear relaxation is going to give us 
a value of 71.33. 
Okay? 
You see that now there is this value of 
this x3 which is fractional, okay, it was 
actually, it was actually not fractional 
in the original relaxation, okay? 
So, we know that this is, we would have 
to continue branching, but what we have 
seen here is that the value of the inner 
relaxation is 71. 
The best solution that I have [UNKNOWN] 
so I can actually prune that node away 
already. 
So, with one branching essentially I, I 
solved this problem optimally. 
Okay? 
So, this is essentially illustrating the 
various concept here. 
At the particular node you solve the 
linear relaxation. 
Okay? 
You look, the value of the linear, the 
objective function of the linear program 
is basically giving you an optimistic 
evaluatoin of what the MIP can do. 
Okay? 
At that particular node. 
Okay? 
And then you look at the variables over 
there and you take a fractional variable 
to actually branch okay? 
And then you branch left and then you 
branch right based on that fractional 
value. 
Okay? 
Now, one of the questions that you have 
to think of is when is branching bound 
going to be effective? 
Okay? 
What is it's going to be really effective 
is the value of the linear relaxation is 
tight. 
It's very, very close if the linear 
programming relaxation is very close to 
the optimal value of the MIP. 
Okay? 
Is that sufficient? 
huh? 
Think about it. 
So, if I tell you, I guarantee, okay, 
that this linear relaxation is going to 
be 0.5%, always of the best value of the 
MIP. 
Is that sufficient for the MIP to 
actually behave nicely all the time? 
Okay? 
Question for you. 
Okay? 
I wish we had quiz in this class. 
We don't, but anyway. 
So think about it. 
Is it sufficient? 
Okay? 
So, what is a good MIP model? 
A good MIP model is going to be a model 
which is a good linear relaxation. 
It's not sufficient necessarily. 
Okay? 
I answered that question, right? 
But this is a necessary condition, you 
want a model with a very good linear 
relaxation. 
Why? 
Because you're going to prune the search 
space much better. 
Okay? 
Now, which variable should we branch on? 
So, we have a lot of variables, it seems 
that we have plenty of variables with 
fractional values. 
Which one are we going to branch on? 
Okay? 
So, one of the good heuristic is to 
branch with the most fractional value 
okay? 
So why, why would we do that well, you 
know once again exaggerate. 
Assume that you variable which is not 
very fractional okay? 
So, it's like you know 0.99999999999 
okay? 
And it can take value 0, 1 okay? 
So, when it is 0.9999999 [UNKNOWN] I hope 
I you know, use the same number of nines, 
but that means that it's really close to 
one, probably branching there doesn't 
make too much sense. 
If a variable is 0.5 what does that mean? 
It means that the linear relaxation is 
saying, hm, maybe I should take this item 
hm, maybe I should not take this item hm, 
I do not really know. 
Okay? 
And so therefore these are the type of 
variables that you need to branch on. 
Okay? 
So, this is a basic introduction to MIP. 
Next time we are going to see really cute 
things, on how you can actually build MIP 
model. 
What does it mean to be a good MIP model? 
Okay? 
come back. 
Thank you.