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.

Â