1 00:00:00,240 --> 00:00:02,827 Okay, welcome back. Supplemental assignment on Warehouse 2 00:00:02,827 --> 00:00:04,950 Location. Are there any of you left? 3 00:00:04,950 --> 00:00:08,790 so, this is an assignment where the actual data format is a little bit more 4 00:00:08,790 --> 00:00:12,873 challenging and we'll review that. But this is the Warehouse Location 5 00:00:12,873 --> 00:00:15,384 problem. It's, once again, one of these beautiful 6 00:00:15,384 --> 00:00:19,480 problems that everybody should try at least once in his or her life. 7 00:00:19,480 --> 00:00:22,910 Okay, so you have basically a bunch of Warehouse Location, Okay? 8 00:00:22,910 --> 00:00:26,049 And you have a bunch of customers. And the key point in this particular 9 00:00:26,049 --> 00:00:29,121 assignment is to find out where you open the warehouses, okay, so that you can 10 00:00:29,121 --> 00:00:33,240 allocate the customers to them. And you minimize two types of costs, 11 00:00:33,240 --> 00:00:35,308 okay. The fixed cost, okay, of, for the 12 00:00:35,308 --> 00:00:38,656 warehouses, okay, and the transportation costs from the customers to the 13 00:00:38,656 --> 00:00:42,240 warehouses, okay. So we have a lot of things that we need 14 00:00:42,240 --> 00:00:44,764 to describe. We need to describe the various 15 00:00:44,764 --> 00:00:48,600 Warehouses, we need to describe the customers, and especially the cost. 16 00:00:48,600 --> 00:00:50,910 Okay? The cost of a particular warehouses, and 17 00:00:50,910 --> 00:00:54,630 then the cost of moving, you know, goods from one warehouse to a particular 18 00:00:54,630 --> 00:00:57,210 customer. Okay? 19 00:00:58,580 --> 00:01:02,720 So, so the ultimate solution here, okay, is going to be you know, choosing some 20 00:01:02,720 --> 00:01:05,430 particular warehouses. Okay? 21 00:01:05,430 --> 00:01:08,200 We choose which one to open and which one not to open. 22 00:01:08,200 --> 00:01:10,000 Okay? And then obviously afterwards, the 23 00:01:10,000 --> 00:01:13,999 customers you know, we left to choose. Which warehouse to associate which 24 00:01:13,999 --> 00:01:16,620 warehouse to associate with each customer. 25 00:01:16,620 --> 00:01:18,468 Okay? So, you see that this customer here has 26 00:01:18,468 --> 00:01:21,634 been associated to that warehouse. You see that that customer here has been 27 00:01:21,634 --> 00:01:23,510 associated to that warehouse. Okay? 28 00:01:23,510 --> 00:01:26,283 So, in a sense what we need to do is basically choose, you know, where the 29 00:01:26,283 --> 00:01:28,962 warehouse, you know, choose which warehouse to open, and then which 30 00:01:28,962 --> 00:01:35,394 customer to assign to which warehouse. Okay, so this is a formalization of the 31 00:01:35,394 --> 00:01:38,022 problem. Okay, it's the most contrived, and I can 32 00:01:38,022 --> 00:01:41,844 tell you it's really contrived. I had to repeat this slide three times, 33 00:01:41,844 --> 00:01:44,552 okay. So this is a very, very contrived, 34 00:01:44,552 --> 00:01:48,450 formulation of the problem. Probably nobody will ever want to use it 35 00:01:48,450 --> 00:01:51,450 in practice, but it's a correct formalization, and it basically models 36 00:01:51,450 --> 00:01:54,650 all the constraints, so in a sense, it tells you what your problem, what, what 37 00:01:54,650 --> 00:01:58,636 you, what your solution will have to satisfy. 38 00:01:58,636 --> 00:02:01,886 We're not giving you any inch whatsoever of what is a good formulation for this 39 00:02:01,886 --> 00:02:04,951 problem, okay? So in this particular problem, we'll 40 00:02:04,951 --> 00:02:08,164 always have n you know, a number of warehouses, a number of customers, okay, 41 00:02:08,164 --> 00:02:11,570 we'll have n warehouses and m customers, okay? 42 00:02:11,570 --> 00:02:15,160 Now the warehouses are going to be characterized by two data points, okay? 43 00:02:15,160 --> 00:02:18,184 One of them is going to be the cost, the cost of opening that warehouse, when you 44 00:02:18,184 --> 00:02:21,400 open that warehouse, you pay that fixed cost, okay? 45 00:02:21,400 --> 00:02:24,400 And then we have a capacity, that's the capacity of goods. 46 00:02:24,400 --> 00:02:26,800 That that particular warehouse can actually serve. 47 00:02:26,800 --> 00:02:28,519 Okay? So that's the two pieces of information 48 00:02:28,519 --> 00:02:30,860 that you need for a particular warehouse, okay. 49 00:02:30,860 --> 00:02:35,280 For the customers you need essentially the cost of transporting the good from 50 00:02:35,280 --> 00:02:39,280 that customer to every, to a warehouse, okay. 51 00:02:39,280 --> 00:02:42,465 And so for every customers, we'll have the cost for every, the transportation 52 00:02:42,465 --> 00:02:46,508 cost to every other warehouse. Now you can think of this as a big matrix 53 00:02:46,508 --> 00:02:50,284 and obviously the data, the input data, will have that, will store that input 54 00:02:50,284 --> 00:02:54,234 matrix, okay. Now one of the things that we'll use in 55 00:02:54,234 --> 00:02:57,540 the formalization is the value a w, the set a w. 56 00:02:57,540 --> 00:03:02,155 And that's the set of customer which are allocated to warehouse w. 57 00:03:02,155 --> 00:03:05,125 Okay, now let me a little bit go over the formulations, such that you understand 58 00:03:05,125 --> 00:03:07,915 the problem very well, because this is not a problem that we have seen in the 59 00:03:07,915 --> 00:03:11,085 slides. There is additional constraints. 60 00:03:11,085 --> 00:03:13,320 Okay. So let's look at the optimization 61 00:03:13,320 --> 00:03:15,944 function first. The first thing that you will do is, you 62 00:03:15,944 --> 00:03:19,520 know, compute both the fixed and the transportation costs. 63 00:03:19,520 --> 00:03:23,561 The fixed costs are pretty easy. If a warehouse is open, okay, you have to 64 00:03:23,561 --> 00:03:28,299 essentially, you know, pay a fixed cost. How do we know that the warehouse is 65 00:03:28,299 --> 00:03:30,590 open? Well at least one customer has to be 66 00:03:30,590 --> 00:03:34,055 associated with it. Which basically means that the size of a 67 00:03:34,055 --> 00:03:38,760 w, the set of customers allocated to warehouse w, has to be greater than one. 68 00:03:38,760 --> 00:03:41,925 So, if that set is greater than one, you have to pay the fix cost. 69 00:03:41,925 --> 00:03:44,186 Okay? So, that's the first thing that you have 70 00:03:44,186 --> 00:03:46,492 to sum. The second thing that you have to sum is 71 00:03:46,492 --> 00:03:48,600 the transportation cost. Okay? 72 00:03:48,600 --> 00:03:51,730 If a customer c is allocated to warehouse w. 73 00:03:51,730 --> 00:03:55,900 What you need to do is make sure that you paid a cost t c w. 74 00:03:55,900 --> 00:03:58,005 Okay? And that's this transportation cost that 75 00:03:58,005 --> 00:03:59,550 you see here. Okay? 76 00:03:59,550 --> 00:04:03,345 So, your formulation will have to compute exactly that cost. 77 00:04:03,345 --> 00:04:05,461 Okay? Now, the second thing that you need to 78 00:04:05,461 --> 00:04:08,020 take into account are the constraints of this problem. 79 00:04:08,020 --> 00:04:11,940 The first one, okay, is basically limiting the capacity. 80 00:04:11,940 --> 00:04:13,806 Okay? Is basically the capacity constraints for 81 00:04:13,806 --> 00:04:15,520 the warehouses. Okay? 82 00:04:15,520 --> 00:04:20,650 So if you look at all the customers that are associated to a warehouse, okay? 83 00:04:20,650 --> 00:04:23,300 Every customer c associated to warehouse w. 84 00:04:23,300 --> 00:04:27,128 You want to be sure that if you sum their demand, it doesn't exceed the capacity of 85 00:04:27,128 --> 00:04:30,700 the network, of the, of the warehouse, okay? 86 00:04:30,700 --> 00:04:33,900 So this is what you see there, it's basically the capacity constraints. 87 00:04:33,900 --> 00:04:37,164 When we discussed the warehouse location, and during the lecture, we didn't have 88 00:04:37,164 --> 00:04:41,694 that capacity constraints, we have one. In this particular, you know this 89 00:04:41,694 --> 00:04:43,530 particular assignment. Okay. 90 00:04:43,530 --> 00:04:46,763 So pay attention, because it may be really critical in how you design your 91 00:04:46,763 --> 00:04:50,816 algorithm. The last constraint that you see here is 92 00:04:50,816 --> 00:04:57,080 making sure that every a customer is served by only one warehouse, okay. 93 00:04:57,080 --> 00:04:59,789 It would be a very different problem is we are allowed to split the demand of a 94 00:04:59,789 --> 00:05:03,262 particular customer. So what this constraints is basically 95 00:05:03,262 --> 00:05:06,846 saying is that, if you look at the particular warehouse, okay, and if, and 96 00:05:06,846 --> 00:05:10,374 if you, if you, if you get particular warehouse and try to find if a customers 97 00:05:10,374 --> 00:05:15,930 belongs to it, okay. This expression is going to be zero one. 98 00:05:15,930 --> 00:05:19,102 And what you want to be sure is that for all the warehouses that you consider 99 00:05:19,102 --> 00:05:22,690 there is exactly one of these warehouses that is actually that, that c actually 100 00:05:22,690 --> 00:05:27,257 belongs to. So, this is constraint that we, we, that 101 00:05:27,257 --> 00:05:31,604 is essentially a very contrived way of saying a particular customers is 102 00:05:31,604 --> 00:05:37,470 allocated to only one of the warehouses. So once again you know, the formulation 103 00:05:37,470 --> 00:05:41,650 that you see is really, really not intended to be used in any system, okay. 104 00:05:41,650 --> 00:05:44,296 You can actually use it in some system, okay, there are very few systems that 105 00:05:44,296 --> 00:05:48,593 support this, but there are some, okay. But it's probably a terrible, terrible 106 00:05:48,593 --> 00:05:51,140 formulation. It just, you know, we are trying to 107 00:05:51,140 --> 00:05:54,590 confuse you as much as we can, because in this particular problem, the particular, 108 00:05:54,590 --> 00:05:59,955 the particular model has a really strong influence on the quality of the solution. 109 00:05:59,955 --> 00:06:02,677 Okay. Now let me go back to the, the, from the 110 00:06:02,677 --> 00:06:06,944 formulation to the, the input data. Okay, so the input data will start, you 111 00:06:06,944 --> 00:06:10,116 know, as usual, by giving you some particular constant that tells you how 112 00:06:10,116 --> 00:06:13,700 many inputs you have. Okay, so we'll specify the number of 113 00:06:13,700 --> 00:06:16,180 warehouses and the number of customers. Okay. 114 00:06:16,180 --> 00:06:18,864 And then we list, you know, the values for the warehouses and then list the 115 00:06:18,864 --> 00:06:21,260 values for the customers. Okay. 116 00:06:21,260 --> 00:06:25,610 For the warehouses, we need to, you know, to give you two pieces of information. 117 00:06:25,610 --> 00:06:29,438 We need to give you the capacity of that warehouse and then the fixed cost of that 118 00:06:29,438 --> 00:06:32,360 warehouse. So what you see is a list of pairs, you 119 00:06:32,360 --> 00:06:35,060 know, for every one of these line, you know, you have you know every one of 120 00:06:35,060 --> 00:06:38,410 these lines is associated with one warehouse. 121 00:06:38,410 --> 00:06:42,895 Okay, and every one of the, and every one of these lines is giving you first a 122 00:06:42,895 --> 00:06:49,010 capacity of that warehouse and then the, the fix, its fixed cost. 123 00:06:49,010 --> 00:06:50,760 Okay? So once we have done that. 124 00:06:50,760 --> 00:06:53,000 We have all the data for the particular warehouse. 125 00:06:53,000 --> 00:06:56,968 And we have to specify essentially all the data for the particular, for the 126 00:06:56,968 --> 00:07:01,233 particular customers. And a customer says two important piece 127 00:07:01,233 --> 00:07:04,080 of information. The first one is its demand and you will 128 00:07:04,080 --> 00:07:08,890 see one data, you know, data value. For that particular, that particular 129 00:07:08,890 --> 00:07:11,476 demand. And then you will see the transportation 130 00:07:11,476 --> 00:07:15,420 costs for, from that particular customers, to all the warehouses. 131 00:07:15,420 --> 00:07:18,180 And that's going to be a list, which can be, you know, ki-, qui-, ki-, kind of 132 00:07:18,180 --> 00:07:21,078 long for some of the, for some of the benchmarks that tell, that is basically 133 00:07:21,078 --> 00:07:24,114 telling you what is the transportation cost for that particular customers to, 134 00:07:24,114 --> 00:07:27,196 you know, to the warehouse zero and then to warehouse one, to warehouse two and so 135 00:07:27,196 --> 00:07:31,690 on and so forth. Okay. 136 00:07:31,690 --> 00:07:34,858 And so essentially your list is here, this is essentially giving you two pieces 137 00:07:34,858 --> 00:07:38,120 of information. This big transportation matrix. 138 00:07:38,120 --> 00:07:42,473 Interleaved with some of the demands of everyone of these customers, okay? 139 00:07:42,473 --> 00:07:45,839 The output here is going to be also very interesting, okay? 140 00:07:45,839 --> 00:07:48,553 So, what you're going to output is obviously the value of the objective 141 00:07:48,553 --> 00:07:51,273 function, okay? The objective value of the optimal 142 00:07:51,273 --> 00:07:54,046 solution, and then a flag telling you whether you have proved that this 143 00:07:54,046 --> 00:07:57,881 solution was optimal or not. And then, what you will say is that for 144 00:07:57,881 --> 00:08:03,037 every one of the customers. You will specify which warehouses it is 145 00:08:03,037 --> 00:08:07,644 associated with, okay. So for every one of the customers, you 146 00:08:07,644 --> 00:08:11,880 basically specify the warehouse it is allocated to, okay. 147 00:08:11,880 --> 00:08:15,260 Now, once again okay, this is the input data, this is the output data, but don't 148 00:08:15,260 --> 00:08:20,000 assume that this is actually telling you how you have to model the problem. 149 00:08:20,000 --> 00:08:22,745 It doesn't mean that because this is the output data, that you have to have 150 00:08:22,745 --> 00:08:26,683 decision variables for these c's. Okay, think about that, maybe there is, 151 00:08:26,683 --> 00:08:29,998 there are modelings which are, you, you know, the models that are actually not 152 00:08:29,998 --> 00:08:34,581 using the c's as decision variables. Once again, you know, the fact that this 153 00:08:34,581 --> 00:08:37,683 is the output doesn't you know, doesn't prescribe a particular way of modeling 154 00:08:37,683 --> 00:08:41,040 the problem, and that's important. Okay? 155 00:08:41,040 --> 00:08:45,070 So don't, you know, distinguish what the output is, okay? 156 00:08:45,070 --> 00:08:47,680 And what the decision variable can be. Okay? 157 00:08:47,680 --> 00:08:50,608 I've usually found the decision variables, you have to be able to compute 158 00:08:50,608 --> 00:08:53,728 the output, and that output is probably something that the decision maker, in 159 00:08:53,728 --> 00:08:56,848 practice, will want to have, but the optimization problem may be modeled with 160 00:08:56,848 --> 00:09:03,020 different variables, okay? So this is a particular example. 161 00:09:03,020 --> 00:09:05,030 Okay, a particular instance. Okay. 162 00:09:05,030 --> 00:09:08,265 So you see that in this instance we have three warehouses four customers. 163 00:09:08,265 --> 00:09:10,820 Okay. The three lines there are basically 164 00:09:10,820 --> 00:09:13,840 describing the warehouse data. Okay. 165 00:09:13,840 --> 00:09:17,998 So you see that you know the first two warehouses essentially have a capacity of 166 00:09:17,998 --> 00:09:21,380 100. The next one is a capacity of 500, and 167 00:09:21,380 --> 00:09:25,280 then you see the various cost of these warehouses here, as the second value for 168 00:09:25,280 --> 00:09:30,872 each one of these lines. And then what you see are basically the 169 00:09:30,872 --> 00:09:34,819 description of all the customers. You see the demand 50, 50 and then 75 170 00:09:34,819 --> 00:09:38,084 afterwards. Okay, that's the demand of every one of 171 00:09:38,084 --> 00:09:41,618 these customers, and what you see here is also the various lines, you know, 172 00:09:41,618 --> 00:09:46,604 specifying the transportation cost, okay. And these lines have to have three 173 00:09:46,604 --> 00:09:49,250 entries, because we have three warehouses, okay. 174 00:09:49,250 --> 00:09:56,180 So the first is one is 1, you know, 101, 202, and 300 and, and 2000.3, okay. 175 00:09:56,180 --> 00:09:59,476 And so on and so forth. And that's describing all the data you 176 00:09:59,476 --> 00:10:03,610 need for the various customers, okay. So the output here, you see the various 177 00:10:03,610 --> 00:10:05,954 output here. You see the value of the objective 178 00:10:05,954 --> 00:10:08,594 function, okay. You see that is not proven optimal, and 179 00:10:08,594 --> 00:10:11,818 then you see 1 1 0 2, which basically means that the first two customers were 180 00:10:11,818 --> 00:10:15,146 assigned to warehouse one, the next one to warehouse two, and the third one to 181 00:10:15,146 --> 00:10:21,580 warehouse the third one to warehouse zero, and the last one to warehouse two. 182 00:10:21,580 --> 00:10:23,220 Okay? So this is the output. 183 00:10:23,220 --> 00:10:25,860 Once again, you know, this doesn't necessarily correspond to decision 184 00:10:25,860 --> 00:10:27,950 variables, but it may be. Okay? 185 00:10:27,950 --> 00:10:30,550 And this is essentially the input data, okay? 186 00:10:30,550 --> 00:10:33,700 One of the things that I'm trying to do always is trying to confuse you, trick 187 00:10:33,700 --> 00:10:37,848 you into the various modelings, right? Okay, so Warehouse Location, as I said 188 00:10:37,848 --> 00:10:41,730 many times during this supplemental material, they are different formulation. 189 00:10:41,730 --> 00:10:44,240 And the way you model the problem is really critical, okay? 190 00:10:44,240 --> 00:10:46,530 So, think about how you can formulate this problem. 191 00:10:46,530 --> 00:10:48,970 So, what are the decision variables? What are the constraints? 192 00:10:48,970 --> 00:10:50,962 Okay? Now this is also an interesting problem, 193 00:10:50,962 --> 00:10:53,860 because different approach are going to be a very differently. 194 00:10:53,860 --> 00:10:55,626 Okay. So, if you use local search or if you use 195 00:10:55,626 --> 00:10:58,382 branch and bound. Think about, you know, when they are 196 00:10:58,382 --> 00:11:00,954 best, what kind of problems they are best for? 197 00:11:00,954 --> 00:11:03,774 You know, are the limitation to some of, for some of the instance of these 198 00:11:03,774 --> 00:11:06,300 techniques. Okay. 199 00:11:06,300 --> 00:11:09,150 Do thy get stuck on some of these problem classes or not, okay? 200 00:11:09,150 --> 00:11:12,505 And if you do local search, think once again of a way to actually have a FAST 201 00:11:12,505 --> 00:11:16,613 neighborhood computation, okay. So, you know, Local Search is about 202 00:11:16,613 --> 00:11:20,850 exploring as many, as many, as many, you know, points in a graph as possible. 203 00:11:20,850 --> 00:11:24,202 Noting the graph is possible. And the faster your neighborhood 204 00:11:24,202 --> 00:11:27,919 computation is, you know, even if it's complex, even if it does interesting 205 00:11:27,919 --> 00:11:30,786 things, okay? The fast, the more, the higher the 206 00:11:30,786 --> 00:11:34,510 quality of your solution will be. So even if your neighborhood is complex, 207 00:11:34,510 --> 00:11:38,230 think about ways to speed up, okay? that's it. 208 00:11:38,230 --> 00:11:40,380 I mean, this is a very interesting assignment, okay? 209 00:11:40,380 --> 00:11:46,450 and I'm very curious to see the solutions, and, you know, good luck.