Now, that's good. We know how to solve the linear relaxation for our root problem, for our original problem. That's a fractional solution and that gives certain objective value 9.8. You may double-check by yourself. Then once we do that, we know there is a fractional value. That fractional value obviously is within zero and one. So we add two constraints. X2 is less than or equal to zero or X2 is greater than or equal to one. Let's talk about the first problem. Here, we're going to add a constraint saying that X2 is less than or equal to zero into our formulation. What does that mean? That means in any case when you are doing this, your X2 has no other option. X2 must be zero for sure. This is fixed when you try to solve this problem. You still have four variables, four items to choose from. Then how to do that? Well, again, that's a continuous knapsack problem. You will still do the ratio and then still do the sorting. Item 3 will still be sorted as the first one, item 4 the second one, item 5 the third one, and item 1 the last one. You will repeat the process that pretty much you already did. You're going to take 100 percent of item, 3, 100 percent of item 4, 100 percent of item 5. After that, you still have three kilograms. You see that for item 1, taking off them requires four kilograms. That means here you may only take three over four, and that means 75 percent of item 1. That's how you solve the second problem. You first fix the value for X2 as zero and then use the same sorting idea to deal with the remaining four items. This gives you another solution which gives you 9.5. Again, it's not integer, so we may need to branch further. We also want to take a look at the other subproblem. Here, we have the constraint saying that your X2 must be one. In that case, what does that mean? Your X2 must be one, you have no other choice. Once you say your X2 must be one, that's going to consume a few capacity for your particular knapsack. You'll probably still remember that your item 2 takes five kilograms. If your item 2 takes five kilograms and in total you have 11 kilograms, then that means here you already used five, so you still have six kilograms as your knapsack capacity. You are going to ask yourself, ''What's the best way to choose among the remaining four items when you only have six kilograms?'' We're going to take the whole item 3, the whole item 4, and now when you are talking about item 5, you already run out of capacity. For item 5, you only take one-half of it and then there's no way for you to take item 1. That's how you get this particular solution. It happens that this solution, unfortunately, is also fractional. You see that there is a fractional value for X5, that means we somehow may need to further do some branch and bound on this one. Here, given that X1 is fractional, we may say X1 is less than or equal to zero and the X1 is greater than or equal to one. Then for this particular subproblem, now we have two variables fixed, X1 must be zero and the X2 also must be zero. You probably may convince yourself that then you have 11 kilograms to serve the last three items. You're going to take off them because you have the capacity to do that. That's going to be an integer solution and that that's your first candidate solution. That's good. Also, if you move onto your next subproblem here, you are going to fix yourself saying that X1 must be one, X2 must be zero. In that case, again, you have some residual capacity and you try to take all of them, all of item 3, all of item 4 and then after that, you only have three kilograms on hand. So you are going to take three over four for item 5. Once you do that, you will get this particular solution where you still have a fractional value and that this objective value, 9.25, seems to be helpful. If we keep branching, maybe, it may still generate a solution that is better than the candidate solution, currently which is the solution for X4. That's the current situation. I guess you would now conclude one thing, whenever you are using branch and bound to solve knapsack, for any node you first fix sound values and then use residual capacity to deal with the remaining items. That's again, another continuous knapsack problem and that's how you may solve everything. That say, we now take a look at the values and then we agree that 9.5, seems to be a better choice. So that say we first branch on 9.5. Then here, we're going to say your x5 is not good, so we're going to say x5 should be less than or equal to 0, or greater than or equal to 1. Once we do that very quickly, we may get another fractional solution, another fractional solution, and each of them gives us some kind of objective values. So up to here, we are having this one, this one, and this one, we are having three solutions. All these three solutions are fractional. Maybe we may think about whether we want to keep branch on them or not. nine point 25 is larger than 8. Ideally, this should be a candidate, that we should keep branching on it. Nine is greater than 8, so we should take this as a candidate. Twenty six over three. If you do some quick calculation, you are going to get 8 point something. Somehow 8 point something seems to be greater than 8. If you thinking that way, you may say, okay, this is still hopeful. But don't forget that for this particular problem, because your values of variables can only be integers, and your objective function have all the coefficients that are integers. That means, if you are going to branch on this, there's no way for you to get an integer solution, which gives you a z value that is greater than 8. It's impossible. The maximum possible integer value that you may get along this particular direction is just 8, and there is no hope to be better than the current one. If you think in that way, there's no need to branch on this because of all those integer variable, integer objective coefficient idea. So you may do this or you may choose not to do this, because if you may have fractional variables or fractional coefficients, then the previous discussion does not work. But in this particular case, you may choose whatever you want. You may do this or chose not to do this. That say we keep doing this way. We take a look at 9.25 and then try to branch on x5. Once we do that, first, we get a solution, and our solution here, 1, 0, 1, 1, 0 gives us 7. Another solution which says your x2 should be 0, x1 should be 1, x5 should be 1, gives us 1, 0, 1, 0, 1. This gives us 9 as your objective value. Then immediately this solution, 1, 0, 1, 0, 1, this solution terminates the original candidate solution, so this one becomes the new current optimal solution. Then we are lucky, because there's no need to keep branching on sub-problems 6. Why is that? Because in this case this guy cannot generate any integer solution that is better than the current solution. So there's no need to do this, and of course there's also no need to do the one, the sub-problems 7. So x9 is optimal and then we are done with this knapsack problem. A quick remark is that, the major process again, it's still branch and bound. The only thing that is unique is that we have a special way to solve the linear relaxation of the knapsack problem. For knapsack problem is this way. For some other problems, we also face the same situations. It happens that some cases when you are solving an integer program, you need to work on it's linear relaxation. If that linear program for that linear relaxation have some special properties, then we may customize the process for solving each node. Somehow that means we may customize the whole branch and bound algorithm. That's possible. That's always possible, and that, something that in some sense may be encouraged. If you really want to use branch and bound to solve a problem, it may take a lot of time. Right? Saving some time for each node can be a good idea, and that's also in many cases some researchers are trying to do, to trying to see some special properties for each linear relaxation through branch and bound. That may also be a way to speed it up, and that's be a way to make branch and bound a more realistic, more practical algorithms that may be applied in practice.
