Discrete optimization MIP part three. Okay?
So what we going to see today is cutting planes.
Okay? So the basic idea is like in constraint
programming. What you want to do, is you want to add
new constraints to the system that going to make the system easier to solve.
Now, in constraint programming, you would do that for actually improving constraint
propagation and reusing the search space, okay?
So, here what we're going to do is add new constraints.
But these new constraints, the goal, is to actually improve the linear
relaxation. Make it, you know, move up as much as you
can, okay. And so these, so, these are cutting
planes okay. I'm going to talk about them this lecture
and the next lecture, okay. And, this lecture is going to be focused
on Gomory cuts, which are very interesting cuts as you will see in a
moment. Okay, so, the basic key idea here, of
this lecture, very simple. We want to find a new linear constraint
okay that is valid. That means it doesn't remove any integer
solution okay any feasible solution. And it also, it helps, okay which
basically means that when you are at a particular point.
Okay, it's going to remove the value of the linear relaxation, the current, well,
the current basic feasible solution. Okay.
So it's going to improve the value of the linear relaxation.
Okay, so this is what we want, this is what we want to do, okay.
So in terms of constraint programming, this would be, okay I want something
that, you know, a new constraint that, which is valid, same definition.
And which improve propagation. Here is going to be improving the linear
relaxation. Which means removing the current value of
removing the current optimal solution of the linear relaxation.
Okay so let me first illustrate that geometrically and then we'll move to the
algebraic part and come back to the geometry at the same time okay.
So this is a very simple MIP. Actually its pretty boring.
Okay you'll see but it's going to be simple enough that we can actually show
these things in practice, okay. So we are maximizing x2 subject to these
two constraints, so 3x1 plus 2x2 is smaller than 6.
Sorry, equal. And then minus 3x1 plus 2x2 is smaller
than 0. Okay, both variables are integers.
Okay. So this is the linear relaxation.
There. Right, so, obviously it's fractional, you
know, x, x 2 is 1.5, x 1 is 1, okay, so x 1 is fine.
Okay? But this is the relaxation.
Okay? Now, when we are actually trying to solve
this as a MIP, you know, the feasible point of this guy, that guy, and that
guy. So essentially, the linear relaxation,
you know, is actually I think a larger space than the space of all the interior
points and that's where the problems come from okay.
And so what we want to do is to say oh can I improve these relaxation to get
closer to these you know integer points. Okay so this is one of the cut that we
will generate okay. So this cut is basically saying that x 2
is smaller or equal to one okay. And so what this cut is basically doing
is cutting this big part of the top of the linear relaxation and it can do that
because we are not removing any integer solution to that particular, to that set
constraints okay. And then we get this smaller poly top now
and we can re optimize over it. The linear relaxation is going to do it's
work and get to one of these vertices okay which is going to be which is
going to be optimal for the linear relaxation at this point okay.
Find vertices, okay the value of x2 is equal to 1 but the value of x1 in this
particular case is 2/3 so it's still not you know it's still fractional.
Okay, so we going to generate the new cut.
So this is a beautiful cut, right so, look at this cut, you know, all rad.
Okay, and now the value of the objective function, yeah well, well, we are cutting
another part of this, you know, linear, linear programing space here, infeasible
solution, the feasible solution to the linear program.
Okay, and we get, we obtain a smaller parting top, and now the optimal
solution, one of the optimal solution to this linear program is also integral.
Okay, and if we are lucky now, the linear relaxation is going to get to this, okay?
And then we can stop, because at this point we are optimal for linear
relaxation, and both variables have integer value, okay, one and one.
Okay? So this is essentially the essense of.
you know, this cutting plane algorithm. You start from the beginning, you start
adding these cuts, re-optimizing. Adding these cuts, re-optimizing.
And you have the optimal solution to the linear relaxation which is now on a on a
on a on a vertex, which is all integral. Okay?
So, so today, so there are many ways of generating these cuts.
Okay? So and, and what are we going to do today
is look at one way, which are these Gomery cuts, okay?
And they are syntactic in the sense that the only thing we're going to do is look
at the tableau and derive the cut from the tableau, the simplex tableau, okay?
The assumption that I'm going to make here, okay, so I make a very simple
assumption here is that all variables take integer values.
This, of course, has been generalized by Lawrence Wolsey, and others, for, you
know, the case where this is not only integer values, they are beautiful
results in that area, but I want to talk about this, okay?
But they are in, you know, most software these days.
Okay? So what I'm going to show you is only,
make these assumptions, because that allows me to, you know, present the cut
in a simpler fashion. Okay.
So now, remember, the simpler algorithm is only, you know, dealing with this you
know basic feasible solution and remember while a basic feasible solution is your
express some of the basic variables in terms of the non-basic variables okay.
And so and obviously these b's here have to be greater or equal to 0.
Okay. And in a basic feasible solution the
value of the non-basic variables are going to be all 0.
And the value of the basic variables are going to be these b's.
Okay, so this is the basic feasible solution, this is the basic feasible
solution corresponding to this selection of basic variables and non-basic
variables. Okay, so we have this basic solution.
Obviously, if all the b's, you know, all the b's are integral, okay, are integer
values, then we are great, okay, so we have a solution, okay, to the myth.
Okay, but in practice, in general, it's not, it's not going to be the case, some
of these variables are going to be assigned fractional values okay, so we
have seen in the previous lecture that this linear programming reaction is
always trying to be cute, right? And making your life as miserable as
possible. Okay, and so in a sense here, what the
linear, so some of these values are going to be, some of these, some of these
b's are going to be fractional. Okay.
So let's assume for simplicity that b1 is fractional.
Which basically means that the value assigned to x1 is fractional.
Okay. So this is all that we can deduce a cut.
Which is a gomory cut. Okay.
So we'll talk about gomory later on. Okay?
So what we going to do is, we going to take, you know, we going to take this row
of the tableau. Okay?
And the first thing we going to do is, we going to take these coefficients there
and round them downwards. Okay?
The largest integer which is smaller than, which is large, wh, which, the
largest integer which is smaller than that value.
Okay, and so what we have now. We know that if run all these coefficent
downward that value is going to be smaller than the value that we have here
okay so we can rewrite that constraint as an equality now which is smaller than.
We are smaller or equal to be 1 now. But we have rounded all the coefficent
downward. And so all these coefficients now are
integer values right okay. So I haven't done anything right.
So this is like. Self evident truth.
Right? So, so what you see here is essentially a
valid inequality that I have. Okay?
And there is a very interesting property about this.
Right? So if you look at x1, it is feasible
solution, x1 is an integer value. [INAUDIBLE] This will be an integer.
Okay? Now this expression here has to be an
integer too. Why?
Because all these coefficients are integers okay and all the xi's are
integers so the whole thing has to be an integer okay?
So now since you know that this value here is an int okay so what do you no b1
is a fraction right but since this is an int you can strengthen that constraint
and make sure that, and this is still valid in the, you know, in the integer
solution to the, to the, to the MIP. Okay.
Okay, but in the feasible solution to the MIP, we now have that, essentially this
expression, that we have the beginning, okay, has to be smaller or equal to the
floor of b1, which is essentially the, you know rounding b1 downwards, okay.
So now, this is the Gomory Cut, okay, so what we are doing here is that we are
basically taking the coefficients here, okay, replace you know, rounding them
downwards we are taking the b, rounding it downwards and of course, this becomes
an inequality. Okay?
And so this is a cut okay. Now this cut, is varying obtusely.
The only thing that I have done are basic you know algebraic manipulations and then
exploiting the fact that these values are integers in the, in the.
In the solutions to the MIP. Okay?
So, it's valid and then it has this also beautiful property that it removes the
value. It prunes the basic feasible solutions of
the basic feasible solution which is the optimal value of the linear relaxation.
Okay. So why what but look at this thing right.
So in the basic feasible solution okay. So what we know okay is basically all
these non-basic variables have to be zero okay.
So if the non-basic variables have to be zero okay.
So x1 is going to be assigned to b1 and then the value here you know, this b1 is
going to be obviously greater than the floor of b1 because we assume that b1 was
fractional, okay? So essentially we have this beautiful
cut, okay, which is looking at the, looking at the you know, the optimal
solution to the linear program, finding a row which is fractional and then adding a
new constraint which removes that basic feasible solution.
Now if I remove that basic feasible solution without constraints, if I
re-optimize what's going to happen, if I put that constraint in, well good things
are going to happen. So,but before we do that I want to
reformulate this cut. Okay?
This is not typically what you do. So this is the, this is, this is the cut
but we going to reformulate it. In such a way that, you know, it's
actually better for, you know, numerical stability.
And so what we going to do, and so in a, in a, in a in a linear program, it's,
it's very nice if the variables are between zero and one, because we
typically deal with these things as floating points, and there are as many
floating points between zero and one as, outside, and so, outside zero and one.
So what we are going to do is we're going to take this constraint, okay, we,
so this is the original constraints, we are going to take the cut here and we are
going to subtract one from the other. Okay?
And so when we subtract one from the other, you'll see that the x1 is going to
disappear, obviously and then, then, you know, this value is going to be smaller
than the other one so what we get is that we get an inequality in the other
direction. Where you see here, basically the sum of
the fractional part of the coefficient times the axis and then the fractional
part of the right inside the b. Okay so in a sense think of the gomory
cut now as oh I take the tableau and I take the fractional part of all the
values, say the basic variables. Okay I take the fractional part here
Okay. So the value is you basically take and
the fractional part is simply the variable the coefficient minus you know,
the, the largest integer which is smaller than the floor of that particular
coefficient. And that has to be greater or equal,
okay, to the fractional part of the right-hand side, okay?
And that's typically the cut that we're going to use, okay?
And so, what are we going to do with this cut?
Well, we're going to put it inside the tableau now.
Okay, if you want to put it inside the tableau, you have to transform it into an
inequality. You take these slack variables that you
add. Okay?
You re express that as an inequality. You get s is equal to minus the
fractional part of the b1 of the, in that ta-, of in that tableau.
Okay? And then the fractional part of all the
other coefficients multiplying the non-basic variables.
And obviously when you look at these constraints you say okay?
It's not feasible but that's good. That's what you wanted.
You wanted that constraints which is not feasible otherwise you would stay at the
same place. You would still have the same, you know,
objective value for the linear, you know, relaxation but now, so you know that this
is not primal feasible, but obviously you turn your head and this is dual feasible.
Yes! You re-optimize the dual, and now you get
another relaxation. Right?
And it's the stronger relaxation because you have removed at least one of the
bases. Right?
And so the basically, that's what you do when you have Gomory cuts.
Okay, so you look at the tableau, you optimize the linear relaxation, okay.
So you get this linear relaxation, okay. Then you choose a row where the basic
variable is fractional, okay. So you know that.
That's not what you want. So you generate the Gomory cut, okay?
The Gomory cut generates this constraint which is primal and feasible, but is dual
feasible. You use a dual algorithm to re optimize,
okay? And you have a new value of the
relaxation. And you integrate this until, you know,
you basically form a solution which is all integral.
You know, all the integral values, you know all the values have integer values.
Or you can show that there are no feasible solution.
Okay, so that's the algorithm here, for solving MIP integer program using Gomory
cut, okay? Now, I want to illustrate that which as
you can see what it does on the simple example that I've shown you, okay?
So once again we start with this model you know, with, with the model over
there. Okay, I have my feet completely tangled
in you know, wires here, okay, so this is the basic, this is the model that I've
shown you. We re-express it in terms of equalities
and, of course, we transform the max into a min, okay, so we get these, these,
these constraints over there. So we have two new variable, x3 and x4,
okay, very important x3 and x4 because, you know, you, you, you see why in a
moment. Okay, but see that we have x3 and x4 and
you can express x3 in terms of x1 and x2, and x4 in terms of X1 and x2 as well,
okay and now we are trying to do the tableau of this thing, okay.
So this is the tableau, okay, so we see that at the beginning I put x3 and x4 in
bases, okay. So you see you see the value one over
there, is one over there. You see the b side on this side.
You see minus z over there. Okay, and you see, you know, the, the,
the objective function over there. Okay?
So, now what we are going to do is solve the linear relaxation.
We are going to take this tableau and do the simplex algorithm, this tableau.
And where we want to get is this point obviously.
That's geometrically where we want to go. Algebraically, this is what it's giving
you, okay? So value 3 over 2 okay?
That's what we wanted to find. The two variables which are in bases are
x1 and x2 okay? So x1 is equal to 1, x2 is equal to 3.5
okay? Which is exactly the point.
The algebra you know, is the same as the geometry, okay?
We are happy okay, and then you look at this tableau which is the tableau the
optimal value of the linear program right, okay.
Now, you look at this tableau when you see that the variable x2 is actually
given a fractional value, that's not good okay.
So, what you are going to do is take a cut okay, a Gomory Cut for that
particular row of the tableau okay. So, what the cut does, take the
fractional part of everyone of the coefficient okay, and multiply that by
the variables, the non basic variables. And I take the fractional part of the b
side and so the fractional part of the the sum of the fractional part of the
coefficients have to be greater than the fractional part of the b side.
Okay and you get this beautiful constraint which is a quarter of x3 plus
a quarter of x4 which is greater than or equal to one half okay and you look at
that chart and you say wow what does it mean, okay?
And of course, that's when I told you, you know, that it's easy to re express x3
and x4 in terms of x1 and x2, so we can take this cut and try to see what it
means in the original space. So you're going to take the value of x3,
which is in that system of equations, the value of x4, which is inside, which can
be re expressed in terms of that system of equation, you know, you re-express
these things here, and what you get is x2 is smaller or equal to 1.
Okay. Just massage this thing, okay, and you
get x2 is smaller or equal to 1. Which is what?
Which is the first cut that I've shown you before.
Okay, wow, that's great, right? So, what I do, is that essentially, you
know when you do this Gomory, you know, cut algorithm.
You basically add these new constraints, okay, with the slack variables.
Okay? So you see the slack variables, now,
which is which is in the basis okay. And you see of usually that value here is
minus 1/2 okay so that's not good. That's not primary feasible.
So you gotta re optimize using the dual simplex okay.
And then essentially what you will get, you will get to this spot.
Of course okay. And so this point corresponds to what?
X1 is about 2/3 right? And X2 is equal to 1.
Hopefully we get that in the tableau, and that's what we get, 2 3rds for x1, and
you know, x2 is equal to 1. Okay?
And we see once again the table, and the table is fine, except that when you look
at the row for x1, you know, x1 received the value 2 3rds.
Okay? So we have to generate a new cut.
Okay? So, we generate a new Gomory cut, and
this is going to be the cut, 2 3rd of x4 plus 2 3rd of s1 is greater than or equal
to 2 3rd. Okay?
Now, you look at this thing, and say, How did he get the value 2/3 for x1?
Okay, so look at this, because this is a 1 minus 1/3 of it.
Okay? Now, this is very simple, right?
So, -1/3, you run downwards. What is the largest integer value which
is you know smaller than this? This is minus 1, so you take minus 1/3
minus minus 1, which is plus 1, and that gives you 2/3, okay?
So that's how you get 2/3 for this particular constraint, okay?
Now, once again, you have these beautiful constraints, you have no clue what it
means, okay, it's 2/3 of x4 plus 2/3 of s1, these are two, one variables where
the slack introduced at the beginning, the other one with the slack introduced
by the cut, okay? the first, you know, the first cut.
So what do they mean? Essentially what do they mean when you
basically transform you know, using the definition of these variables you know,
when they were introduced, okay. It basically gives you the cut x1 minus
x2 is greater than 0, okay? Which is this beautiful cut here that we
saw before, okay? Now we re optimize and we get the optimal
solution. To this MIP, which is going to be this
beautiful point over here. It's an integer and we stop okay.
Now, this algorithm was invented in 1958 by Gomory, okay.
And obviously, at that point, it was considered as, you know, an amazing
achievement. Because essentially, you know, people
think, you know, people had solved linear program and that algorithm was telling
them, no, you can essentially generalize that to integer program, just by using
these beautiful cuts. Okay.
Now one other thing that you have to see here is that this is 1958, right.
So this is before, you know, complexity theory was invented.
Cook invented, you know, complexity theory, and p completeness in '70, or '70
was, I think 1970 or '72 okay, so essentially, what we don't know is that
the difference between linear programs and mixed integer program is a big gap,
right. So this is the gap between polynomial
time and then np completeness. So when you run this algorithm, what is
happening? Okay?
So what is happening is that you may generate potentially, an exponential
number of these cuts, right, otherwise, you know, these problems would be
polynomial. Okay, and so essentially at that point
when people realize that and also did a lot of computer experiment using this
algorithm, so that the conversion of this algorithm can be really, really slow, and
there were, you know, some other issues as well.
So, so that point this algorithm was mostly consider as a beautiful
theoretical result but not practical. Okay?
But science is like the linear relaxation, it has, you know, it's very
unpredicatable. Okay?
And so what happen is that these cuts were actually completely revived in the
90's by, you know, these people, so [UNKNOWN] and [UNKNOWN] Ceria, Cornuejol,
okay? In the, and, and what the, what this show
is that you can actually use this Gomory cut inside the branch and bound
algorithm. You have to be a little bit clever.
You don't want to introduce them one at a time.
You want to introduce them, you want to introduce all of them for the tableau at
the same time. You also don't want to introduce them at
every node. You skip some nodes and so on and so
forth. And they showed that they actually were
the best, that they were all perfect for every existing algorithm at that point.
Okay? That was part of the thesis of Sebastian.
And if you want to read more about this, it's very interesting, just, you know,
look at the article that Gerard Cornuejols has written on that.
So this is very interesting right. So Gomory Cuts were basically a really
you know a major breakthrough and then they become an essentially a tiny
[UNKNOWN] interesting feature and then they become essentially completely.
You know practical again and they are essentially integrated in all the
commercial software now for MIP solvers okay.
Of course you don't generate them all of them.
You only generate a sub set of them but they essentially are a big part of every
commercial MIP system since you know Sebastian, Edgar, Cornuejols and and I, I
don't know the first name of, of Natraj but these people actually did this
computational experiment. So, once again this is an interesting
story here. The science is beautiful, but there is
also a very interesting story personally and the story of
Of, you know, of Gomory is very interesting.
He, you know, after, after having doing a lot of science, he went to IBM, became an
IBM fellow. He revolutionized the way IBM did, you
know, research, you know, and then when he was, you know, at the mandatory age
for retirement he went to the Sloan Foundation and, you know, revised, you
know, and revolutionized the Sloan Foundation as well.
So you should read about him. It's very interesting.
And once again, you know, what you saw today is very interesting science and a
very interesting personal story at the same time.
Thank you.