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.