Now let's take a look at a solution to remedy that detriments for rounding linear relaxation solutions. We're going to make us stronger, we're going to consider more, we're going to use this branch and bound algorithm. Let's recall our idea. We got one solution from our linear relaxation. For this particular example, if you take a look at this solution, is going to be some fractional values. In that case, either round up, or round down, or whatever, they fail to find an optimal solution. That's not enough. Well, why is that? Because when we are doing linear relaxation or when we get it back to integer solutions, we are actually eliminating too many feasible points. What does that mean? If we only look at something around here, then pretty much there's no way for us to find a solution that is far of from our optimal solutions. Now, let's take a look at our ideas. Previously, when we are rounding up or rounding down, we may say that we are adding equality constraints. For example, if you'll try to round up, you may say that you are adding a constraint saying that x_2 should be equal to 3, and x_1 should be equal to 4. You may say it in that way. But once you do that, your feasible points get to only just a few. Then you are cutting away this optimal solution. People say, well, let's don't do that. Instead of adding equalities, let's add inequalities. Let's say I add x_1 greater than or equal to 4, and the x_1 less than or equal to 3. I'm going to say, hey, I want either to be greater than or equal to 4 or x_1 less than or equal to 3. If I do that, then please note that I am going to have two linear programs and all the feasible points, all the integer points in those linear programs, if I collect them together, they form our original points for all our original integer problem. We are going to divide one problem to two problems. We're going to add two constraints and solve this problem and that problem. Once we do that, in some sense, we are removing this feasible region and then we are cutting down the feasible region to make it smaller. Maybe once we do that, we will be able to focus more and hopefully get our optimal solution. This is to split one problem to two problems. That's a branching step. Once we do that, if we add a constraint saying that x_1 should be less than or equal to 3, the feasible region is here. That's another, you can call it an integer program. Then we may apply that linear relaxation idea again. Or we may add x_1 greater than or equal to 4, in that case, we get again another integer program. The optimal solution to the original IP must be contained in one of the above two feasible regions. Why is that? Because the optimal solution to the original IP, they are lost on grid points or integer points. If you collected this part and that part and collect those feasible points from two sets, actually they form exactly your feasible region for the original IP. That's why you don't lose any chance. You don't lose any feasible candidates to your IP. That's how you make get an optimal solution. Well, That sounds good. Actually, we can do it again, again, and again. When we solve the linear relaxation and find any variable violating any integer constraints, like previously, you see some 4.3, 3.8, whatever. If you see 3.8, then let's say, I want to focus on the part where I have x_1 less than or equal to 3, or x_1 greater than or equal to 4, we will branch the problem into two sub-problems. One, we send additional constraint, and then the two new programs are still linear programs. They are originally integer programs. Once you do linear relaxation, they are still linear programs. We still know how to solve them. If for any of them, if the LR-optimal solution is IP-feasible, then we know that the problem has been solved. If not, if any of them results in a variable violating the integer constraint, then we do it again. For example here, suppose here we still get a fractional value after we solve the LR-optimal solution, then that's two branch again. Eventually, we will get all those sub-problems. Eventually, the collection of all of them will give us an optimal solution less the idea of branch and bound. Of course, there are some more, but let's start to illustrate the idea with some examples and show you more about the details.
