So that was a general description about branch-and-bound. So that's good. But there's one thing that I would like to remind you is that when we are doing branch-and-bound for each subproblem we are solving a linear program pretty much, okay? And for such a linear program, in many cases, we somehow need to solve that particular optimization problem, we somehow need to find a solution. And it happens that sometimes we don't need to use the general simplex method. So the simplex method is always valid for solving a linear program. But if your problem, if your sub problems they have some unique features that you don't need to use the simplex method, then you should do that. You should try to speed up the process for solving each linear program. When it is possible, don't use the simplex method. So one example that you already observed is that sometimes when you have only two variables, then in that case for solving each linear program, you don't really need to do simplex method. Just use your observation then it may be good enough. So here we're going to give you another example is that we are going to use the branch-and-bound to solve the knapsack problem. So there are two reasons for doing this. First, we want to give you an illustration about the idea I just mentioned. For each sub problem if there is a unique feature then don't use the simplest medicine use something else that is actually faster. Second is that knapsack is just so important so it deserves a lot of attentions. So here we're going to also take this chance to give you some ideas, some more deeper understanding about the knapsack problem. Okay so, let's do this with an introduction or a review for the classic knapsack problem. So, let's say there are four items to select, I mean there are five items to select. Okay so there are five items. For these five items we have different values, different weights, for example, for item one it is worth about $2 and the weight is 4 kilograms and so on and so on. Unfortunately, we cannot take everything. We have a knapsack which is a backpack and that capacity is 11 kilograms. So what does that mean? That means we cannot carry more than 11 kilograms. Okay, so whenever we see that we know our problem is the following. We want to maximize the total value without exceeding the knapsack capacity. So we want to choose a subset of items such that their total weight is not larger than 11 and we want to maximize the total value. So this is a very typical optimization problem which may be formulated, again, as an integer program. So the formulation is here, we have five items, for each item we determine a binary variable, whether we want to take it or not, okay? So xi is 1 if we want to take this item xi 0 if we don't. So we want to maximize the total value that we bring, subject to the fact that the total weight we carry cannot be greater than 11. So that's a knapsack problem. Of course, this is just an example but when you are given a lot of items and all kinds of different values, you know how to formulate it, right? This is just a very typical case that the general compact formulation can be done by yourself. So we are going to use this example to show you how to use branch and bound to deal with this particular knapsack particular instance. So of course, the first step is to do the root node. So the first step is to solve the linear relaxation, okay? So we have a problem here. If you take a look at this problem, well, actually you also know how to use the simplex method to solve it. You just need to add a slack, and then once you do that, you're going to also have some variables they should be less than or equal to 1. So you add a slack for each of them. So you add six slack variables and then you have a standard form and then you do this do that power eventually you will get an optimal solution. So using simplex is okay, but here we don't want to do that. We're going to show you that there is actually a very incurative way that works for knapsack problem. So what's that? First, that sort only items in the descending order of their value weight ratio. So the value is put at the numerator and the weight is at the denominator, all right? So, once we have that, we are able to calculate several ratios. For example, for the first one, the first item that ratio is 1 over 2. The second item, the ratio is 3 over 5, and so on and so on. So we are able to calculate the ratio for all the items, and then we sorted all the items in the descending order. For example here if we calculate all the five ratios, okay, they are here, then the order would be item 3 is put in front of everything, because item 3 has the largest ratio. And then item 4 as the second one, and so on and so on and so on. So we first sort all these items, and then what do we do? Select each item one by one, according to the order until the knapsack is full. So what does that mean? Item 3 is the first item, so we try to take item three as much as possible. Don't forget that now all these values are fractional. So you are allowed to take 60% of item 3, 80% of item 3, and so on. So we try to add as much item 3 as possible and eventually we will take the whole item 3, because taking the whole item 3 is okay for us. After we do that, we still have 8 kilograms as our residual capacity. Then we move on to our next item, item 4. For item 4, we get as much as possible, and then we take the whole item four, we still have 7 kilograms. And then for the next one, we move to item 5. For item 5, we take as much as possible then we still take 1, the whole 100% of item 5, and then 7 minus 4, we still have 3 kilograms as the residual capacity. Then we move on to item 2. For item 2, if we want to take the whole item 2, that's going to consume 5 kilograms. But now we only have 3 kilograms. So what do we do? We take 3 over 5 of item 2, we take 60% of item 2 instead of the whole item 2, or no item 2, okay? So, if this is the original integer program, we are not allowed to do that. We cannot take 60% of item 2. But because this is already a linear relaxation so we are allowed to do that and we conclude that once we do all of this, once we do this as a solution, then this would be optimal to the linear relaxation here. All the capacity is used out and we have maximized our total value. So this may be very intuitive, but I hope you may want to think about why this L reason is guaranteed to be true, okay? Why you cannot generate another solution, that is also feasible, and that is better than this one. So actually this is impossible. So, there are many ways to prove this, but I'm just going to give you another example to help you think about this. Suppose there is a way to generate another solution that is better than this one. Then because for the other three items they already be taken for 100%. Somehow it means there must be some values taken from item 1, all right? Otherwise there is no way for you to generate another solution. Then you'll somehow need to decrease the value for the other four, somehow. Otherwise your backpack is not enough. So if that's the case you are doing some kind of exchange using higher ratio items to exchange for lower ratio items, and very quickly you may convince yourself that this is not good. And then that somehow concludes that this particular ordering and the greedy algorithm is optimal for your linear relaxation for knapsack, okay? And once that is true, then this tells us that for solving this knapsack problem, there's no need for running the simplex method. All you need to do is to calculate five ratios and then sort them, and then do some one by one checking. So if you are familiar with this big O notation, then the total complexity is just a log n. It depends on how long it takes to sort O items. So if you are not familiar with the big O notation, that's also fine, just convince yourself that this seems to be much easier than running the simplex method, okay? So then that creates a building block for solving the knapsack problem the integer knapsack problem with branch-and-bound.
