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.
