Nu Zha attempted to attack the weakest tower's priest according to Zhuge Liang's calculation, only to find that there was no priest at this particular spot. It turned out, the Grandmaster of Heaven had secretly shifted the Qi shields, and so, the method Zhuge Liang used to find out the weakest point failed. Nu Zha headed back to Zhuge Liang and asked him to recompute the weakest point. Zhuge Liang summoned the dragon of dimensions for assistance from the professors. So, using the calculation of Zhuge Liang, Nu Zha attacked the Qi shield, but he was surprised to find that it wasn't the weakest spot. The priest who was there was very strong. So, what had gone wrong? So, Tai Shang Lao Jun looked at what had happened and realised that the Grandmaster of Heavens had actually subtly shifted the Qi shields. So that was fine. I've shifted the Qi shields. Once I worked out the new Qi shield, I re-ran the algorithm to find the weakest point again, and Nu Zha went to attack. But this time, he found nobody there. So, what's going on? So, the Grandmaster of Heaven has adjusted one of the Qi shields. And in fact, in this case, the weakest point of the Qi shields is not on one of the integral points, it's not on the grid anymore. So it's really changed the task now. So Nu Zha needs to find the weakest spot amongst all the integral points inside the Qi shield. He needs to find the weakest of the priests inside the Qi shield, but it won't be one of these vertexes. So, all that's changed in our model is we've slightly changed the value of one coefficient in the problem. When we do that, when we run our Simplex algorithm, we get this as the optimal solution, alright? So, this is not an integral point, there's no priest at this point, so what should we do? The last time, we were lucky. It turned out that the vertex points were all on integral points, and so, there was a priest there. So, we've changed our problem. We need to find the weakest priest who's standing in the grid at the integral points within the Qi shield. And what this is, is a mixed integer linear program. So, here is our slightly revised polytope of the Qi shield, and you can see that the intersection points aren't necessarily integral. And so, the priests that we're looking at, all the priest lie within this polytope. So that's all these red dots that you can see here where each of the priests in the 10,000 formation stand. And if we look at this, what is the optimal vertex in terms of the linear program, then you can see it's not integral. So, what is the problem we're trying to solve? So it's just as before. We've got a linear objective and linear system of constraints, and then we've got some other variables, in this case, all of our variables have to be integer. So this set of variables S have to be constrained to be integers. And in our case, all of the variables that we're talking about have to be constrained to be integers. So, once we do this, solving the problem is actually NP-hard. Because in fact, even solving a single linear equation on 0-1 integers is NP-complete. So this is the subset sum problem. So if I give you a set of integers, so these are fixed integers and some other integer, S_0, and I say, find me a subset of these which adds up to exactly S_0, then I can write this down as a mixed integer program. So I got all of these x_i's which are between zero and one, and I just need that sum, so take the value one if I'm picking the value S_i, and take the value zero if I'm not picking it, and then this single equation here is the subset sum problem, which is an NP-complete problem. So, we've really upped our difficulty by adding this integrality constraint. So how are we going to solve it? Well, basically, we're going to use linear relaxation. We're going to ignore this integrality, and treat this mixed integer program as a linear program, because we know how to solve a linear program. And then, we're going to see if we can fix the result. So if we take the simple example here, and the optimal solution, if the objective is like this, is this point here which is (1.857, 0). And the problem is, if we look at the nearest integer solution, well actually, it's infeasible, so that's not good. If we just rounded the solution down, we'd get this one which is sub-optimal because the true optimal we're looking for is this guy here. So, how can we go from this LP optimal to find the true integer optimal? That's the question. So, what we do know is that all feasible points for the mixed integer program are feasible in the linear relaxation, right? So linear relaxation, the area inside this polytope, is a larger number of points than just the places in the integral matrix inside that where the priests stand. So we do know that the integer valued optimal of the relaxation is an optimal solution of the MIP, but not necessary vice versa. Okay, so how are we going to solve the MIPs? Well, we can naively just enumerate the feasible points of the relaxed problem. Of course, there is way too many points to do that. So we are going to have to do better. And the way we're going to do this is we're going to repeatedly solve improved relaxations with the Simplex, and then we're going to branch by adding constraints until it happens that the true integer optimal solution is on a vertex of this newly improved relaxation. So, what we're going to do is what's called branch and bound. We take a mixed integer program, P We solve the linear relaxation of P using the Simplex, let's say, giving theta, so a theta is a solution. So if the solution is integer valued for every integer variable, we're finished, right? We've actually found the optimal solution, theta is the optimal of the linear relaxation, then its certainly optimal-- because it actually satisfies integer constraints as well, it's optimal for the entire problem. Otherwise, there are going to be some integer variable which takes a non-integer value, v, let's say. We're going to create two sub-problems. So we're going to either say that x_i is less than equal or equal to the floor of v. So it's basically, this is going to be something like 1.75, this is going to say x is less than or equal to one, or x_i is greater than or equal to the ceiling of v, so this is 1.75, it's going to say it's greater than or equal to two. So basically, what we're doing is both of these problems remove this optimal value. There's no way x_i can take this value because these two constraints, this constraint and this constraint, remove it. And we haven't removed any non-integer solutions because x_i can't take any integer values in between the floor of v and the ceiling of v. So, we haven't removed any solution, we just split the solution space into two. Now, we can solve each of these sub-problems recursively. And the solution to P, the original problem, is the better of the two solutions of P_below, and P_above. Alright, it's straightforward, or at least, it seems so. Alright, so let's try it. Here is our original problem with the Qi shields, and our objective here is at this point here, which is non-integral. So, Nu Zha is going to pick, let's say he picks x, which is taking a non-integral value. We're going to split on the x is less than equal to seven or greater than equal to eight. So that'll certainly remove this possibility. So if he cuts through and adds this x less than or equal to seven constraint into the problem effectively, he's going to get this little face here, and he's going to get this little part of the original face leftover, and here is a new polytope. And again, we can find the optimal point on this polytope which will be here, which is this x is seven, y is zero, and z is non-integral, so we haven't solved our problem. So now, we're going to split on z. Let's say, we can say z is less than or equal to four or greater than or equal to five. So, let's add this z less than or equal to four constraint, cut through the polytope like that. Alright, so now, we get this new polytope. We solve this again. Now, the optimal solution again is not integral. Now, it's non-integral in terms of y. So we're going to split on y. That's the optimal point in the polytope. We're going to split on y, we're going to split either y is less than or equal to one or y is greater than or equal to two. So, once we do y is less than or equal to one, then, we'll get this remaining polytope, it's a very simple polytope in fact. And in this case, we're guaranteed all of the vertexes of this polytope are integral. We get an integral solution. So we finally found a solution to our problem. And this is a solution to the entire problem but not necessarily the optimal one. And so currently, the best objective we found is this solution which is 34. So now we have to go back and try all of the other possibilities. So we have to look at the other side. We can try y grater than or equal to two, maybe there's a better solution in this half. So we get this much bigger polytope. And we can see, we get this solution which is non integral, so we have to keep going. Right. So if we look at the whole branch and bound decision tree that we would take. In this we started here, and that we got a nonequal solution. We split on X and tried this branch first, and then we split on Z and tried this branch, then we split on Y and next we actually got an integral solution, with an objective of 34. But then we had to try the other half of Y, and then we got non-integral we had to split on Z, we non-integral we split on Y. This time, we got a solution but it wasn't better than the previous one, and we split on Y the other direction, then we again found another solution but it wasn't better. We keep going, and you can see, we do a lot of search throughout this tree. Keep going. All kinds of things to look at. Now, eventually after searching all of this sub tree we try the other original choice for Z in the other direction. And after many more steps, we eventually say, oh there's no better solutions in here, then we go up and try this, a different way for X. And in fact, immediately find an optimal solution which is actually better than the one we've seen before. And we found our best solution and there's no more choices left, so we're finished. Okay. So that is in fact the optimal solution of 36 at this position X is eight and Z is four. So, if we look back at our original polytope, that was the original polytope, we were very close to it, except that we chose to go the wrong way first, and it took us a long time to find this optimal solution. Alright. But, in fact, we haven't been very clever in what we're doing here. So, it's not the case that every sub-problem we looked at there needs to be explored. So, there's-- when we're doing our search, there are reasons we can stop. So we can get to a leaf. So if the problem is unsatisfiable, if the constraints have no solution we know there's no real solution, then there's no integer solution, we can just stop. If the solution we get is integer, for all the integer variables, then we know that we've got the optimal for that sub-problem, and we can stop. But the other reason we can stop is that the relaxed optimal is worse than the best solution that we've found already. And this is what we call a fathomed sub problem. So obviously, if we have the best solution we can get in this polytope is no better than a solution we've already found. Then we know that no way of searching in this polytope will give me a better integer solution. Because the best real solution is in fact not better than the best solution we've already found. So that means that we can just stop at that point. So, let's go through our decision tree again, actually doing branching bound with fathoming, which is the normal way we run it. So when we go down to here, we found the best objective is 34. Now we branch to here, of course we solved the linear program and we find, the best real solution has a value of 33.5. That means that there's no integer solution better than 33.5 in this entire tree. So we don't need to look at that entire tree. We can stop at this point, and not go any further. So we just stop there. That can be fathomed. So now we come over to here, again when we get down to here we find the linear program solution is 34, which means we can't be better than the solution we've already found, we could be equal but it couldn't be better. So again there's no point in investigating any of this tree here. So we should stop. And that basically gets us almost directly to get back to the right branch we should have tacken, which is branching on X, greater than or equal to eight, and then we find an optimal solution, and we're finished. And you can see that the Fathomed decision tree is much, much smaller, than if we hadn't used fathoming. Okay. But there were some decisions to be made. So search just like in C.P., search in MIP is very important. So which integer variable should we branch on, and which sub-problem should we try first? Should we go down or should we go up? So branching for many years use the most fractional variables, so basically the variable which took a value closest to the middle. But actually it turns out this is really really bad. In fact choosing a random variable which is non-integral, is actually better than this. In recent times, all modern MIP solvers use some kind of strong branching, or pseudo cost branching. The strong branching is a fairly obvious thing. What will we do? We'll actually evaluate the objective of the two sides, if I go this way or this way and see, which one gives you the biggest increase in objective value. Right. So basically you are branching you're going to one which looks like the better option. It turns out that strong branching is very expensive, because basically for every variable we have to calculate two linear programs at each node. So that's very very expensive. So in practice we use some kind of pseudo cost branching, which is basically we estimate the value that the strong branching will give for each variable, and then we choose the one with the best estimate. And the way we do this estimation is basically historically at the start of the tree will typically do some kind of strong branching, because we can then gain some information about each variables pseudo cost and then later on during the tree. We will just see which ones we actually took and how they worked, and use that to calculate which variables are most likely to give us the biggest advantage. So modern MIP Solvers are actually incredibly fast and surprisingly scalable. They can handle millions of constraints and millions of variables. And they use other things that we haven't talked about, cutting plane algorithms, which generate their own constraints on the fly and we'll talk about those in the next section. Diving algorithms, so they'll try to find a good solution very quickly, because that will help the branch and bound search and other parts of their search. They've got some other clever autonomous search not just pseudo cost branching, but they also use activity based search and other things. And they also include, say CP propagation. So, a modern MIP solver will do all the propagation that a CP solver can do on the linears. And they'll also go around to detect special linear structures. So like finding globals in the linear constraints they are given, such as knapsack like constraints or, all different cleek constraints etc. So modern MIP solvers are a wonder to behold, and they can solve very very big problems. So in summary we've talked about Mixed Integer Programs, and this is the basically the most solved form of discrete optimisations. So Mixed Integer Programs are very widely used for solving discrete optimisation problems. And branch and bound is really the basis of this MIP solving. We should say it uses the dual simplex, because we're solving one LP and we're adding one more constraint, then we resolve that new linear program using the dual simplex, because that's designed for adding an extra constraint. And in general these modern MIP solvers are very effective and their big advantage over CP solver is that they know where to look for good solutions. So, a MIP solver is driving to where it knows good solutions are, because that's where the linear programming relaxation is telling us and it is generating both upper and lower bounds on the objective, and this allows it to reason about the search space and cuts off lots of space. So there's a lot more to learn about MIP, there's not much we can cover in this short course, and I invite you to go and look at more information. And that brings us to the end of this section.
