Okay, so that's almost the end of today's lecture. Today we mentioned about branch and bound, okay. In this algorithm basically we have an integer problem. Maybe linear relaxation, solve it, if needed, create to solve problems and keep doing during this process. So the thing is that using branch and bound to solve a problem is just that way. But if you want to implement it into the practice, you need to take a look at a few things more. So we know how to use groby to do this. We know how to write programs to invoke grobypy, to write your Python program to combine everything into a single program. You know how to decouple models and the data. So that's all good. One thing that you may want to also know is to take a look at this part. So this is a screenshot, that when you are trying to use groby to solve your integer program that you may see. So in this particular screenshot, there are several things to take a look. So first we are happy, optimal solution found a bra bra bra on this labels that we are done. But there are also some interesting to observe. So first, you may see that the optimal solution is 2.68 bra bra and you also see some values here. Okay? These are some feasible solutions found during the process. So, basically, we are trying to do maximization. So during the process at some node, we may find some current optimal solution. And then later, we have some other node finding a better solution. So, you may see that we first find the solution and then we find a better one and eventually we find a best one. So, you too can see this process. And also, here, you may see several things about gap. The gap percentage goes from 19 bra bra bra, to 8 bra bra, to 4, to 2, 0, and eventually gets to 0%. So understand me. Well, it basically says that when you are solving your integer program, that say this is time or iterations or a number of nodes, okay? And this is objective value. Integer programming or branching bound will first give you an observation or estimation about a bound. Which is the best you may do in a maximization problem. So originally you don't have solutions. At some point you get a feasible solution. This is your first solution. In this particular example, it may be these 2. This may be this particular solution, which is around 250, 50 100. And then a few iterations later you get to a better solution. And if the solution is found by the solver to be the same as the bound, then the solution process will stop. And tell you that this is optimal. And you may see that the bound also changes from time to time. Okay. So this somehow means you are keeping doing the iterations. Sometimes you are having a better solution, sometimes the bound is going to decrease, decrease and decrease. So maybe the most important thing that you want to ask is, well, I'm trying to solve a problem. I don't know where is an optimal solution? That's why I need to solve it, right? I don't know were is an optimal solution, then how could I know whether there is a bound or not? So this really relies on the relationship between integer programming and linear programming. To try to solve an integer program and you know, there is related linear program, which is the linear relaxation. The linear relaxation provides an upper bound. So the bound here can be provided by linear relaxation, right? Because if you relax those integer constraints, you get an upper bound of your objective value for this maximization problem. So that's how groby may estimate was the maximum possible gap between your solution, the currently found solution, and its theoretical upper bound. It's because that you know, linear relaxation provides an upper bound, so that you may do this estimation. So that groby solver eventually knows when to stop. So because we are still at the beginning stage, we don't talk about too many theories too advanced things. So I cannot get into more details about this particular bounding whatever thing. So, I need to stop here. But I hope the very brief discussion gave you an idea about how the solver works. We all know that during the whole process of friendship bound, you will keep finding better solutions, better solutions, better solutions. But a very good thing is that, when you are solving integer programs, you not only get a candidate solution. You not only get feasible solutions. You also get estimations about how far this current solution is how far it is from the optimal solution. Or a theoretical upper bound. This helps you estimate how good your solution is. This may guide your search direction, and at least may tell the solver when to stop. Well, that's some details about the implementations. Okay, so that's the end for today's lecture. See you next time. [MUSIC]
