Well, welcome to the module summary of module three of course three. Jimmy, what's happening in the story? Well, Zhuge Liang was headed to another point in time and he met Ne Zha. And at that time, Ne Zha and Tai Shang Lao Jun, they had to battle against the sneaky grand master of heaven. And then, the grand master of heaven was defending using the 10,000 immortal formation, as well as the mysterious G shield. So, in terms of technical content, I think we are introducing a new approach to solving. Absolutely. So, we're beginning to look at how Mixed-Integer Programming solver solves discrete optimisation problems, but we're going to do that in a few steps because what sits behind a mixed-integer programming solver is a linear solver. Okay. The first thing is the two phase simplex algorithm. Absolutely. So, linear programming ends up doing two things. First, it's an optimisation algorithm, but in fact, we use the same algorithm in order to find a first solution. So, it works from moving from one solution to another, but in order to get a first solution, we actually use the same algorithm. So, that's the two phase simplex algorithm. Well, the simplex algorithm is actually for solving continuous problem. Why do we care? Because we are solving discrete optimisation problem. Exactly. Well, it's a very good question because actually, once we solve discrete optimisation problems, we're going to end up having integer variables and it's going to force us to branch. And that's what gives us mixed-integer programming. Right? So, we end up using linear programming basically as a check at each node. It essentially like our inference that the CP is over dose, instead we do this linear programming check at each node to find a solution, which might not be an integer solution. And if it isn't, then we're going to branch, we're going to basically split the search phase to remove that solution and keep going until we find the best integer solution. So, this is still called branch and bound? Exactly. It is a form of branch and bound. We keep track of the best integer solution we've found so far. And in fact, in mixed-integer programming solvers, we can actually prune away large parts of the search space because the linear programming relaxation will tell us, we're never going to find a better solution in this part of the search space. So, the guessing part is branching. Yes. Absolutely. In any kind of discrete optimisation problem, we're going to have to do some kind of search. That's crucial. I think we also talk about cutting planes. Absolutely. Another important part of mixed-integer programming solvers are cutting plane methods, which basically allow us to cut off part of the polytope. So, there's a linear programming polytope, which is a relaxation of the actual problem we're trying to solve. And what we're trying to do is cut off parts which don't have any integer points in them, but make us get a better view of what's going on in terms of integer constraints that we're dealing with. So, I think we introduced Gomory cut. Absolutely, it's nice simple, cutting plane algorithm. And we could use it entirely to solve a mixed-integer programming problem. In fact, do we ever do it? No, we don't. I mean that was the interesting thing when Gomory first introduced that he thought would never be practical but actually once we add it in when we bind it with branching. Gomory cuts are very important and other kinds of cuts. Right. So, that's branch and cut. Exactly. So, branch and cut is a very powerful method, which is used in all of the most powerful mixed-integer programming solvers. We also looked remember at actually how MiniZinc talks to a mixed-integer programming solver because mixed-integer programming solvers only take linear constraints and when we write down MiniZinc models there. Full of things which are linear. So, we talk about how that conversion happened as well. Okay, how about the workshop? Yes. So, in the workshop, we have to look at how we can convert or how we can build a model directly using linear constraints only. Well, the story is that you know how he actually has to buy arrows from the market and because of the special way of using those buy X get Y free voucher thing, how you will have to minimise the cost, the money that he's spending in getting all the arrows he wants, right? So again, this is a different kind of workshop that we've seen in previous courses because we're going to actually give you a CP model, which you can actually use to run a MIP solver. But you need to build a direct MIP model only using linear constraints and then you should be able to see that you can build a model, which will run much faster on a MIP solver. Then, if you just write a model which is targeted at a CP solver. And it turns out that this exercise will help us to build a better CP model as well. Exactly. If we then take the insights we get from that and map them back to our CP model, we can actually improve that as well. And so that brings us to the end of module three summary.
