So let's use this very simple example to illustrate this idea. So we want to maximize 3x1 + x2 subject to 4x1 + 2x2 less than or equal to 11. All the variables should be non-negative and they should be integers. So here on the finger, I plotted all those points, all those dots that are feasible to our original integer programs, okay? So in this particular problem, if you use a graph that is precise enough, I guess you may agree that, okay, 2,1 seems to be optimal, okay, while 2,0 is not optimal. 1,3 seems to be not as good as 2,1, right? So 2,1 seems to be optimal. Let's see how branch-and-bound may be applied to get through the whole process and get through an optimal solution. So first, we would solve the linear relaxation. So we're going to relax those integer constraints and focus on the linear program obtained by linear relaxation. Then either you call simplex method or you just use your eye to take a look at this figure. Very quickly, graphical solution also tells us that your x1 will be 11 over 4, x2 is 0, that's your optimal solution. So branch-and-bound tells us that we focus on any one of the fractional values. Here, we only have one fractional value, that's x1. So let's branch on x1. So now, we're going to prepare a branching tree to illustrate the idea of branch and bound. So in this branching tree, we start with a root node that represents our original problem. That original problem is actually the linear relaxation of our original problem. So in that case, we get one solution, 11 over 4, 0, and its objective value. Through simple calculation, we may get 33 over 4. So each node represents a subproblem, and we write down the solution inside the box, okay? So once we have that, every time when we branch a variable, we're going to create two child nodes by adding two constraints. For example, in this case, because x1 is within 2 and 3, we're going to add a constraint, restricting x1 to be less than or equal to 2, or restricting x1 to be greater than or equal to 3. If we add x1 to be less than or equal to 2, then once we do that, we're going to add a constraint here, literally add a constraint. So once we do that, well, feasible region becomes this part. And again, we know how to do simplex method, we know how to do graphical solution. We're going to get x2 as our optimal solution, and in this case, the second variable x2 becomes a fractional value. So later, we still need to deal with this fractional variable, we're going to branch on x2. But before that, don't forget, we have another subproblem, okay? So let's solve the other one. For the other one, we add x1 should be greater than or equal to 3. And once we make that constraint inside, immediately that problem becomes infeasible, okay? And that means left node is dead or is soft, and there is no way for us to generate any candidate solution from here. There's also no child nodes for this particular dead node. If we put the information back into the branching tree, then once we solved problem one, let's call it P1, we get a fractional solution. So we add two constraints to create subproblems P2 and P3. We see that P3 has an infeasible solution. So p3 is there, it has been solved. There's no reason to keep branching on P3. But for P2, the solution is still fractional, so we probably need to do something more to solve problem two, okay? So there are some other things that we may observe. So z2 is 7.5, okay? If you plug in x2 back into your objective function, you are going to get z2 as 7.5. At the same time z1 is 8.25. What does that mean? That's actually a general case. This is a maximization problem, okay? And for a maximization problem, once we add a constraint into an existing program, we are restricting our Earth more. And once we do that, we're not going to do as good as our original case, okay? So in general, when we branch to a new level, that objective value would decrease, at least a weekly decrease, okay? You're not going to see that, when we go deeper, we get a larger objective value. Well, that's impossible for a maximization problem because once you go deeper and the deeper and the deeper, you are adding constraints, adding constraints, adding constraints. So you'll have a smaller, smaller, and smaller feasible region when you go deeper. And that's how you always get weekly lower objective value, okay? If you are doing a minimization problem, then of course, when you go deeper, deeper, and deeper, feasible region, smaller, smaller, and smaller. So your optimal objective value would become larger, larger, and larger, okay? That's some definite thing, that will definitely happen on any branch and bound tree.
