1 00:00:00,160 --> 00:00:04,920 So, this is Discrete Optimization, Local Search Part three, okay? 2 00:00:04,920 --> 00:00:07,510 And things are going to get more and more interesting. 3 00:00:07,510 --> 00:00:09,400 So, we're going to see two interesting problems today. 4 00:00:09,400 --> 00:00:12,770 One is warehouse location, very, you know, well-studied problem. 5 00:00:12,770 --> 00:00:16,004 And then we're going to see the traveling salesman problem, which is probably the 6 00:00:16,004 --> 00:00:20,203 most studied programming optimization. So the key point here is to start doing 7 00:00:20,203 --> 00:00:23,720 optimization, look and search for optimization problems. 8 00:00:23,720 --> 00:00:25,662 Okay? So let's start with the warehouse 9 00:00:25,662 --> 00:00:28,290 location. So what you have here is you have a set 10 00:00:28,290 --> 00:00:32,377 of warehouse, you know, place, a set of locations where you can place a 11 00:00:32,377 --> 00:00:35,830 warehouse. And then you have a. 12 00:00:35,830 --> 00:00:39,798 Large set of customers and your goal is to actually choose the location of the 13 00:00:39,798 --> 00:00:43,900 warehouses. So that you minimize two things. 14 00:00:43,900 --> 00:00:46,250 Okay, the cost of setting up the warehouse. 15 00:00:46,250 --> 00:00:49,630 And then the transportation cost from the warehouses to the customers. 16 00:00:49,630 --> 00:00:53,140 Okay, so this for instance, one particle of configuration. 17 00:00:53,140 --> 00:00:55,490 You can decide, oh I'm opening one warehouse. 18 00:00:55,490 --> 00:00:58,060 And then all the customers have to connect to that particular warehouse. 19 00:00:58,060 --> 00:01:00,146 Okay? So whatever's cheap cost for opening the 20 00:01:00,146 --> 00:01:03,135 warehouse, but of course there are customers that are really far and they 21 00:01:03,135 --> 00:01:06,222 have to travel very, you know they have to travel a lot before you know, being 22 00:01:06,222 --> 00:01:10,925 served by the warehouse, okay? So in a sense. 23 00:01:10,925 --> 00:01:14,555 You can have another configuration where you open two warehouses, so the fixed 24 00:01:14,555 --> 00:01:17,651 cost of the warehouses are going to increase. 25 00:01:17,651 --> 00:01:21,446 But now, the customers are closer to the warehouses, so the distribution cost, the 26 00:01:21,446 --> 00:01:25,915 transportation cost are decreasing. So this is one configuration with two 27 00:01:25,915 --> 00:01:28,310 warehouses open. Okay, this is another one. 28 00:01:28,310 --> 00:01:31,600 The two different warehouses, and two different assignments of the customers. 29 00:01:31,600 --> 00:01:35,560 Okay, so formally, this is what the warehouse location problem is. 30 00:01:35,560 --> 00:01:38,076 Okay? So we have a set of warehouse locations 31 00:01:38,076 --> 00:01:41,020 that we can actually build a warehouse on. 32 00:01:41,020 --> 00:01:44,230 And for every one of these locations we'll have a fixed cost. 33 00:01:44,230 --> 00:01:48,790 Okay, so fw that you see over there is essentially the cost of opening and 34 00:01:48,790 --> 00:01:54,440 maintaining your warehouse, okay. Now you also have set of customer, c, 35 00:01:54,440 --> 00:01:56,736 okay? And for every one of the warehouse and 36 00:01:56,736 --> 00:01:59,772 every one of the customers you have a transportation cost from the customers to 37 00:01:59,772 --> 00:02:03,385 the warehouse. Okay and what you want to do is to find 38 00:02:03,385 --> 00:02:07,810 which warehouse to open such that you minimize the two things. 39 00:02:07,810 --> 00:02:11,842 The transportation cost from the customers to the warehouse and then the 40 00:02:11,842 --> 00:02:15,482 fixed cost of opening these warehouses. Okay? 41 00:02:15,482 --> 00:02:18,690 So that's the problem. Okay, now its a beautiful problem because 42 00:02:18,690 --> 00:02:22,430 what, you know, they are new constraints. Okay, so essentially. 43 00:02:22,430 --> 00:02:25,713 You have, the only, well, essentially the only implicit constraint is that, you 44 00:02:25,713 --> 00:02:29,609 know customers have to be connected to a warehouse which is open. 45 00:02:29,609 --> 00:02:32,480 But this is not really a constraint, right, in that sense. 46 00:02:32,480 --> 00:02:35,713 So, the decision variables in these, in these problems are going to be which 47 00:02:35,713 --> 00:02:39,380 warehouse I'm opening, okay? Or closing, okay? 48 00:02:39,380 --> 00:02:42,356 So there, there's is a for every one of the warehouse, I will have a decision 49 00:02:42,356 --> 00:02:46,760 variable, 0/1, which decide whether the warehouse is open or not. 50 00:02:46,760 --> 00:02:50,324 And then for every customers, okay, I'm going to assign one warehouse, and that 51 00:02:50,324 --> 00:02:54,252 warehouse has to be open, okay. So in a sense when you think about it 52 00:02:54,252 --> 00:02:56,494 from a local search standpoint, it, you know, there are essentially no 53 00:02:56,494 --> 00:03:00,498 constraints. What is the objective, this is the 54 00:03:00,498 --> 00:03:03,857 objective, okay? So the objective is minimizing the sum 55 00:03:03,857 --> 00:03:07,822 for every one of the warehouses of the fixed cost of the warehouse's times, you 56 00:03:07,822 --> 00:03:12,100 know? Whether the warehouse is open or not. 57 00:03:12,100 --> 00:03:15,900 And then the transportation cost. How much does it cost to move from one 58 00:03:15,900 --> 00:03:19,480 customer to a warehouse or vice versa? Okay? 59 00:03:19,480 --> 00:03:21,950 So that's the objective function that we are minimizing. 60 00:03:21,950 --> 00:03:26,451 Now one of the key observation here that you have to realize is that. 61 00:03:26,451 --> 00:03:30,411 Once you open a warehouse, it's very easy to decide where the customer should be 62 00:03:30,411 --> 00:03:34,970 allocated, which warehouse they should be allocated to. 63 00:03:34,970 --> 00:03:38,350 And the reason is that, you know, there, basically what you want is to minimize 64 00:03:38,350 --> 00:03:41,984 the transportation cost. And therefore, once, once you know which 65 00:03:41,984 --> 00:03:45,066 warehouses are open, a customer should be assigned to the warehouse, which is as 66 00:03:45,066 --> 00:03:48,406 close as possible. And the reason is that there are no 67 00:03:48,406 --> 00:03:51,310 capacity constraints on these warehouses, okay? 68 00:03:51,310 --> 00:03:54,894 So, in a sense, the objective can be view of, okay, so which are the warehouses 69 00:03:54,894 --> 00:03:58,838 that I'm opening, knowing that essentially afterwards. 70 00:03:58,838 --> 00:04:02,438 You know assigning the customers is easy. You want to assign the customers to the 71 00:04:02,438 --> 00:04:05,623 warehouse which is, you know, which is open and which is as close as possible to 72 00:04:05,623 --> 00:04:09,368 the customer. So in a sense for every customer what you 73 00:04:09,368 --> 00:04:12,840 want is to minimize, to find the transportation cost which is the smallest 74 00:04:12,840 --> 00:04:16,438 given the warehouses which are open, okay? 75 00:04:16,438 --> 00:04:19,830 So once you know the warehouses its very easy to know which, how the customers 76 00:04:19,830 --> 00:04:24,005 have to be allocated and you can compute this cost easily. 77 00:04:24,005 --> 00:04:26,730 Okay? Now, what is the neighborhood? 78 00:04:26,730 --> 00:04:29,832 Okay, so what kinds of neighborhoods are we going to consider for the warehouse 79 00:04:29,832 --> 00:04:33,490 location problem, okay? Now many possibilities, but let me just, 80 00:04:33,490 --> 00:04:37,039 you know, mention two of them. One of them, is that you can have the 81 00:04:37,039 --> 00:04:40,560 most simplest neighborhood ever. The only thing you do is you decide 82 00:04:40,560 --> 00:04:44,341 whether, you know, decide to change the value of a warehouse, okay? 83 00:04:44,341 --> 00:04:47,090 If it was open you close it, if its closed you open it, okay? 84 00:04:47,090 --> 00:04:50,559 That's the, that's the simplest neighborhood you can imagine for, right? 85 00:04:50,559 --> 00:04:53,708 You decide whether you open or you close, you change the value of a warehouse, you 86 00:04:53,708 --> 00:04:56,280 know? Flipping it's value, essentially. 87 00:04:56,280 --> 00:04:58,640 From zero to one, or from one to zero, okay? 88 00:04:58,640 --> 00:05:01,675 So, that's a very simple neighborhood. But you will say, yeah, but this is tough 89 00:05:01,675 --> 00:05:04,356 sometimes, you know? It makes no sense to close a warehouse, 90 00:05:04,356 --> 00:05:07,332 you probably want to open a, another at the same time, and you can usually do 91 00:05:07,332 --> 00:05:09,560 that, okay? So. 92 00:05:09,560 --> 00:05:12,722 You can think of a neighborhood which has two neighborhoods, one of them is 93 00:05:12,722 --> 00:05:15,678 going to flip close or open a warehouse okay? 94 00:05:15,678 --> 00:05:19,017 And the other one is something where you will simply decide that you have one 95 00:05:19,017 --> 00:05:22,144 warehouse which is open, another one which is closed and you going to swap 96 00:05:22,144 --> 00:05:26,114 there values. Okay, so you open the warehouse which is 97 00:05:26,114 --> 00:05:29,324 closed and you close the warehouse which is open, okay? 98 00:05:29,324 --> 00:05:32,474 So you can use these two neighborhoods and so on and you can, you know, you can 99 00:05:32,474 --> 00:05:36,388 try to decide for yourself. What would be good and the efficiency of 100 00:05:36,388 --> 00:05:40,056 these various neighborhoods, okay? So that's essentially what you can do for 101 00:05:40,056 --> 00:05:42,706 warehouse location. Now, I want to talk about the Traveling 102 00:05:42,706 --> 00:05:45,236 Salesman problem now because the neighborhoods here are going to be 103 00:05:45,236 --> 00:05:49,382 really, really interesting, okay? So what you see for the warehouse 104 00:05:49,382 --> 00:05:53,780 location is a set of cities that you have to visit, okay? 105 00:05:53,780 --> 00:05:58,188 And the goal is that you have one salesman and, you know, one traveling 106 00:05:58,188 --> 00:06:02,976 salesman problem and that salesmans have to visit every one of these cities 107 00:06:02,976 --> 00:06:08,674 exactly once. And, and, and wants to minimize the total 108 00:06:08,674 --> 00:06:11,832 distance that it will travel. Okay? 109 00:06:11,832 --> 00:06:15,651 So, you know, Bill Cook, who is an expert in this, in this area, would always model 110 00:06:15,651 --> 00:06:20,100 with this example by saying this is the Santa Claus problem. 111 00:06:20,100 --> 00:06:22,521 Right? So, you you know, this is, you know, all 112 00:06:22,521 --> 00:06:27,840 the cities are actually children, you know, who have to receive presents. 113 00:06:27,840 --> 00:06:31,104 And the goal of Santa Claus is to visit them you know one, you know exactly once 114 00:06:31,104 --> 00:06:35,725 and minimize this travel distance that time its going to take for traveling. 115 00:06:35,725 --> 00:06:38,130 The and and bring these presents to everyone. 116 00:06:38,130 --> 00:06:40,580 Okay, so its this one of the that we can do. 117 00:06:40,580 --> 00:06:42,600 Okay one of the two that Santa Claus can do. 118 00:06:42,600 --> 00:06:46,630 Okay so you see, you know, you see basically 119 00:06:46,630 --> 00:06:51,530 You see basically the various the various cities that are being visited exactly 120 00:06:51,530 --> 00:06:53,726 once. Okay? 121 00:06:53,726 --> 00:06:59,030 And, and this is another tour. OK which looks better than the first one. 122 00:06:59,030 --> 00:07:01,620 So which one is actually the shortest one is probably this one. 123 00:07:01,620 --> 00:07:04,478 But that's what you want to find out. So you want to find out which is the 124 00:07:04,478 --> 00:07:08,210 tour, which is basically visiting all these, all these cities. 125 00:07:08,210 --> 00:07:12,541 Exactly once, and, and minimize the travel distance, the overall travel 126 00:07:12,541 --> 00:07:14,270 distance. Okay? 127 00:07:14,270 --> 00:07:17,702 So formally, you have a set of cities to visit, and you have a symmetry, you know, 128 00:07:17,702 --> 00:07:22,680 distance matrix, which is telling you the distance between every two cities. 129 00:07:22,680 --> 00:07:25,270 Okay? The fact that it's a symmetry distance 130 00:07:25,270 --> 00:07:28,300 matrix is actually pretty important. Okay? 131 00:07:28,300 --> 00:07:33,170 so what we want to do is to find a minimum, a tour of minimal cost. 132 00:07:33,170 --> 00:07:36,580 Which is visiting every city once. Okay, so you never want to come back to 133 00:07:36,580 --> 00:07:40,563 the same city twice, okay? And you are basically you basically want 134 00:07:40,563 --> 00:07:44,634 to minimize the sum of the, the distances between the cities that you're visiting, 135 00:07:44,634 --> 00:07:48,882 okay? as I said before, the traveling salesman 136 00:07:48,882 --> 00:07:52,131 problem is probably the most studied problems in all combinatorial 137 00:07:52,131 --> 00:07:55,539 optimization. And there are a lot of beautiful results 138 00:07:55,539 --> 00:08:00,000 in using many different approaches on this, on this particular problem. 139 00:08:00,000 --> 00:08:02,904 So this is essentially a very high level constraint programming model for this 140 00:08:02,904 --> 00:08:04,735 particular example. Okay? 141 00:08:04,735 --> 00:08:07,429 And is very similar to what we did for, you know? 142 00:08:07,429 --> 00:08:10,712 Euler Knight problems where, you know, we had this knight that had to move across 143 00:08:10,712 --> 00:08:14,655 the chess board and visit every one of the squares exactly once. 144 00:08:14,655 --> 00:08:17,820 Okay, so what you see here is that we have a set of cities. 145 00:08:17,820 --> 00:08:20,170 Okay, these are the cities that we want to visit. 146 00:08:20,170 --> 00:08:23,010 We have a distance matrix between everyone of these cities. 147 00:08:23,010 --> 00:08:26,121 That tells you, you know, how far these two cities, how far apart these two 148 00:08:26,121 --> 00:08:29,590 cities are. And then the decision variables start to 149 00:08:29,590 --> 00:08:32,740 say well for every one of these cities what is the next city that you, you will 150 00:08:32,740 --> 00:08:36,650 be visiting, that the traveling salesman will visit. 151 00:08:36,650 --> 00:08:39,331 Okay? And what you minimize is the sum, the sum 152 00:08:39,331 --> 00:08:44,210 of the travel distance. Okay, so which is. 153 00:08:44,210 --> 00:08:47,016 Which is essentially the only thing that you have to do is to take for every 154 00:08:47,016 --> 00:08:50,098 cities what is the distance to the next cities that the traveling salesmens have 155 00:08:50,098 --> 00:08:54,646 to visit from that popular city. And that's what this is denoting here, 156 00:08:54,646 --> 00:08:56,727 okay? And that eventually you want to have a 157 00:08:56,727 --> 00:09:01,408 circuit which means that you visit. Every city once and come back to the, to 158 00:09:01,408 --> 00:09:05,056 your starting point. Okay, so we're going to ignore the 159 00:09:05,056 --> 00:09:08,488 circuit constraints basically because we are going to assume that it's always 160 00:09:08,488 --> 00:09:14,152 satisfied, we maintain the circuit. So, essentially we will always be in a 161 00:09:14,152 --> 00:09:18,688 circuit like that, in a tour like this and the goal for us will be to move from, 162 00:09:18,688 --> 00:09:23,514 you know. But, you know, long tour to shorter and 163 00:09:23,514 --> 00:09:28,052 shorter and shorter tours, okay? And so what I want you to think about, is 164 00:09:28,052 --> 00:09:32,390 what is going to be the neighborhood in this particular case, okay? 165 00:09:32,390 --> 00:09:34,755 And so this is a problem when the neighborhoods start getting more 166 00:09:34,755 --> 00:09:38,160 interesting, right? So what is going to be the neighborhood 167 00:09:38,160 --> 00:09:43,059 for the traveling salesman problem? Okay, so think about it a little bit. 168 00:09:43,059 --> 00:09:46,557 Okay, now you will see that there are a lot of possible neighborhoods and this is 169 00:09:46,557 --> 00:09:49,733 one of them. It's called 2-OPT, okay, and the basic 170 00:09:49,733 --> 00:09:52,905 idea as I've told you before we want a tour, okay, we want to stay in you know 171 00:09:52,905 --> 00:09:57,730 this tourist you know, we always want to keep a feasible tour. 172 00:09:57,730 --> 00:10:01,480 So, what we going to do is select two edges, okay, inside our tour. 173 00:10:01,480 --> 00:10:04,630 And we going to replace them by two other edges, okay? 174 00:10:04,630 --> 00:10:06,810 So look at this. This is one of the tours that you see, 175 00:10:06,810 --> 00:10:09,038 okay? So you start from there, you move, you 176 00:10:09,038 --> 00:10:12,950 move, you move, you go up, you go there, and then you know, you go back. 177 00:10:12,950 --> 00:10:15,002 Okay? So and, and what is interesting in this 178 00:10:15,002 --> 00:10:17,270 particular case is that you see that there is a crossing there, you know, for 179 00:10:17,270 --> 00:10:20,270 this particular problem. The way I phrase it. 180 00:10:20,270 --> 00:10:22,530 This is always bad as soon as you have crossing. 181 00:10:22,530 --> 00:10:25,878 You know that you are not optimal. So you can decide to remove two edges, 182 00:10:25,878 --> 00:10:28,560 like these two edges over there. Right? 183 00:10:28,560 --> 00:10:30,515 So, these ones that were basically crossing. 184 00:10:30,515 --> 00:10:33,210 Okay? And then what you can do is to replace 185 00:10:33,210 --> 00:10:35,914 them by two other edges. And you have to make sure that you get a 186 00:10:35,914 --> 00:10:37,920 tour back. Okay? 187 00:10:37,920 --> 00:10:42,120 So, what you see here is essentially the tour and the edges that we are removing. 188 00:10:42,120 --> 00:10:44,940 You replace them by two other edges. Okay? 189 00:10:44,940 --> 00:10:50,660 So you see the two new you see the two new edges that we have inserted here. 190 00:10:50,660 --> 00:10:54,697 Okay, so this one and that one okay? And of course when you look at the actual 191 00:10:54,697 --> 00:10:57,735 specification of the tour and when you look at the tour here you know you see 192 00:10:57,735 --> 00:11:00,822 that some of the edges no are not in the right direction so you will have to fix 193 00:11:00,822 --> 00:11:04,871 them. But essentially what you do is select two 194 00:11:04,871 --> 00:11:07,991 edges, you replace them by two edges you fix the different direction of some of 195 00:11:07,991 --> 00:11:12,760 the edges. Such that you get another two. 196 00:11:12,760 --> 00:11:16,420 Okay, and that's essentially the 2-OPT neighborhood, okay? 197 00:11:16,420 --> 00:11:19,410 So what you do is you select two edges, okay? 198 00:11:19,410 --> 00:11:22,200 These two edges you know, will be removed from the two. 199 00:11:22,200 --> 00:11:24,950 Will be replaced by two other edges, okay? 200 00:11:24,950 --> 00:11:27,410 And then you will have to fix a little bit the tour in between the two edges 201 00:11:27,410 --> 00:11:31,660 that you've selected such that. You know, you get a two back, okay? 202 00:11:31,660 --> 00:11:35,894 So that's the 2-OPT neighborhood, okay? So in a sense, you know, you start from a 203 00:11:35,894 --> 00:11:39,788 tour and the neighborhood is all the set of tours that can be reached by swapping 204 00:11:39,788 --> 00:11:43,741 two edges. And, and by swap, by swapping out two 205 00:11:43,741 --> 00:11:48,200 edges and bringing two new edges inside the, inside, inside the tour. 206 00:11:49,320 --> 00:11:51,151 Okay? Now, you may say yeah, that's a 207 00:11:51,151 --> 00:11:55,080 neighborhood, but you know, why not swapping three edges. 208 00:11:55,080 --> 00:11:57,394 Okay? I want to remove three of them, and then 209 00:11:57,394 --> 00:12:01,180 essentially replace by three other edges. Okay? 210 00:12:01,180 --> 00:12:03,170 So that's, that's obviously a nice neighborhood. 211 00:12:03,170 --> 00:12:04,830 This is called 3-OPT. Okay? 212 00:12:04,830 --> 00:12:07,770 And you see the idea here, you see the pattern, right? 213 00:12:07,770 --> 00:12:11,215 So, this point scientists love this, because now we can write infinitely many 214 00:12:11,215 --> 00:12:14,980 papers, right? We can do 2-OPT, 3-OPT, 4-OPT, 5-OPT. 215 00:12:14,980 --> 00:12:16,300 Okay? So this is nice. 216 00:12:16,300 --> 00:12:18,990 Okay? So so this is this is 2-OPT okay? 217 00:12:18,990 --> 00:12:21,938 So remember, you know, I told you before crossings are terrible so you can remove 218 00:12:21,938 --> 00:12:25,384 these things, okay? You can remove these two edges, replace 219 00:12:25,384 --> 00:12:30,190 them by two other edges, okay? That one and this one, okay? 220 00:12:30,190 --> 00:12:34,018 And now you have an, so that's basically 2-OPT, okay, and you are to replace, you 221 00:12:34,018 --> 00:12:37,556 know, the orientation of the edges around, around that part of the cycle, 222 00:12:37,556 --> 00:12:42,550 okay? Now, 3-OPT is going to be removing three. 223 00:12:42,550 --> 00:12:45,280 Edges, okay? So you see this one, you see this one, 224 00:12:45,280 --> 00:12:47,380 you see that one. Okay? 225 00:12:47,380 --> 00:12:52,000 So this out of three edges that we remove, and know we are three edges 1, 2, 226 00:12:52,000 --> 00:12:56,245 and 3 here. which are basically the three edges that 227 00:12:56,245 --> 00:12:59,960 we are replacing the original edges by. Okay? 228 00:12:59,960 --> 00:13:03,370 Now this is a 3-OPT, we have to reverse the direction of that edge and you get 229 00:13:03,370 --> 00:13:08,015 another nice two, okay? So we saw 2-OPT, we saw 3-OPT. 230 00:13:08,015 --> 00:13:09,778 Okay? And you may wonder, you know, what is the 231 00:13:09,778 --> 00:13:12,821 difference between them? Well, usually 3-OPT is going to be better 232 00:13:12,821 --> 00:13:16,850 because it, it contains 2-OPT as a, as a, as a, as, as, as a sub-neighborhood. 233 00:13:16,850 --> 00:13:21,590 It's in general much better than 2-OPT, okay, in quality. 234 00:13:21,590 --> 00:13:24,200 But it's also more expensive because now we have to. 235 00:13:24,200 --> 00:13:27,788 Examine, you know, a much larger set of, of combinations, okay? 236 00:13:27,788 --> 00:13:31,500 I told you that, you know, computer scientists love this thing because now we 237 00:13:31,500 --> 00:13:35,386 can, we can start investigating 4-OPT and typically, if you do that you will find 238 00:13:35,386 --> 00:13:40,872 out obviously 4-OPT is going to be. Better in quality but now it's become 239 00:13:40,872 --> 00:13:45,400 really, really, really more expansive. And then you may say, okay but what about 240 00:13:45,400 --> 00:13:48,550 5-OPT, and at that point there is this genius which is basically killing the 241 00:13:48,550 --> 00:13:54,370 entire, you know, set of paper, okay? Because it's going to define K-OPT, okay? 242 00:13:54,370 --> 00:13:57,566 And basically the key ID here, is instead of looking at these neighborhoods one at 243 00:13:57,566 --> 00:14:01,910 a time, you may say well you know. Typically there will be a good k but I 244 00:14:01,910 --> 00:14:05,506 don't know what it is, okay? And so essentially what I want to do is 245 00:14:05,506 --> 00:14:09,200 replace the notion of, okay I'm basically doing a swap. 246 00:14:09,200 --> 00:14:12,480 We've a sequence of swaps. I'm going to look at a sequence of swaps 247 00:14:12,480 --> 00:14:15,670 that I can do and for and, and, and then dynamically I will choose which 248 00:14:15,670 --> 00:14:18,817 sub-sequence is really nice. Okay? 249 00:14:18,817 --> 00:14:22,145 So, of course I won't search the, the entire set of sequences, they are way too 250 00:14:22,145 --> 00:14:25,426 many of them. But I'm going to explore the seq, you 251 00:14:25,426 --> 00:14:29,332 know I am going to build the sequence dynamically, and try to find an amazingly 252 00:14:29,332 --> 00:14:34,956 avoid, for instance, selecting. The same cities twice and things like 253 00:14:34,956 --> 00:14:37,523 this. So I'm going to build only one sequence 254 00:14:37,523 --> 00:14:41,358 in an incremental fashion and trying to have, to build a sequence over certain 255 00:14:41,358 --> 00:14:45,460 quality but at a high level this is what you do. 256 00:14:45,460 --> 00:14:49,198 Right,so you start with. One possible, one possible move and then 257 00:14:49,198 --> 00:14:53,551 you start exploring all at once and you move along this shunt. 258 00:14:53,551 --> 00:14:57,091 And so at the beginning you know by performing more swaps, by being, you 259 00:14:57,091 --> 00:15:02,293 know, making several swaps in sequence. I may actually, weaken the quality of a 260 00:15:02,293 --> 00:15:05,953 solution but at some point it can be really become very good and then it can 261 00:15:05,953 --> 00:15:09,998 deteriorate. It can actually deteriorate the quality 262 00:15:09,998 --> 00:15:12,680 of the solution. And then at some point, you know, you 263 00:15:12,680 --> 00:15:14,690 stop because you have selected everything. 264 00:15:14,690 --> 00:15:18,920 And so the key idea of K-OPT is that you, you, you explore this sequence. 265 00:15:18,920 --> 00:15:23,600 And then you step back and you say, well, but what was the best sub-sequence? 266 00:15:23,600 --> 00:15:25,280 And in this particular case, you'll find it here. 267 00:15:25,280 --> 00:15:27,780 This is where the best improvement was obtained. 268 00:15:27,780 --> 00:15:31,095 And so what you now that you have to do is basically perform these sub-sequence 269 00:15:31,095 --> 00:15:35,640 of move and, if you do so, you will have the best improvement here, okay? 270 00:15:35,640 --> 00:15:39,820 So the key point is to try to build incrementally this sequence. 271 00:15:39,820 --> 00:15:43,006 And then, when you have built the entire thing, you look back at the best 272 00:15:43,006 --> 00:15:47,240 sub-sequence and you execute that, okay? So, how do we do that? 273 00:15:47,240 --> 00:15:50,092 Essentially, you want to find, you know, essentially what, if you, I try to 274 00:15:50,092 --> 00:15:53,871 summarize what we just did. We tried to find you know, the key, key 275 00:15:53,871 --> 00:15:57,891 moves that are really good, okay? Dynamically while trying to do that, 276 00:15:57,891 --> 00:15:59,520 okay? We are not trying to fix K at the 277 00:15:59,520 --> 00:16:02,312 beginning. We are trying to find a good, you know, 278 00:16:02,312 --> 00:16:05,660 set a good sequence of moves that will improve the cost, you know, 279 00:16:05,660 --> 00:16:09,780 significantly. And so we are basically exploring, you 280 00:16:09,780 --> 00:16:14,415 know, sub-sequence of higher and higher, you know, longer and longer sizes. 281 00:16:14,415 --> 00:16:18,260 Okay, so this is, this is what K-OPT does. 282 00:16:18,260 --> 00:16:20,700 Okay, so if we look at these slides you won't understand anything. 283 00:16:20,700 --> 00:16:23,340 If you don't see a picture, it's not going to work but this is let me just go 284 00:16:23,340 --> 00:16:26,830 over so as to get an intuition of what we are trying to do. 285 00:16:26,830 --> 00:16:30,650 So what we'll do is we'll take a vertex and that vertex is a successor. 286 00:16:30,650 --> 00:16:34,432 That, that we have an edge there and let's assume that this edge is very long 287 00:16:34,432 --> 00:16:37,165 okay? So what we're going to do is we're 288 00:16:37,165 --> 00:16:40,529 going to look at the next vertex in the sequence and we going to try to select 289 00:16:40,529 --> 00:16:45,146 another edge which is very sharp. So the basic idea is that we want to swap 290 00:16:45,146 --> 00:16:47,740 these two edge okay? Of course, when you do that there is 291 00:16:47,740 --> 00:16:51,280 another edge which was pointing to that success so we have to remove it. 292 00:16:51,280 --> 00:16:55,166 And then essentially you can connect the first one to the, the vertex that we just 293 00:16:55,166 --> 00:16:59,000 disconnected. And then you have a two, okay? 294 00:16:59,000 --> 00:17:01,380 So you have essentially a two-swap move, okay? 295 00:17:01,380 --> 00:17:04,715 So let's look at that visually, okay? So we come back to this slide afterwards. 296 00:17:04,715 --> 00:17:08,050 Okay? So we select t1, right, okay? 297 00:17:08,050 --> 00:17:10,666 So that's what we have, okay, and we select t2, okay? 298 00:17:10,666 --> 00:17:13,800 So that's basically, we select this edge. And this edge is long. 299 00:17:13,800 --> 00:17:17,086 So we say, maybe we can actually find something which is shorter than that, 300 00:17:17,086 --> 00:17:21,110 okay? So we select another vertex t3, okay? 301 00:17:21,110 --> 00:17:24,160 So that's you see over here, okay? And then this edge here is short compared 302 00:17:24,160 --> 00:17:27,525 to the edge so we're going to remove that and put that edge. 303 00:17:27,525 --> 00:17:29,886 Okay? Obviously now, we have these edges here 304 00:17:29,886 --> 00:17:32,870 which, you know, we have two edges going that are going to t3. 305 00:17:32,870 --> 00:17:35,489 That's not good. So, t4 there, we have to remove that 306 00:17:35,489 --> 00:17:39,284 edge, okay? And now, the key point is that if we take 307 00:17:39,284 --> 00:17:45,935 t1, okay, and we connect it to the, to, to, to t4 here, we would have. 308 00:17:45,935 --> 00:17:50,142 we would have another tour. Right, so this is what we see on this 309 00:17:50,142 --> 00:17:52,836 one. Okay, so and the key ID is that we could 310 00:17:52,836 --> 00:17:56,150 do that. Okay, so this is a two-swap move. 311 00:17:56,150 --> 00:17:59,368 But we won't do it. Okay so we won't, we won't connect t1 to 312 00:17:59,368 --> 00:18:02,163 t4. Okay, because the reason is that we want 313 00:18:02,163 --> 00:18:06,110 to explore this sequences of move. Okay, so if we look at the slides that 314 00:18:06,110 --> 00:18:09,870 I've shown you before which was impossible to understand for anyone. 315 00:18:09,870 --> 00:18:13,315 You know, in his own mind. So the only, so you see now that we have 316 00:18:13,315 --> 00:18:16,780 these two edges, you know X1 and X2, so that was the long one and the short one, 317 00:18:16,780 --> 00:18:20,276 okay? And then, essentially, what i was telling 318 00:18:20,276 --> 00:18:23,632 you is that when we connect T4 to T1 we have a tour again, okay? 319 00:18:23,632 --> 00:18:26,668 But what I'm saying, what I'm telling you to do now is that you compute the cost of 320 00:18:26,668 --> 00:18:29,796 this, this is, you know, in the beautiful sequence that I've shown you, that's one 321 00:18:29,796 --> 00:18:33,720 of the cost. But we don't want to connect them. 322 00:18:33,720 --> 00:18:35,703 No, we don't. We are going to continue doing 323 00:18:35,703 --> 00:18:38,670 interesting things, okay? So what are we going to do? 324 00:18:38,670 --> 00:18:40,470 Okay? We going to simply consider, you know, 325 00:18:40,470 --> 00:18:43,890 basically swap t4 with t2 in the slides that I've shown you. 326 00:18:43,890 --> 00:18:47,190 So we basically restart the process but the edge that we select, no is not 327 00:18:47,190 --> 00:18:50,470 between t1 and t2, it's going to be t1 and t4. 328 00:18:50,470 --> 00:18:54,569 That's a long edge, most likely. And therefore we try to see if we can 329 00:18:54,569 --> 00:18:57,440 connect t4 to something which is smaller, okay? 330 00:18:57,440 --> 00:19:01,050 And that's what we do here, right? So we have these long edges, no? 331 00:19:01,050 --> 00:19:03,700 Okay? Between t1 and t4. 332 00:19:03,700 --> 00:19:07,600 And what we want to do is, can I find a shorter edge, and do the same process 333 00:19:07,600 --> 00:19:11,625 again, okay? And of course here we connect, for 334 00:19:11,625 --> 00:19:13,890 instance, t4 to t5. Okay? 335 00:19:13,890 --> 00:19:17,481 And then, no of use, the, there are two things pointing to t5, okay, so we have 336 00:19:17,481 --> 00:19:21,920 to remove one of them, okay? So we remove this guy, okay? 337 00:19:21,920 --> 00:19:27,224 And now, what we do, is basically, once again, what would be nice now is that, we 338 00:19:27,224 --> 00:19:31,816 could connect actually t6 and t1. Okay? 339 00:19:31,816 --> 00:19:35,590 Or t1 and t6, okay? And get, that's what you see over there, 340 00:19:35,590 --> 00:19:38,420 and get another two. Okay? 341 00:19:38,420 --> 00:19:41,326 Now, do we want to do it? No, no, no, no, we don't want to connect 342 00:19:41,326 --> 00:19:44,142 at this point. We just want to compute the cost and say 343 00:19:44,142 --> 00:19:48,080 wow, this is like, a 3-OPT, okay? I have the cost of this 3-OPT, no I have 344 00:19:48,080 --> 00:19:51,390 the cost of 2-OPT, I have the cost of 3-OPT, okay? 345 00:19:51,390 --> 00:19:54,180 I can compare which one is better, but I don't want to stop there. 346 00:19:54,180 --> 00:19:56,286 Right? Once again, what I'm going to do is, do 347 00:19:56,286 --> 00:20:00,898 the same algorithm that I've shown you. But instead of starting with t1 and t2, 348 00:20:00,898 --> 00:20:05,128 I'm starting with t1 and t6. Of course, that edge doesn't exist, but I 349 00:20:05,128 --> 00:20:08,944 just pretend it's there. And then from t6, I'm trying to find out 350 00:20:08,944 --> 00:20:13,030 if there is a shorter edge to this t1, t6 edge. 351 00:20:13,030 --> 00:20:14,680 Okay? And that's what I do. 352 00:20:14,680 --> 00:20:16,520 Okay? So, I looked at a. 353 00:20:16,520 --> 00:20:18,209 T6 over here. Okay? 354 00:20:18,209 --> 00:20:20,320 And I tried to see if there is a smaller edge. 355 00:20:20,320 --> 00:20:21,720 That's what you see over there. Right? 356 00:20:21,720 --> 00:20:25,689 And once again, I have to remove you know, the other edge that was pointing to 357 00:20:25,689 --> 00:20:27,510 t7. Okay? 358 00:20:27,510 --> 00:20:29,560 So, which was this guy over here. Right? 359 00:20:29,560 --> 00:20:34,020 And now, I can you know, once again connect it to t8. 360 00:20:34,020 --> 00:20:35,500 Okay? T1 to t8. 361 00:20:35,500 --> 00:20:37,490 Okay? And now, I have a 4-OPT. 362 00:20:37,490 --> 00:20:39,498 Okay? So, what you see, what you are seeing me 363 00:20:39,498 --> 00:20:42,560 doing here is doing, okay, I have a 2-OPT. 364 00:20:42,560 --> 00:20:46,025 Then I continue to search, I get 3-OPT [SOUND], I continue and I get 4-OPT and 365 00:20:46,025 --> 00:20:49,325 in this particular case I'm going to be stuck at this point because from t8 I 366 00:20:49,325 --> 00:20:54,090 won't find and edge which is smaller than that, okay? 367 00:20:54,090 --> 00:20:56,400 And so I can stop and this is my sequence. 368 00:20:56,400 --> 00:20:59,536 Then I can look at the various tour that I seen, you know, the 2-OPT, the 3-OPT, 369 00:20:59,536 --> 00:21:02,660 the 4-OPT and select the one which is better. 370 00:21:02,660 --> 00:21:05,142 Okay? The key point here is that I'm not 371 00:21:05,142 --> 00:21:08,838 exploring the entire neighborhood for 4-OPT or the entire neighborhood of the 372 00:21:08,838 --> 00:21:12,804 sequence. The only that I am doing is building the 373 00:21:12,804 --> 00:21:17,350 sequence of move, one step at a time. And then I look back, I step back and I 374 00:21:17,350 --> 00:21:20,090 say which one was the best? Okay? 375 00:21:20,090 --> 00:21:21,960 And that's the one that we select. Okay? 376 00:21:21,960 --> 00:21:24,898 For the first iteration. And let's assume that this was the last 377 00:21:24,898 --> 00:21:27,330 one because this looks like an i two, right? 378 00:21:27,330 --> 00:21:30,150 So, at this point, I've done one iteration, I've found one sequence, and 379 00:21:30,150 --> 00:21:34,350 the best move in that sequence. Now, I start the second sequence. 380 00:21:34,350 --> 00:21:36,630 Okay? So, I start the second iteration. 381 00:21:36,630 --> 00:21:38,725 Okay? And let's say that I, that my t1 is over 382 00:21:38,725 --> 00:21:42,068 there, this is t2. I decide to link t2 to this guy because 383 00:21:42,068 --> 00:21:45,530 that's a very short edge. So, it's smaller than this one. 384 00:21:45,530 --> 00:21:47,828 And then I do the same. And this is essentially the first 385 00:21:47,828 --> 00:21:52,110 configuration that I get. And then I take another edges, you know 386 00:21:52,110 --> 00:21:56,900 from t4 to t5 I get the t6 over there. I reconnect this. 387 00:21:56,900 --> 00:21:59,380 And this is the beautiful tour that I get afterwards. 388 00:21:59,380 --> 00:22:02,270 Is it better than the previous one? Well we would have to compare the cost. 389 00:22:02,270 --> 00:22:04,777 But essentially no. I'm basically showing you how this 390 00:22:04,777 --> 00:22:07,410 sequence will work. Have, have been working, right? 391 00:22:07,410 --> 00:22:09,380 So you select the first sequence. That's the sequence of move. 392 00:22:09,380 --> 00:22:11,300 You select the best of them. Okay? 393 00:22:11,300 --> 00:22:14,134 Then you move to another iteration. You select another vertex, you select 394 00:22:14,134 --> 00:22:16,702 these edges. And you keep selecting this sequence and 395 00:22:16,702 --> 00:22:19,625 then the sub-sequence which is optimal. And that's K-OPT. 396 00:22:19,625 --> 00:22:21,980 Okay? So, you see, what we have done here 397 00:22:21,980 --> 00:22:24,754 essentially. Is looking at neighborhoods that are much 398 00:22:24,754 --> 00:22:28,154 more sophisticated at just assigning a variable to a variable, or assigning, you 399 00:22:28,154 --> 00:22:30,790 know, swapping two values. Okay? 400 00:22:30,790 --> 00:22:34,175 So, we are trying essentially to find a good sequence of moves. 401 00:22:34,175 --> 00:22:36,788 Okay? And this is a very, very effective 402 00:22:36,788 --> 00:22:42,547 neighborhood for this traveling salesman problem, okay, so, summary here, okay? 403 00:22:42,547 --> 00:22:45,680 We saw two problems, which were optimization problem. 404 00:22:45,680 --> 00:22:48,181 We looked at one which is warehouse location where there were very simple 405 00:22:48,181 --> 00:22:51,274 neighborhoods. We looked at a TSP which has essentially, 406 00:22:51,274 --> 00:22:54,405 a variety of neighborhoods that you can apply. 407 00:22:54,405 --> 00:22:57,262 Okay? And they will have different strengths 408 00:22:57,262 --> 00:23:00,718 and K-OPT is something that is focusing on essentially finding a sequence of 409 00:23:00,718 --> 00:23:04,650 move. Not a sequence, not a single move. 410 00:23:04,650 --> 00:23:06,438 Okay? Thank you very much, and next time we'll 411 00:23:06,438 --> 00:23:07,730 see graph coloring.