1 00:00:00,025 --> 00:00:01,270 Okay? Welcome back. 2 00:00:01,270 --> 00:00:04,790 This is Discrete Optimization, second part of the Knapsack Problem. 3 00:00:04,790 --> 00:00:07,028 Okay. So what I'm going to do here on this 4 00:00:07,028 --> 00:00:10,520 lecture is switch hats. I'm going to take my made in the USA hat, 5 00:00:10,520 --> 00:00:15,970 okay, and change it and take another hat, you know, made in China, okay? 6 00:00:15,970 --> 00:00:19,234 And the reason that I'm doing this is because we are looking at the completely 7 00:00:19,234 --> 00:00:22,800 different way of solving exactly the same problem. 8 00:00:22,800 --> 00:00:25,350 And that's what is beautiful in optimization, right? 9 00:00:25,350 --> 00:00:28,430 So you have many hats, okay? And every one of them is a bag of tools 10 00:00:28,430 --> 00:00:31,400 that you can use for tackling a problem, okay? 11 00:00:31,400 --> 00:00:35,190 So today, I just changed my bag of tool, okay? 12 00:00:35,190 --> 00:00:38,552 I'm picking up another tool, okay? And that, and I'm going to show you how 13 00:00:38,552 --> 00:00:41,710 to use that tool for actually solving the Knapsack, okay? 14 00:00:41,710 --> 00:00:45,690 One of the thing I won't tell you is which of the two hats is better, okay? 15 00:00:45,690 --> 00:00:48,350 So you will have to figure out, you know, from yourself. 16 00:00:48,350 --> 00:00:51,220 But we're going to introduce a technique which is widely useful. 17 00:00:51,220 --> 00:00:53,240 Okay? Which is called branch and bound. 18 00:00:53,240 --> 00:00:55,428 Okay? Once again, we take the one-dimensional 19 00:00:55,428 --> 00:00:58,450 knapsack, okay? That we solved with dynamic programming. 20 00:00:58,450 --> 00:01:01,316 My other hat the other, the other day, okay? 21 00:01:01,316 --> 00:01:05,680 And so, what we see is we have the, the value of all the items. 22 00:01:05,680 --> 00:01:08,688 You have the weight of old d items which is to be smaller than k, and then we have 23 00:01:08,688 --> 00:01:11,670 to decide whether we have taken item or not. 24 00:01:11,670 --> 00:01:14,989 0 and 1 over it right? Okay, so that's the one-dimensional 25 00:01:14,989 --> 00:01:18,116 knapsack okay? Now, if I want to introduce. 26 00:01:18,116 --> 00:01:20,412 Branch and bones. What I have to do is start with 27 00:01:20,412 --> 00:01:23,330 exhaustive search, right? And that's the first thing I told you 28 00:01:23,330 --> 00:01:26,330 last time, right? So you can always decide, you know, I 29 00:01:26,330 --> 00:01:29,320 take, I take the item or I don't. OK? 30 00:01:30,960 --> 00:01:34,614 So, so in a sense, you know, once I have, once I make this, once I do that, I have 31 00:01:34,614 --> 00:01:37,806 two nodes. And I can do the same thing for the next 32 00:01:37,806 --> 00:01:39,875 level. I can decide where I take item to or I 33 00:01:39,875 --> 00:01:42,868 don't take the item to. And then I can continue and this part, 34 00:01:42,868 --> 00:01:45,976 this particular case. If I have three item, I get eight 35 00:01:45,976 --> 00:01:49,115 configuration. If I, if I get four, I'm going to get 16, 36 00:01:49,115 --> 00:01:52,730 32, 64 and so on. And it's going to grow exponentially. 37 00:01:52,730 --> 00:01:55,502 And of course what you don't want to do is explore all of these configuration, 38 00:01:55,502 --> 00:01:58,063 okay? So what we did with dynamic programming 39 00:01:58,063 --> 00:02:00,600 is trying to compute this thing bottom up. 40 00:02:00,600 --> 00:02:02,880 Avoiding to compute several times the same thing. 41 00:02:02,880 --> 00:02:06,910 What we're going to see here is branch and bound where you iterate two steps. 42 00:02:06,910 --> 00:02:11,290 A branching step, which is really trying to explore this, this tree, all right. 43 00:02:11,290 --> 00:02:14,200 So, like basically, we are going to explore the entire tree. 44 00:02:14,200 --> 00:02:16,910 But, we are going to use this technique, which is bounding. 45 00:02:16,910 --> 00:02:20,250 And bounding is going to tell you, wow, I look at this node. 46 00:02:20,250 --> 00:02:23,450 And I know for sure that I'm not going to ever be able to find and optimal solution 47 00:02:23,450 --> 00:02:27,000 below that node. So, I don't have to expand it. 48 00:02:27,000 --> 00:02:30,222 So you prune large part of this tree. And that's what branch and bound is all 49 00:02:30,222 --> 00:02:31,130 about. Okay? 50 00:02:31,130 --> 00:02:34,590 So looking at a tree, and starting, removing large pieces of it. 51 00:02:34,590 --> 00:02:37,120 Okay? Using what is called bounding. 52 00:02:37,120 --> 00:02:38,773 Okay? So, branching, I told you what it was, 53 00:02:38,773 --> 00:02:41,224 very easy, it's like an exhaustive search, sort of want to enumerate 54 00:02:41,224 --> 00:02:43,092 everything. Okay? 55 00:02:43,092 --> 00:02:47,832 And bounding is about finding an optimistic evaluation of a particular 56 00:02:47,832 --> 00:02:49,423 node. Okay? 57 00:02:49,423 --> 00:02:53,440 So optimization is for optimistic people. If you are not optimistic you can already 58 00:02:53,440 --> 00:02:55,965 give up, okay? So because we are trying to solve really 59 00:02:55,965 --> 00:02:59,160 hard problem, if you don't think you can do it, just no hope. 60 00:02:59,160 --> 00:03:02,696 So you have to be optimistic. And bounding is just that, okay? 61 00:03:02,696 --> 00:03:06,925 So you are looking at the node and how best can you do that node. 62 00:03:06,925 --> 00:03:09,590 Okay? So, if you maximize, you will have an 63 00:03:09,590 --> 00:03:12,230 upper bound. That's the top, you know, best that I 64 00:03:12,230 --> 00:03:15,760 could do for this knapsack. You know, if I, you know, if, the best 65 00:03:15,760 --> 00:03:18,622 that I can hope for. And if it's a minimization, it's going to 66 00:03:18,622 --> 00:03:20,650 be a lower bound. And how low can I go. 67 00:03:20,650 --> 00:03:22,956 Okay? So in a sense, what you want to do is 68 00:03:22,956 --> 00:03:25,964 find an optimistic evaluation, you know the best you can do, but of course you 69 00:03:25,964 --> 00:03:29,019 want the optimistic evaluation to be as middle of the optimistic as possible, 70 00:03:29,019 --> 00:03:32,718 right? So you want to make it as tight, as close 71 00:03:32,718 --> 00:03:35,679 to the optimal value as possible, okay, so we want to try to evaluate how good 72 00:03:35,679 --> 00:03:39,680 this node can be. As precisely as possible. 73 00:03:39,680 --> 00:03:40,810 Okay? That's bounding. 74 00:03:40,810 --> 00:03:43,136 Okay? So, how do we find this bounding 75 00:03:43,136 --> 00:03:45,630 technique? How, how do we bound? 76 00:03:45,630 --> 00:03:47,696 Okay? And so the basic idea here is that, what 77 00:03:47,696 --> 00:03:51,240 we're going to do is take the problem and relax it. 78 00:03:51,240 --> 00:03:52,840 Okay? So they also are going to think that you 79 00:03:52,840 --> 00:03:57,267 have always to remember is that. In a sense, optimization is the art of 80 00:03:57,267 --> 00:03:58,990 relaxation. OK? 81 00:03:58,990 --> 00:04:02,382 So, you know, optimization people, are both optimistic, and they know how to 82 00:04:02,382 --> 00:04:03,850 relax. OK? 83 00:04:03,850 --> 00:04:07,360 So we are very nice people, right? So, that's what we have to do. 84 00:04:07,360 --> 00:04:11,890 So, so now what we have to discuss is how we do relaxation in practice. 85 00:04:11,890 --> 00:04:13,970 OK? So you look at this model again, okay? 86 00:04:13,970 --> 00:04:17,567 That's a knapsack problem. And you are wondering you know, how can I 87 00:04:17,567 --> 00:04:21,343 relax this problem in such a way that the optimal solution is going to be better, 88 00:04:21,343 --> 00:04:24,883 well, the optimal solution of the relaxation is going to be better than the 89 00:04:24,883 --> 00:04:29,725 true optimal solution. How do I do that? 90 00:04:29,725 --> 00:04:32,040 Okay? Now you can look at everyting here and 91 00:04:32,040 --> 00:04:35,650 decide what to relax, one of the easy things to relax is [UNKNOWN]. 92 00:04:35,650 --> 00:04:39,329 While you can say, oh I'm going to relax the capacity constraint. 93 00:04:39,329 --> 00:04:41,480 So if I'm going to remove that constraints. 94 00:04:41,480 --> 00:04:45,100 I make the problems, you know, I make, it's a relaxation. 95 00:04:45,100 --> 00:04:48,348 Why is it a relaxation, because essentially I'm increasing the set of 96 00:04:48,348 --> 00:04:52,340 solutions to the problem. Now all these invisible solutions that I 97 00:04:52,340 --> 00:04:56,720 have to, that I eliminated before. Know they are solution. 98 00:04:56,720 --> 00:05:00,482 So these invisible configuration can somehow Are becoming feasible, so I have 99 00:05:00,482 --> 00:05:04,003 more of them. So the value of the objective value, the 100 00:05:04,003 --> 00:05:08,060 optimal solution of the optimal value is going to be higher. 101 00:05:08,060 --> 00:05:10,328 Okay. So that's an optimistic relaxation of 102 00:05:10,328 --> 00:05:12,180 this problem. Okay? 103 00:05:12,180 --> 00:05:13,850 So what happens when you do that? Okay. 104 00:05:13,850 --> 00:05:15,870 So, this is a simple example that I've shown you. 105 00:05:15,870 --> 00:05:18,878 You see on the table here You know, you see all the values of the items, and then 106 00:05:18,878 --> 00:05:21,910 you see the weight of every one of them, okay? 107 00:05:21,910 --> 00:05:26,896 So the first item, for instance, has a value of 45 and a weight of 5, okay? 108 00:05:26,896 --> 00:05:29,780 48 for the next one, and 8 as the weight, okay? 109 00:05:29,780 --> 00:05:33,056 So what we want to do is essentially solve th-, this, this problem with these 110 00:05:33,056 --> 00:05:38,020 three items and a capacity of 10, okay? So, you basically start at the beginning. 111 00:05:38,020 --> 00:05:41,390 What is the best, best, best you could ever do, okay? 112 00:05:41,390 --> 00:05:44,099 Well, we have relaxed the capacity constraint, so we can take all the items, 113 00:05:44,099 --> 00:05:46,552 okay? So, in this particular case, if you sum 114 00:05:46,552 --> 00:05:48,986 all the items. What you get, the va-, the sum of the 115 00:05:48,986 --> 00:05:53,055 values of all the items, you get 128. And that's what you see are these root 116 00:05:53,055 --> 00:05:56,950 node here, okay? So what you see are the root node, okay? 117 00:05:56,950 --> 00:06:00,124 Is basically the value 128. You see that the capacity of the knapsack 118 00:06:00,124 --> 00:06:02,192 is 10. And we are at the root node; we haven't 119 00:06:02,192 --> 00:06:05,380 actually accumulated anything. So the value is still 0, okay? 120 00:06:05,380 --> 00:06:07,736 So what are we going to do? Is we're going to take that node and 121 00:06:07,736 --> 00:06:10,767 branch, okay? So when we branch, and that's what you 122 00:06:10,767 --> 00:06:14,472 see there, okay, so I basically branch on the first item, okay, and that branch 123 00:06:14,472 --> 00:06:17,210 gives me a value of 45. Okay. 124 00:06:17,210 --> 00:06:22,170 Now, it also take a weight of 5, so now the capacity of the knapsack is 5, okay. 125 00:06:22,170 --> 00:06:26,262 And my, you know, optimistic evaluation is still 128 because now, if I can still 126 00:06:26,262 --> 00:06:30,480 take all the items, okay >> So single variation, okay. 127 00:06:30,480 --> 00:06:33,320 I keep going. I decide to take item two, okay. 128 00:06:33,320 --> 00:06:37,744 If I take item two [NOISE] boom okay. I'm exceeding, I'm exceeding the capacity 129 00:06:37,744 --> 00:06:41,150 of the nap sac, five plus eight, 13. Okay, so this is an infeasible 130 00:06:41,150 --> 00:06:42,840 configureation. OK? 131 00:06:42,840 --> 00:06:45,640 Not a solution, and so I can reject it. OK? 132 00:06:45,640 --> 00:06:50,260 So I know that I cannot take item two if I have taken item one, OK? 133 00:06:50,260 --> 00:06:53,371 So the new evaluation is the sum of all the items that I can take, and in this 134 00:06:53,371 --> 00:06:56,737 particular case there is only one left, which is three And so the best thing that 135 00:06:56,737 --> 00:07:01,100 I could ever do, if I don't take item two, is 80. 136 00:07:01,100 --> 00:07:03,560 OK? And then I decide to take item three. 137 00:07:03,560 --> 00:07:04,950 That's what you see here. OK? 138 00:07:04,950 --> 00:07:06,860 And I get that value of 80. Yes! 139 00:07:06,860 --> 00:07:08,360 I have a solution now. OK? 140 00:07:08,360 --> 00:07:11,356 And its value is 80. If I don't take the item, I also get a 141 00:07:11,356 --> 00:07:13,970 solution. Its value is 45, so I can prune it away, 142 00:07:13,970 --> 00:07:16,305 okay? These nice little symbols here means, and 143 00:07:16,305 --> 00:07:19,005 we'll see that again and again, is basically mean I can prune that node, I 144 00:07:19,005 --> 00:07:23,335 don't need to look at that node. Is, is dominated by the best solutions I 145 00:07:23,335 --> 00:07:25,730 have found so far. Okay. 146 00:07:25,730 --> 00:07:29,078 Now you go back and there's the thing that you could do there is essentially 147 00:07:29,078 --> 00:07:33,167 not selecting item 1. What you get tehre is an optimastic 148 00:07:33,167 --> 00:07:35,560 evaluation which is 83. Okay. 149 00:07:35,560 --> 00:07:37,996 So if select the 2 other items I can get 83. 150 00:07:37,996 --> 00:07:42,110 Now 83 is still better than 80 the solution that I have. 151 00:07:42,110 --> 00:07:43,740 Okay so i have to continue. Okay. 152 00:07:43,740 --> 00:07:45,750 So I'm continuing. Okay. 153 00:07:45,750 --> 00:07:49,350 So, I take item 2 okay, so I get still an evaluation of 83. 154 00:07:49,350 --> 00:07:53,160 And then, if I take item 3, [SOUND] I exceed the capacity of the knapsack. 155 00:07:53,160 --> 00:07:55,100 So, that's not a feasible, that's not a solution. 156 00:07:55,100 --> 00:07:58,210 That's not a feasible configuration. And if I don't take it, I get a value of 157 00:07:58,210 --> 00:08:00,430 48. that's not good. 158 00:08:00,430 --> 00:08:02,640 It's dominated by the best solution I found. 159 00:08:02,640 --> 00:08:05,910 I go back here, okay, I decide not to take item 2. 160 00:08:05,910 --> 00:08:10,000 And so, now all best value is 1 is 35. Okay, 35 is worse, is way worse. 161 00:08:10,000 --> 00:08:13,840 That what we have found there, I don't need to explore below, below that node. 162 00:08:13,840 --> 00:08:16,594 That's bounding, right. I know that, even if I take all the 163 00:08:16,594 --> 00:08:19,714 possible items that I have left, this will, this, this note will never be 164 00:08:19,714 --> 00:08:25,052 expanded to something which is better than 35 and before I can prune it away. 165 00:08:25,052 --> 00:08:29,170 I don't need to explore the choices. For the third item, below that node, 166 00:08:29,170 --> 00:08:32,072 okay? So that, you know, that explains to you, 167 00:08:32,072 --> 00:08:37,086 the bonding process in a very very naieve and simple relaxation, okay? 168 00:08:37,086 --> 00:08:40,744 So, now we look at this thing and we say, okay, so can I actually do something 169 00:08:40,744 --> 00:08:45,903 which is not completely stupid, can I actually get a relaxation here? 170 00:08:45,903 --> 00:08:50,430 Which is giving me some interesting, some interesting optimistic evaluation. 171 00:08:50,430 --> 00:08:54,015 How can I relax this in an interesting fashion? 172 00:08:54,015 --> 00:08:56,735 Okay? Now, think, you know, if instead of 173 00:08:56,735 --> 00:09:00,420 having these beautiful artifacts that, you know, Indiana Jones has to collect, 174 00:09:00,420 --> 00:09:03,885 what we are trying to do is to collect something which is almost as valuable, 175 00:09:03,885 --> 00:09:09,024 Belgian chocolate, right? So we are basically at all these bars of 176 00:09:09,024 --> 00:09:12,900 Belgian chocolate we will take as many as we can. 177 00:09:12,900 --> 00:09:16,183 But then, essentially, what can happen is that, okay, you fill your knapsack and 178 00:09:16,183 --> 00:09:20,050 then there is this nice bar that doesn't fit into the knapsack. 179 00:09:20,050 --> 00:09:24,230 What you can always do at that point is take the bar and break it, right. 180 00:09:24,230 --> 00:09:28,220 And you take a piece of it, okay. So, in a sense, one of the things that 181 00:09:28,220 --> 00:09:31,952 you can do in this particular case. If, if you are dealing with this 182 00:09:31,952 --> 00:09:36,640 beautiful and tasty Belgian chocolate. Is cut one item in parts, okay? 183 00:09:36,640 --> 00:09:40,680 You can do that, so that you can actually fit it inside the knapsack. 184 00:09:40,680 --> 00:09:44,980 So, if you do that essentially what you're doing is relaxing. 185 00:09:44,980 --> 00:09:48,030 The decision, the values of the decision variable can take. 186 00:09:48,030 --> 00:09:51,254 Remember before, the value that xi could take is 0 and 1, I take it or I don't, 187 00:09:51,254 --> 00:09:56,178 well I don't take it or I take it, okay? And so what I'm doing here is saying, oh 188 00:09:56,178 --> 00:09:59,600 but no, I can take an item or I cannot take an item or I can take any part of 189 00:09:59,600 --> 00:10:05,880 that item, any fraction of the item. And that's really what I do here, okay? 190 00:10:05,880 --> 00:10:10,284 So this is an interesting relaxation. We'll come back to it many, many times in 191 00:10:10,284 --> 00:10:14,230 this, in this class. And it's called the linear relaxation. 192 00:10:14,230 --> 00:10:16,186 Okay? So what we are basically doing is taking 193 00:10:16,186 --> 00:10:20,660 the, you know, the, the variable, the decision variable, which takes. 194 00:10:20,660 --> 00:10:25,240 We just have to take an integral value. And relaxing that so that they can take 195 00:10:25,240 --> 00:10:30,310 this continuous values inside the, their, their branches, okay? 196 00:10:30,310 --> 00:10:34,210 So we are basically saying that, no, we can take fractional parts of these, you 197 00:10:34,210 --> 00:10:38,730 know, items are in the values that these variables can take. 198 00:10:38,730 --> 00:10:41,930 Okay, so when you do that, okay, so you look at this knapsack and how do you, can 199 00:10:41,930 --> 00:10:45,090 you actually compute this in your relaxation? 200 00:10:45,090 --> 00:10:47,670 How do you actually find the solution, okay? 201 00:10:47,670 --> 00:10:50,088 Because now, we have to take, you know, we have to take all these fractional 202 00:10:50,088 --> 00:10:53,280 numbers, there are many, many, many more positive entities, right? 203 00:10:53,280 --> 00:10:55,747 So how are we going to do that? Well, there is a very simple way very, 204 00:10:55,747 --> 00:10:58,980 very simple way to do that in this particular case. 205 00:10:58,980 --> 00:11:02,460 And the key idea is that you look at all the items, and you rank them by this 206 00:11:02,460 --> 00:11:06,958 ratio, W-, Vi over Wi. So, remember, Vi is the value of the 207 00:11:06,958 --> 00:11:11,600 item, Wi is the weight. So in a sense, when you rank, so this 208 00:11:11,600 --> 00:11:17,060 ratio is giving you the most value per, you know, kilo or pot, okay? 209 00:11:17,060 --> 00:11:20,954 It's giving you the value, the most value of the, the items, that are, is ranking 210 00:11:20,954 --> 00:11:26,090 by the items that are the most valuable In, per unit, in a sense, okay? 211 00:11:26,090 --> 00:11:29,051 And so, you rank them in that particular way, and the key idea is that once you 212 00:11:29,051 --> 00:11:32,938 have ranked them in that particular way, you take them, you know. 213 00:11:32,938 --> 00:11:35,946 You take the most valuable item, and then the next valuable item, and then the 214 00:11:35,946 --> 00:11:39,369 subsequent valuable item. And at some point, you're going to get to 215 00:11:39,369 --> 00:11:42,790 the capacity of the knapsack. You can't fill the knapsack with the next 216 00:11:42,790 --> 00:11:45,290 item. And at that point, what you do is, you 217 00:11:45,290 --> 00:11:49,810 take a fractional part of that last item that you can't really fit into it, okay? 218 00:11:49,810 --> 00:11:53,120 And that's going to give you the optimal solution to this thing, okay? 219 00:11:53,120 --> 00:11:55,350 So if you look at this problem here, okay? 220 00:11:55,350 --> 00:11:57,310 So, these are the various ratios that you see there. 221 00:11:57,310 --> 00:12:00,180 Right? So, the first one is ni-, a value of 9. 222 00:12:00,180 --> 00:12:03,440 The second one 6. The, the third one is roughly 11.7. 223 00:12:03,440 --> 00:12:06,170 So, this is the, the third item is the most valuable. 224 00:12:06,170 --> 00:12:07,710 Okay? And that's obvious, right? 225 00:12:07,710 --> 00:12:12,441 So you see 35 divided by 3. That's obviously greater than, you know 226 00:12:12,441 --> 00:12:15,780 6, which is 48 divided by 8. Okay? 227 00:12:15,780 --> 00:12:19,257 So, in a sense, so now we have rang/ these guys, so we're going to select the 228 00:12:19,257 --> 00:12:21,510 third item first. Okay? 229 00:12:21,510 --> 00:12:24,294 And the total items take only a weight of 3, so you still have room in the 230 00:12:24,294 --> 00:12:25,830 knapsack. Okay? 231 00:12:25,830 --> 00:12:29,569 And you got already a value of 35. Then you take the value 1, you take the 232 00:12:29,569 --> 00:12:33,530 item 1, its value, 45; so that gives you already 80, okay? 233 00:12:33,530 --> 00:12:35,639 And, you know that, that fits in the knapsack. 234 00:12:35,639 --> 00:12:39,401 Your knapsack at that point is, is you have already taken 8, 8 of the capaci-, 235 00:12:39,401 --> 00:12:44,430 you know, 8, you know, 8 units of the, of the capacity of the knapsack. 236 00:12:44,430 --> 00:12:47,391 Now, you look at the last item. The last i-, item would take 8, you know, 237 00:12:47,391 --> 00:12:50,600 of capacity in the knapsack. You can't fit it in, okay? 238 00:12:50,600 --> 00:12:54,194 You have only 2, you know, left. And so what you're going to do is take 239 00:12:54,194 --> 00:12:58,650 only a quarter of that item and of course, you get a quarter of that value. 240 00:12:58,650 --> 00:13:02,871 Okay, which is in this particular case, 12, and you get an optimistic evaluation 241 00:13:02,871 --> 00:13:06,370 node, which is 92. Now, look at what we have done. 242 00:13:06,370 --> 00:13:11,320 Before if you take all the items, we have something like what, you know 128. 243 00:13:11,320 --> 00:13:13,284 Right? Now, we have an optimistic evaluation 244 00:13:13,284 --> 00:13:15,850 here, which is 92. That, we will never reach that. 245 00:13:15,850 --> 00:13:18,418 This, well, maybe we can. But, but this is the best we could ever 246 00:13:18,418 --> 00:13:22,200 do, if we actually select an, you know, items in their entirety. 247 00:13:22,200 --> 00:13:24,980 But this is an optimistic evaluation of the best you can do. 248 00:13:24,980 --> 00:13:27,260 Okay? So, so, so, but, it's much tighter than 249 00:13:27,260 --> 00:13:29,880 the one that we did before and that's good. 250 00:13:29,880 --> 00:13:33,300 So, you want this bond to be optimistic but as tight as possible. 251 00:13:33,300 --> 00:13:34,874 Right? And that's what we just did in this 252 00:13:34,874 --> 00:13:36,310 particular case. Okay? 253 00:13:36,310 --> 00:13:39,190 Now, you know, this is, this is the intuition why it is correct. 254 00:13:39,190 --> 00:13:41,540 You can play this valuable transformation. 255 00:13:41,540 --> 00:13:45,160 Where, you know, Yy is essentially Vi times Xi. 256 00:13:45,160 --> 00:13:49,430 When you do that, essentially, the objective function becomes beautiful. 257 00:13:49,430 --> 00:13:52,010 It's just a sum of all the decision variables. 258 00:13:52,010 --> 00:13:54,980 Inside, all the items have the same values. 259 00:13:54,980 --> 00:13:57,094 Okay. What has changed is the weight of these 260 00:13:57,094 --> 00:14:00,050 item now, okay. So the one which was, which was the most 261 00:14:00,050 --> 00:14:03,100 valuable now essentially is the s-, is the one that takes the fewest space 262 00:14:03,100 --> 00:14:06,410 inside the item. So what you're going to do is basically 263 00:14:06,410 --> 00:14:09,140 fill the item one by one, the one that take the least space inside the knapsack, 264 00:14:09,140 --> 00:14:13,100 until you get to the last one because they have all the same value. 265 00:14:13,100 --> 00:14:15,872 And until you get the last one which has a, you know, which maybe takes more space 266 00:14:15,872 --> 00:14:19,240 and you can, you will take only a fractional part of it. 267 00:14:19,240 --> 00:14:22,110 This is why, this is how you can justify correctness. 268 00:14:22,110 --> 00:14:24,190 Of the linear relaxation that I have shown you before. 269 00:14:24,190 --> 00:14:26,730 Okay? So, now, of course, in practice, you 270 00:14:26,730 --> 00:14:30,698 know, you probably don't want to take this, you know, stone, or Afghan emblem 271 00:14:30,698 --> 00:14:37,530 mask and break it into part, right? So we have to take entire pieces. 272 00:14:37,530 --> 00:14:39,928 We can't break them into parts. So all we're going to use that 273 00:14:39,928 --> 00:14:44,016 relaxation, well, we are going to use it as a bonding technique, right? 274 00:14:44,016 --> 00:14:47,746 So now we are at the top of the node. We know that the best we could ever do is 275 00:14:47,746 --> 00:14:50,539 92, okay? We haven't selected anything, we still 276 00:14:50,539 --> 00:14:53,840 have the full capacity of the knapsack available, okay? 277 00:14:53,840 --> 00:14:57,155 Now, if you select item 1, obviously every time you select something, okay, so 278 00:14:57,155 --> 00:15:00,521 in this particular case, you know, since it was taken into relaxation, you will 279 00:15:00,521 --> 00:15:05,110 have the same relaxation over, optimistic value here. 280 00:15:05,110 --> 00:15:07,860 So you still get 92. Now, you have already accumulated the 281 00:15:07,860 --> 00:15:10,660 value of 45 and the capacity of the knapsack is 5, okay? 282 00:15:10,660 --> 00:15:13,876 You keep going, you know if you take item 2, boom, okay, you exceed the capacity of 283 00:15:13,876 --> 00:15:18,150 the knapsack, this is unfeasible so you don't consider that guy. 284 00:15:18,150 --> 00:15:20,310 You go on the right. You don't take item 2. 285 00:15:20,310 --> 00:15:23,650 What is interesting here is that now, the evaluation is different. 286 00:15:23,650 --> 00:15:26,960 It's 80, okay? It's taking basically item 1 and item 3. 287 00:15:26,960 --> 00:15:29,580 And you get a feasible solution when you take it. 288 00:15:29,580 --> 00:15:32,142 You also get a feasible solution if you don't take it, but that solution is 289 00:15:32,142 --> 00:15:34,950 dominated so you can create a way. Okay? 290 00:15:34,950 --> 00:15:39,820 So what is interesting, though, is what happens if you don't take item 1. 291 00:15:39,820 --> 00:15:42,640 Okay? If you don't take item 1, look. 292 00:15:42,640 --> 00:15:48,730 What we have is the value 77, right? That value is already lower than the best 293 00:15:48,730 --> 00:15:53,350 solution you found, which is 80. Which basically means what? 294 00:15:53,350 --> 00:15:57,010 Whatever you will do here below that tree, right, below that node, okay, 295 00:15:57,010 --> 00:16:02,480 whatever you will do Is not going to get you better, better solution than 77. 296 00:16:02,480 --> 00:16:05,808 You know that 77 is already lower than this one so you can throw the entire tree 297 00:16:05,808 --> 00:16:10,080 there, completely away. You can prune that, you know, away. 298 00:16:10,080 --> 00:16:11,920 Okay? So which is great. 299 00:16:11,920 --> 00:16:13,547 Right? So know the 3 is much smaller than 300 00:16:13,547 --> 00:16:16,460 before, you are cutting this exponential growth. 301 00:16:16,460 --> 00:16:19,490 Okay. Now how did we get, you know, 77. 302 00:16:19,490 --> 00:16:21,400 Well, what you know is that you can take item 1. 303 00:16:21,400 --> 00:16:23,786 Right? So you know that the most valuable item 304 00:16:23,786 --> 00:16:27,692 is item 3 so you take also 3 units of capacity for knapsack, okay, and you 305 00:16:27,692 --> 00:16:32,271 accumulate 35. So which means what, that you have 7 306 00:16:32,271 --> 00:16:36,915 units left in the knapsack, okay? So this guy is taking eight and you can't 307 00:16:36,915 --> 00:16:39,940 take all of them okay, so you are going to do what, you going to take seven 308 00:16:39,940 --> 00:16:45,202 of these 8 units. So if you do 7 8ths of 48, what you get 309 00:16:45,202 --> 00:16:47,892 is, is what? Okay. 310 00:16:47,892 --> 00:16:53,030 Is 42, 42 plus 35 is 77. That's the value that you see there. 311 00:16:53,030 --> 00:16:56,486 Okay, so but the key point here is that this is an optimistic evaluation using 312 00:16:56,486 --> 00:17:00,349 the linear relaxation. That's what I just told you about and 313 00:17:00,349 --> 00:17:04,184 because this value is really tight in this particular case, we can prune it, we 314 00:17:04,184 --> 00:17:07,724 can prune the entire subtree which is below that node in one step, at that 315 00:17:07,724 --> 00:17:11,120 level. Okay? 316 00:17:11,120 --> 00:17:13,730 And therefore the tree is much smaller. Okay? 317 00:17:13,730 --> 00:17:17,455 We prune that guy; we are done, okay? So, essentially, this is an introduction 318 00:17:17,455 --> 00:17:20,746 to depth-first branch and bound. That's the strategy that we have done, 319 00:17:20,746 --> 00:17:23,059 okay? So we start exploring the node, and then 320 00:17:23,059 --> 00:17:26,031 the node, you know? Th-, we start exploring from left to, you 321 00:17:26,031 --> 00:17:28,822 know, from left to right. And every time we branch, we have two 322 00:17:28,822 --> 00:17:31,090 nodes, we take the left one and we do that. 323 00:17:31,090 --> 00:17:32,800 When you go back we explore the right one. 324 00:17:32,800 --> 00:17:35,430 That's the depth-first search. There is another strategy which is 325 00:17:35,430 --> 00:17:38,046 best-first. And that strategy is essentially always 326 00:17:38,046 --> 00:17:40,770 taking the node which has the best evaluation. 327 00:17:40,770 --> 00:17:43,336 Okay? So we always say, oh, that node is a good 328 00:17:43,336 --> 00:17:45,992 evaluation. I want to take it because that's probably 329 00:17:45,992 --> 00:17:47,820 where the best solutions are. Okay? 330 00:17:47,820 --> 00:17:49,590 I'm going to discuss that in a moment. Okay? 331 00:17:49,590 --> 00:17:52,335 But there are many others and we'll come back to that later in the class. 332 00:17:52,335 --> 00:17:55,919 Okay, so that first, the key ID in that first is that you prune a node every time 333 00:17:55,919 --> 00:18:01,500 the evaluation is worse than the one you, that, that you have found so far, okay. 334 00:18:01,500 --> 00:18:04,599 It's very memory efficient. The only thing that you have to remember 335 00:18:04,599 --> 00:18:08,424 is essentially a path, okay. best-first search is always selecting the 336 00:18:08,424 --> 00:18:12,787 node with the best estimation, okay? And the key ID, what, the reason why you 337 00:18:12,787 --> 00:18:18,450 want to use a technique like that is because you want to dive in very quickly. 338 00:18:18,450 --> 00:18:20,220 To the best possible solution. Okay? 339 00:18:20,220 --> 00:18:23,370 So let me illustrate this by using the stupid illustration that we have seen 340 00:18:23,370 --> 00:18:25,996 before. Because it's easier to actually do the 341 00:18:25,996 --> 00:18:28,880 illustration here, okay? So I restart from the root. 342 00:18:28,880 --> 00:18:30,656 Okay? And I have the value of 28 nothing in the 343 00:18:30,656 --> 00:18:32,735 knapsack. No value accumulated. 344 00:18:32,735 --> 00:18:35,421 Okay? So essentially what I do is that in the 345 00:18:35,421 --> 00:18:38,685 particular case, you know, I branch, I generate these two nodes and I take the 346 00:18:38,685 --> 00:18:42,515 one that has the largest value. Right? 347 00:18:42,515 --> 00:18:47,600 so I take the one which has the value 128, okay? 348 00:18:47,600 --> 00:18:50,987 So that's when I take the item, right? And now, what I do is, I expand that 349 00:18:50,987 --> 00:18:54,433 node, and I get 2 nodes, okay? So, I get one which is infeasible, so I 350 00:18:54,433 --> 00:18:57,980 throw it away, and I get another one, which has value 80. 351 00:18:57,980 --> 00:19:00,200 At that point, I look at all the nodes that I have, okay? 352 00:19:00,200 --> 00:19:02,486 I have 2 left. Which are feasible, which are potentially 353 00:19:02,486 --> 00:19:04,490 feasible, they are still feasible at this point. 354 00:19:04,490 --> 00:19:07,370 And I think the one which is the best evaluation of function which is this guy, 355 00:19:07,370 --> 00:19:10,524 right. So I expand that guy and I get two nodes, 356 00:19:10,524 --> 00:19:15,020 I get another node with 83 and I get a node with 35. 357 00:19:15,020 --> 00:19:18,958 So I take the node which has the highest value which is once again 83. 358 00:19:18,958 --> 00:19:24,350 I expand 83 and i get a value of 48. Okay, and any, and any feasible solution, 359 00:19:24,350 --> 00:19:26,560 okay? So I get 48 over there. 360 00:19:26,560 --> 00:19:29,420 That's the best, so that's the solution now, okay, and I can throw all the nodes 361 00:19:29,420 --> 00:19:32,260 which are in the tree which are worse than that. 362 00:19:32,260 --> 00:19:35,510 So I will throw away this particular node here, okay. 363 00:19:35,510 --> 00:19:38,612 Now that node here as evaluated, it's still greater than the best solution that 364 00:19:38,612 --> 00:19:42,670 I found, so I keep expanding it, okay. Whoops, sorry, so I forgot one of the 365 00:19:42,670 --> 00:19:45,872 things that I wanted to do. Okay, so I get these two, I get these two 366 00:19:45,872 --> 00:19:49,010 nodes, I get these two nodes there. Okay? 367 00:19:49,010 --> 00:19:52,760 And one of them is the value 80. The other one is the value 45, okay? 368 00:19:52,760 --> 00:19:55,879 So the value 45, I can throw away again. Okay? 369 00:19:55,879 --> 00:19:58,770 And the value 80 now becomes the best form solution. 370 00:19:58,770 --> 00:20:01,161 Okay? So, essentially, best-first is always 371 00:20:01,161 --> 00:20:04,068 going to look at the nodes and take the one which has the best evaluation 372 00:20:04,068 --> 00:20:06,760 function. When does it prune? 373 00:20:06,760 --> 00:20:08,810 It prunes when you have a physical solution, okay? 374 00:20:08,810 --> 00:20:11,800 When you find a physical solution, then all the nodes which are, you know, that 375 00:20:11,800 --> 00:20:15,200 are worse evaluations are going to be thrown away. 376 00:20:15,200 --> 00:20:18,575 And, the question that I have for you is that, is it memory efficient? 377 00:20:18,575 --> 00:20:20,914 Okay? And, I'm give you, I'm giving you a trick 378 00:20:20,914 --> 00:20:22,830 here. In most of these optimization problems, 379 00:20:22,830 --> 00:20:25,160 and most of the questions I'm going to ask you. 380 00:20:25,160 --> 00:20:28,020 The answers can always be found by exaggerating. 381 00:20:28,020 --> 00:20:31,000 Okay? So exaggerate the situation. 382 00:20:31,000 --> 00:20:34,685 If you exaggerate the situation, you will find out whether this thing, you know, 383 00:20:34,685 --> 00:20:38,150 whether the answer is, you know, whether the, well, what the answer is to the 384 00:20:38,150 --> 00:20:42,484 question. Okay so how do we exaggerate in this 385 00:20:42,484 --> 00:20:46,189 particular context. The way to exaggerate there is to assume 386 00:20:46,189 --> 00:20:49,687 that you have a terrible optimistic evaluation, you always return minus, plus 387 00:20:49,687 --> 00:20:53,238 infinity, you always believe that you can win the lottery, okay, so if you do that 388 00:20:53,238 --> 00:20:56,365 how many nodes are you going to expire, okay, so you are basically going to 389 00:20:56,365 --> 00:20:59,916 explore the entire tree because it's only when you find a solution at the end that 390 00:20:59,916 --> 00:21:06,260 it's going to tell you oh, this is the value... 391 00:21:06,260 --> 00:21:09,070 But all the other nodes are still, I can do better, I can do better. 392 00:21:09,070 --> 00:21:12,414 So you gotta explore the entire thing. So, what this is basically telling you is 393 00:21:12,414 --> 00:21:15,525 that if, you know, there are many nodes which are very close to the optimal 394 00:21:15,525 --> 00:21:19,016 solution, okay? So you may explore a very large portion 395 00:21:19,016 --> 00:21:20,910 of the tree. Okay? 396 00:21:20,910 --> 00:21:24,210 So it's, so the memory is an issue when you do a best, you know, best-first 397 00:21:24,210 --> 00:21:27,100 branch and bound. You have to make sure that you are not 398 00:21:27,100 --> 00:21:28,762 going to explore too many nodes. Okay? 399 00:21:28,762 --> 00:21:33,840 So so we have seen two techniques now dynamic programming and branch and bound. 400 00:21:33,840 --> 00:21:37,320 So one of the things you have to think about is which one is better than the 401 00:21:37,320 --> 00:21:40,907 other one, okay? One of the things that you may think 402 00:21:40,907 --> 00:21:44,317 about is that is this a good question, okay, is this even a valid question so 403 00:21:44,317 --> 00:21:48,392 think about it, okay? And then the other thing, and this is a 404 00:21:48,392 --> 00:21:51,957 valid question for sure. Can you actually combine these two 405 00:21:51,957 --> 00:21:55,572 techniques together? Can you actually have an algorithm which 406 00:21:55,572 --> 00:21:59,052 is the same, which is at the same time exploring some features of dynamic 407 00:21:59,052 --> 00:22:03,142 programming? And some features of Branch and Bound, 408 00:22:03,142 --> 00:22:05,156 okay? So you need to think about, what is 409 00:22:05,156 --> 00:22:07,870 really the essence of dynamic programming, okay? 410 00:22:07,870 --> 00:22:09,970 What is really the essence of Branch and Bound? 411 00:22:09,970 --> 00:22:12,330 Can you actually combine the two of them? Okay? 412 00:22:12,330 --> 00:22:15,316 Good. So this is essentially, you know, the end 413 00:22:15,316 --> 00:22:18,930 of the ramping up phase of the class. OK? 414 00:22:18,930 --> 00:22:21,115 So we have seen a very, very simple problem. 415 00:22:21,115 --> 00:22:22,620 Knapsack. Okay? 416 00:22:22,620 --> 00:22:25,920 Two basic techniques, you know, dynamic programming and branch and bound. 417 00:22:25,920 --> 00:22:28,820 We're going to look, now, in the next, the rest of the class, at various 418 00:22:28,820 --> 00:22:33,613 techniques like constrained programming, local search, mathematical programming. 419 00:22:33,613 --> 00:22:36,730 And, and try to look at more complex problems of course, okay? 420 00:22:36,730 --> 00:22:37,780 See you next time.