We just introduced branch and bound the general idea and gave you some examples. I hope the process is somehow makes sense, and here we want to have some remarks. So the first thing is that somehow you may from time to time, see that when you are choosing the next node to solve, the next node to branch on or the next subproblem to deal with, you'll sometimes have multiple solutions. For example, when we have one node as the root and therefore we add constraints to get two subproblems. You may either solve this one or that one, so you have actually two options. Suppose you choose the first one subproblem 2, and then suppose subproblem 2 gives you another two subproblems, now you would have three subproblems to choose from. Then in this case, somehow, if you are implementing an algorithm, you need to specify a way to determine which node to select from as the next one. So in this case, they are typically two ways to deal with that. There are actually many different ways. No one can guarantee you whether one way is always better than the other way. But here are two typical ways that are somewhat makes sense. So one common approach, first is to branch the node with the highest objective value. We are talking about a maximization problem. So why is that? Let's say, here we have two subproblems so both are fractional. Suppose here the value is 40.2, for the other is 98.3 suppose, then obviously in this rule we will solve the second one before we solve the first one. The reason is that if we are trying to solve a problem and keep branching, then any IP feasible solution is going to have a value less than or equal to 98. So it's somewhat more possible to having a solution that is better than 40.2, is that right? But on the other hand, if you try to move on to the first side, if you are lucky to get a feasible solution then in that IP feasible problem is going to be less than or equal to 40.2. So if that's the case, then there's no way for you to generate a solution that is better than 98.3, and obviously is also less likely for you to eventually get an optimal solution. So in short, when you are seeing two subproblems and then they have different objective values, it's more likely for the larger route to give you the eventually optimal solution under its subtree. So that's the idea. Another idea is here, we are going to say once a node is branched, all it's descendants are branched before any non-descendant. So what's that? The idea is the following, suppose we do this one first and get its descendants. Then in any case, we will finish this particular subtree before we try anything on the other subtree. So that means if we choose this one, then we will move on and then if we choose this one we will move on and then suppose that is dead, we will choose this one. We move on, that is dead and then we do this one, this is dead only after the whole subtree here has been done, then we move to the other subtree. So you may want to ask, why do we want to do that? There's also a reason, typically when we are still here, when we are still at higher level, we get fractional solutions. So that's why we need to keep adding constraints because those constraints typically set the values to be integers. So that means we keep branching along one direction is going to give us IP feasible solution faster. Instead of jumping amongst subtrees focusing on one subtree and keep doing that until the end, it's easier to get a feasible solution. So if that's the case, then it will be easier for us to get a lower bound for maximization problem. It's easier to get a feasible solution that help us cut some branches instead of solving all these nodes. So that's the reason behind the second approach. So no one can say whether this y is better than that one or that y is better than this one. But anyway, there are still many researchers talking about this and doing research on this and when we are trying to use a branch and bound we somehow need to know this issue exists. Choosing a variable to branch on is also a challenging task. So you may already observe that previously in our second example here after we solve the root, they are two variables that are fractional. Sometimes we choose the first one, sometimes we choose the second one. Somehow there is also a rule to help us determine which one to choose from. But again is out of the scope of this course, so we're going to ignore this idea. Then the branch and bound algorithm there's a nice property. If we keep doing that until the end, the algorithm guarantees to find an optimal solution if one exists. So that's why in this particular case we say the branch and bound algorithm is an exact algorithm, it is exactly returns the optimal solution for the problem, so that's good. But also there's one thing that is bad, is actually an exponential time algorithm. So roughly speaking, this is saying that if you have a huge problem with a lot of variables, a lot of constraints with a lot of integer variables, branch and bound may take such a long time so that it gets you an optimal solution. That longtime may be hours, hundreds of hours, thousands of hours, a few days, or even you just cannot wait to see the solution that's possible. So maybe you would agree that if you have an integer variables, roughly you need to solve two to the power of n subproblems. So this number is of course not exact but when you know that you add constraints and then you keep branching and you have two other nodes and then you keep branching. Basically you may see that there may be a lot of subproblems to solve, even though solving each linear problem is not so difficult. But if you have millions of linear programs to solve that's still a lot of works. Also that's one drawback on branch and bound. So in academia, many researchers they try to devote themselves to try to speed up branch and bound. Also if you take some advanced courses about integer programming, you will see many of them. But for this introductory course, we will stop our introduction to branch and bound here. All you need to know is to get an idea about okay, branch any bound runs in this way. Branch and bound guarantees to find an optimal solution and okay, branch and bound use some smart ways to avoid solving too many subproblems, then that's good enough for here.
