So finally, we want to add some remarks to the whole process. So pretty much when we are doing all of this, we want to evaluate the difference between an optimal solution and our proposed solution. But unfortunately, the fact is that the optimal solution is just too hard to be calculated. So that's why we sort to some kind of upper bound or lower bound for the optimal solution. So that's how people do in practice and then that's why some people they refer to the gap between a reported solution and that theoretical upper bound or lower bound as the definition for optimality gap. So if you read some articles, websites, textbooks, you may see different definitions for the optimality gap. But anyway, the idea is just there. If you have an optimal solution compare with that. Otherwise compare with its upper bound or lower bound according to whether you are solving a maximization problem or minimization problem. That's for average performance guarantee. Some people actually they look for worst-case performance guaranteed. What does that mean? That means, whenever we have a heuristic algorithm, we know it's not going to generate an optimal solution and that means that z ALG is going to be for a maximization problem is going to be no greater than z star. We know that. But we also try to prove a worst-case performance guarantee, saying that for any for any possible random instances, for any instance, our zALG is not going to be too small, okay? It's going to be that the ratio between zALG and the z star is going to be greater than or equal to fun factor typically denoted as alpha. So for example, your alpha may be 80%, 75%. That means your zALG can be small, but it will not be too small. It will not be lower than 75% of your optimal solution. That may be some properties that we may prove from time to time. But unfortunately, this is very good, but difficult to do. So in this lecture, I don't plan to do that. I want and all I can do is that I want to highlight that some people are working with worst case performance guarantee. So we don't have time to talk about this. So if you are interested, maybe you may want to take some further courses. Designing or proposing a heuristic algorithm is always simple. You may have yours I may have mine, you may propose 1000s or hundreds of different versions of your heuristic. That's simple. What's difficult is a rigorous evaluation or rigorous analysis. That's actually something which is hard, okay? So if you don't ever have learned anything about integer programming, branch and bound linear relaxation, you may see that you are still able to design heuristic algorithms for most of your real world problems. In the real world, you may have scheduling problems, facility location problems, inventory problems, production problems, whatever problems for all these optimization problems, even if it is very difficult. You may always design heuristic algorithms by yourself some kind of greedy approach some kind of role based approach, whatever they may still be good. The only thing is that you don't know whether it is good. Only if you have integer programming, only if you are able to find an optimal solution, then you may evaluate how good your algorithm is, right, by having a benchmark or if an optimal solution is unable to be obtained, you have an upper bound or lower bound. How to do that to get an upper bound or lower bound of an optimal solution? Actually, it's very hard, only if you know that the linear relaxation provides that bound. Then you have it, okay. There are some other more advanced ways to find upper bounds and lower bounds, but linear relaxations for integer program is always one good candidates. Okay, so that's how we may evaluate we may really rigorously evaluate our heuristic algorithms, you have a heuristic algorithms. Then I write down the mathematical formulation for our proposed problems. Then I may get an upper bound, lower bound by solving the linear relaxation, then I may do some benchmarking and see whether our algorithm is really good or not. So that's the whole idea of doing rigorous evaluation, okay? If you don't know integer programming, in many cases, you don't have an easy way to do the rigorous evaluation. And that's one another reason why integer programming or mathematical programming is useful. That's the end for this lecture.
