If you take a look at this problem, well, actually you also know how to use the simplex method to solve it. So the first step is to solve the linear relaxation, okay? So we have a problem here. So of course, the first step is to do the root node. 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. 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 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 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 this is a very typical optimization problem which may be formulated, again, as an integer program. 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. We want to maximize the total value without exceeding the knapsack capacity. Okay, so whenever we see that we know our problem is the following. So what does that mean? That means we cannot carry more than 11 kilograms. We have a knapsack which is a backpack and that capacity is 11 kilograms. Unfortunately, we cannot take everything. 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. So, let's say there are four items to select, I mean there are five items to select. Okay so, let's do this with an introduction or a review for the classic knapsack problem. So here we're going to also take this chance to give you some ideas, some more deeper understanding about the knapsack problem. Second is that knapsack is just so important so it deserves a lot of attentions. For each sub problem if there is a unique feature then don't use the simplest medicine use something else that is actually faster. First, we want to give you an illustration about the idea I just mentioned. 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. Just use your observation then it may be good enough. 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. When it is possible, don't use the simplex method. You should try to speed up the process for solving each 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. So the simplex method is always valid for solving a linear program. And it happens that sometimes we don't need to use the general simplex method. 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. So that was a general description about branch-and-bound.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |