Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming. Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.
MIP 1 - intuition, relaxation, branch and bound, knapsack, warehouse location
Loading...
来自 The University of Melbourne 的课程
Discrete Optimization
207 个评分
从本节课中
Mixed Integer Programming
Mixed Integer Programming generalizes linear programming by allowing integer variables, which dramatically changes the complexity of the problems but also broadens the potential applications significantly. These lectures review how to model problems in mixed-integer programming and how to solve mixed-integer programs using branch and bound. Advanced techniques such as cutting planes and polyhedral cuts are also covered.
与讲师见面
Professor Pascal Van Hentenryck
Dr. Carleton CoffrinAdjunct Lecturer
Computing and Information Systems
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.
