0:00

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.

11:44

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.