The new method proposed by Zhuge Liang involved large cuts to Qi shields. Tai Shang Lao Jun warned that this might have negative consequences and suggested using another method to help find the weakest point. Zhuge Liang summoned the dragon of dimensions for assistance from the professors. So, Nu Zha is ready to make a big cut through this Qi shield in order to get closer to finding the weakest priest and he's just about to do this when Tai Shang Lao Jun says, "Hang on, hang on, wait a minute. So, if we cut through this shield, we're going to let out a whole lot of hell energy, which is going to weaken you considerably. And if that's the case, it might be that these priests may well be able to defeat you." So, we really want to be able to find this weakest integral point amongst the Qi shield but we're not allowed to employ this Branch and Bound, which requires cutting through the shield in a large way, so basically splitting the problem into two. So, if this is our MiniZinc model, we can't employ Branch and Bound, then how can we solve the same problem? So, we can rewrite our problem this way with this initial Simplex tableau, and notice we have done everything as normal except that we've multiplied the second constraint here by two so that we have all integer coefficients. And the important point about that is that now, there's all integer coefficients here, and we know that x, y, and z are integer vaiables, and it's very clear that all of the slack variables, s1, s2 and s3, will have to take integer values in any of these equations for them to hold. Alright, so if we now solve that using our Simplex method, we'll find this optimal objective and this point here which, of course, is not integral, so it doesn't correspond to one of the priests. That was our problem. If we have a look at the final Simplex tableaux, ??> it actually spells out this solution. We can see the objective value here and the values of the slack variables and the other variables, which are taking non-zero values. So, this is the resulting Simplex tableau, and you can see that the objective cannot be be further improved because, of course, these are non-negatives, y, s2, and s3, so we can only increase them, which will just decrease the objective. Alright, so what can we do? Let's have a look at this second constraint row here, which says that z, at the current point, is taking this value, four forty divided by nine, a non-integral value. So, we can rewrite this equation just by moving terms around. So we can rewrite it to z plus five-ninths y plus two-ninths s2 minus one-third s3 equals forty divided by nine. That's just moving all of these terms here over to the other side. Then we can sort of collect together terms. So, we can collect together all the integer terms here, so we take z minus s3, so we're going to add a copy of s3, so subtract one here and add one here so that we end up with two-thirds s3 left over here. We're going to take the integer part of that, which is four, and move it over here, and leave the fractional part left over, which is four-ninths. So you can see that 36-ninths plus four nights is forty-ninths. And we split our problem into two parts. Here's an integer part and here is a fractional part. So we know that in any solution, this thing must be an integer value. And we know that this thing must be a positive value, because these are all non-negative variables and we're multiplying by positive fractions. And really, that shows us that the only way we can get our four-ninths is to get the four-ninths out of this part here, alright? So the four-ninths, the fractional value that's left over, can only come out of this expression here, because this is an integer expression. It can't create any fractional value. So if we think about this in more general terms, if we have some equation which has an integer expression and a fractional expression, which is all of strictly positive fractions, so we cannot have some subtraction of them, and we have this fractional value here, which is also positive, then it must be the case that this fractional expression here, F is greater than or equal to f, because it's only the F that can create this fractional value. So, in our example, here is the integer part, here is the fractional part which is definitely strictly positive, and here is the fractional part left over. And from this, we can gather that this four-ninths has to be created by this fractional part. So it could be that the whole thing adds up to exactly four-ninths, or it could be one plus four-ninths, or two plus four-ninths, or whatever. But it's certainly bigger than or equal to four-ninths. So we know this constraint is a consequence of the original row that we looked at. So, we've generated a Gomory Cut. The Gomory Cut here said that these fractional part had to be greater than or equal to four-ninths, we can multiply through and get this integer form. And in fact, we can substitute for the slack variables s2 and s3 to just get back an equation in terms of the original variables, 2x plus y plus 2z is less than equal to 24. Now, the important part of adding this Gomory Cut to our original problem is, the cut certainly removes the optimal solution to the original linear relaxation, because it's going to prevent that constraint from holding at optimality. And all the feasible solutions of the original MIP are retained. So, what we're adding here is a cut which can't cut off any integer solutions, because it was just a consequence of some equation of the row, which is already a consequence of the original problem, and we made sure that its reasoning was correct. It was a true consequence of that constraint so it can't get rid of any solution. We used the integrality of the variables in order to generate this cut. So, we've left behind all the integer solutions, but we may have cut off some non-integer solutions, and that's the important part. So in general, we can look for, in a Simplex tableau, if we see a row like this, x_i equals b plus f, so we've got a non-integer solution in this sol form for x_i, and some other part. So, the b is the integer part of the current solution for x_i, and the f is this fractional part between zero and one. We can rewrite this just as a form, move all the equation onto this side. Then we can take the floor of all of these coefficients here. So that'll certainly be an integer. So this is really getting the integer part of this a_i, x_i. And since we have the floor here, we subtract it here, so we still got the same equation. And the key thing to notice is that this expression here, a_i minus the floor of a_i, is certainly a fraction or zero if a_i is already an integer, and it's certainly positive, non-negative. It's a fraction between zero and one. Alright, once we've done that, we know since this can only generate integers, then this part has to generate the fractional part. So we know it has to be greater than equal to f. And that's exactly the Gomory Cut in general. But notice also, we can build a Gomory Cut by taking any row of the Simplex tableaux as long as this is not an integer. Of course, if this is an integer, then we're not going to learn anything here because this f will be zero. And if the objective value is not an integral as it was in our example, we could also use that to generate a Gomory cut. So, we can actually use Gomory cuts to completely solve an integer linear program. So we just solve our linear program, we add Gomory cuts from the LP basis, and we resolve. Right. We're going to cut off part of the solution and if we keep doing this forever and ever eventually, in a finite amount of time, we will actually find the LP solution is forced to be integral. And the problem with doing this in general is that it may not converge very fast, it might take a lot of iterations through this loop to get an integral solution, and the other thing is that deciding which of the Gomory cuts to add is not so obvious. So some of them will be very useful about driving us towards an integral solution and some not, and a far the problem is that as we add more and more Gomory cuts actually the coefficients of our constraints tend to grow, and they grow very fast, and then that makes it hard for actually our solvers to solve because solving with big coefficients starts to get mathematical inaccuracies happening. Alright. We've generated this Gomory cuts, we can introduce that into our linear programming model by adding the Slack variable, and then we can resolve the LP, and then in this case we'll get to this solution and if we look at this very nicely we've actually generated an integral solution. So x takes value 8, z takes value 4 and y takes value 0 and we found a solution, right? An objective of 36, and if we look at adding that cutting, what we've done is cut off a little bit of the polytype type, the original polytype and if we zoom in we can see here we have this little new facet that's come from cutting that off and we've ended up with the simplex at this point here, which is an optimal solution. So it turns out that actually there are other optimal solutions so exactly everywhere along this line is also optimal. So we may not have been lucky. The simplex may have ended up in this point, as we representing this point because this is an equally good solution from the real numbers perspective, it's not so good for what we're looking for because we're looking for an integer solution. So we may end up here and may end up needing to do more cuts. So remember the final simplex of the original LP had another row which had a non-integral solution here for x, we took the z row before, we can generate a Gomory cut from that. So we can go through exactly the same process, we can rewrite like this way, we can separate it into an integer part and a fractional part equals this fraction and that would generate us another Gomory cut in this case this one, and in terms of the original variables if we substitute that these slack variables we get this one instead. If we did that, if we chose to add this Gomory cut instead, we can resolve the LP and we get to this solution and you can see it's not integral. So we haven't really solved our problem yet and if we look at what's happened in our polytope, then this cut has added another facet here, but none of the points on this intersection were integral so we're not going to find an integral optimal at this point. So we were lucky in our example we picked the right Gomory cut and in fact we are lucky also that the simplex ended up in an optimal integral point instead of an equally good non-integral point. So here the simplex has ended us up here which is non-integral, and all the other points in this case, this is the optimal, but all of the other points are also non-integral. So Gomory cuts is the most basic form of cutting plane, we can extend them to mixed integer programs, so we assume the variables are real and not integer. And obviously that tends to generate weaker cuts because if we have non-integral variables and we can't use this integer reasoning. But there are other important general classes of cuts, mixed integer rounding cuts, a general way of building a cut for arbitrary mixed integer programs and Lift and Project Cuts is another way. And the most important thing though is with cuts in general is that we can combine these cutting plane methods with branch and bound and that obtains this method we call Branch and Cut and the nice thing about Branch and Cut is that if we just use pure cutting plane methods then we typically get this explosion of coefficients, the coefficients get bigger and bigger and bigger and it gets harder and harder to solve the LP. But if we combine the power of search, branch and bound with cutting planes we can get very useful cuts which will quickly drive us to integer solutions and we won't just be forced to generate many many more until we only get an optimal solution by cutting planes. So Branch and Cut is we take our branch and bound algorithm which we've seen before, we solve the relaxation giving some solution, if it's integer value we're finished, otherwise we add the cutting planes to P and resolve and sort of go around this loop any number of times we want to, and then we get to our branching stage where we pick a variable x_i which is integer which takes a non-integer value and then we break into two problems and then solve them using the same way. So Branch and Cut is just a minor extension of branch and bound where they have the option to add cutting planes in the middle of any of these searches. So cutting planes are a vital component of modern commercial MIP solvers and there's these general cutting plane methods like Gomory cuts, Mixed Integer Rounding Cuts, and Lift and Project cuts, and there's other cutting plane methods which are based on specific structures like Knapsack Cover Cuts and Clique Cuts. And it's interesting that Gomory cuts were the first cutting plane method ever devised and though initially thought to be impractical, it's sort of interesting that they could actually be used as a way of solving the problem, but then they saw this explosion of coefficients and made them look impractical in general and actually now there a very important component in MIP and part of this reason is that if we use Gomory cuts in Branch and Cuts so we're not just only using Gomory cuts to solve the problem then actually they can give us very good cutting information without causing large amounts of instability. So in summary cutting planes are an essential method for solving MIPs. So they're used in presolving where we do a lot of structural cuts can be applied to simplify the problem and they are used during search where we can do cutting methods like Gomory cuts to tighten the LP relaxation. And so they're an essential part of how MIP solvers work, but there's always a lot more to learn about MIP.
