Well, welcome to another summary of module three of course three. Jimmy, what's happening in the story? Well, Zhuge Liang was teleported to another point in time, and he met Nadja. And at that time, Nadja and Titan Aojin, they had to battle against the sneaky grandmaster of heaven, and then the grandmaster of heaven was defending using the 10,000 immortal formation, as well as the mysterious chi 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 solvers, solve discrete optimization problems. But we are going to do that in a few steps because what sits behind a mixed integer programming solver is a linear solver. Okay. That the first thing is the two-phase simplex algorithm. Absolutely, so linear programming ends up doing two things. First, well, it's an optimization algorithm, but in fact, we use the same algorithm in order to find the first solution. So, it works from moving on 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 optimization problem. Exactly, that's a very good question. Because, actually once we solve discrete optimization problems, we can end up adding 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 since we like our inference that the CP solver does. 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 space 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 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 optimization problem, we're going to have to do some kind of search. That's for sure. I think we also talk about cutting planes. Absolutely, another important part of mixing your programming solvers are cutting plane methods which basically allow us to cut off part of the polytopes. 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 or 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. That's the most simple cutting plane algorithm. And we can use it entirely to solve a mixed integer programming problem. Absolutely. In fact. Do we ever do it? No, we don't. That was the interesting thing when Gomory first introduced it. We thought it would never be practical but actually, once we added in when we combine 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 our 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 they're full of things which are linear. So we talked 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 handling. But the stories 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 he will have to minimize the cost, the money that he is spending in getting all of the arrows he wants, right? Yeah. 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 the MIP server. 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 server than if you just write a model which is targeted at a CP server. But it turns out that this exercise would help us to build a better CP model as well. Exactly. If we then take the insights we get from that and make 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.
