We need to move on, because x_2 , in our solution, x_2 is three over two. In that case, we need to further split our problem P_2 into P_4 and P_5, by adding two constraints. We add x_2 less than or equal to 1 and x_2 greater than or equal to 2. Why is that? Because this guy is 1.5, it is within one and two. We need to eliminate the possibility for this guy to be 1.5, that's why we add these two constraints. Once we add x_2 less than or equal to 1, we get our feasible region here. Don't forget that this is the result of adding two constraints. Previously when we are at P_2, for P_2 we already have this constraint, x_2 less than or equal to 2. For P_4, we add one additional one. Now our x_2 is less than or equal to 2, and x_2 must be less than or equal to 1. In this case, once we solve the linear relaxation, then our x_4, the optimal solution would be (2,1). This is an integer solution, that's very good. If we add in the other side, x_2 is greater than or equal to 2, then in this case, we get two constraints, x_1 should be less than or equal to 2, this is this one, and your x_2 now should be greater than or equal to 2. Once we do that, the feasible region becomes here, and then our optimal solution is seven over four and a 2. Another fractional solution. Putting the information back to our original problem. In this case, we can see that for problem P_4, actually we get an integer solution to one. So x_4 satisfies all the integer constraints. We say it is IP feasible, it is feasible to the original integer program, which is denoted as P_0. So x_4 now serves as a candidate solution to the original integer program. It's [inaudible] good, but maybe it is not optimal, because here we have sub-problem P_5. It is fractional. We need to do something else to solve P_5, to see whether this is going to generate a solution that is even better than x_4. That's something we need to do. That's move up. This guy, seven over four is one point something, so we add two constraints, x_1 less than or equal to one, and x_1 greater than or equal to 2. For the first one, we add a constraint. Now in this program we have three newly added constraints. Again here, once we do this cut, we are going to get one, and then seven over two. Well, unfortunately, this is fractional again. Later we need to talk about this sub-problem. Or if we add x_1 should be greater than or equal to two, then in this case, we're going to see that we are having again an infeasible problem. Because if your x_1 is less than or equal to 2 and and your x_1 is greater than or equal to 2 your x_1 must be two. But then immediately that as long as you also have x_2 no less than two, then you are going to have an infeasible solution. This node again is dead. Putting information back, this is done, this is done, and also this is done. Pretty much we are reaching an outcome. But here you also may do some observation on our remaining node, P_6. The only alive node is sub-problem six, where your x_2, seven over two is fractional. But don't forget that when we are going down, when we are going deeper, our objective value will only decrease. If we do further, for example, if we say x_2 should be less than or equal to 3, or x_2 should be greater than or equal to 4, then in either case, we are not going to get a value that is greater than or equal to 13 over two. That's something we mentioned. But you already get a solution that is seven. Seven is already greater than 13 over two. If you are going to get something that is even smaller, there's no way for them to be optimal. Actually, we may stop here. Once we do this, we see we are going to get solution worse than that, and also we know seven is already good enough. That's why we say we may stop here, because all the solutions that we may generate would be worse than x_4, or cannot be greater than or better than x_4. Here, there is no need to keep branching out in this problem, P_6. This is the bounding situation in the branch-and-bound algorithm. This algorithm has two words there. Branch is the idea of splitting one problem to two, bound is to say that once we get a feasible solution, we get seven, seven provides a bound. Seven is saying that for this maximization problem, seven is a lower bound. Or any feasible solution to the IP gives us a lower bound on your optimal solution. The optimal solution cannot be worse than seven, because seven is already feasible, your optimal solution must be better than seven. Seven, eight, nine or whatever, it cannot be worse than seven. Somehow, if you see 13 over two, you don't need to keep branching, and this lower bound provides us this useful information. A very quick summary says that once we run the branch-and-bound algorithm, we maintain a tree. If you are reading wrong to write a program to do this, you also need to maintain a tree. You get new nodes, and you get connections by yourself so that you know where you are. If a sub-problem is soft and if the solution is IP feasible, we may set it as a candidate solution. Of course, we do that only if it is currently better than the current candidate. When we are doing branching, we always keep an eye on the currently best Solution. Once we get a better one, we replace the current solution. We always update the current best solution that we already found, so that we may provide better lower bound, better lower bound, better lower bound. If a sub-problem is infeasible, then it is dead. If a sub-problem, an optimal solution is not IP feasible, then either we keep branching on the fractional solution or once we can see there is no hope to generate a better one then we stop. This branch is the idea of getting all the required trials, and this bounding idea is to say, we can save our time and not to solve those problems that has no hope to generate an optimal solution. One is to make sure that our algorithm is correct, the otherwise is saying that we can speed up our algorithm.
