1 00:00:00,025 --> 00:00:03,160 Okay discrete optimization, but I can tabu search. 2 00:00:03,160 --> 00:00:06,454 so I want to spend a little bit of time on tabu search because this is very 3 00:00:06,454 --> 00:00:11,460 interesting and I want to, I want to tell you a little bit of a story before. 4 00:00:11,460 --> 00:00:14,994 So, so, John Hooker once told me that, for every invention, there are very, 5 00:00:14,994 --> 00:00:18,902 there are three stages. Okay, so the first stage is that people 6 00:00:18,902 --> 00:00:22,318 are going to look at the invention, and say oh, this can't work, okay, this is 7 00:00:22,318 --> 00:00:26,006 all wrong, okay? And so that's the first stage and then 8 00:00:26,006 --> 00:00:28,996 you go to the second stage where people realize that this is actually working, 9 00:00:28,996 --> 00:00:32,360 but then would say, oh, but this is trivial, okay? 10 00:00:32,360 --> 00:00:36,150 So, that's the second phase of an invention, people will say it's trivial. 11 00:00:36,150 --> 00:00:38,412 And of course that lasts for a while and then the third stage is the most 12 00:00:38,412 --> 00:00:41,532 interesting one. People will say, oh, that invention, I 13 00:00:41,532 --> 00:00:45,340 invented it. Okay, i'ts a footnote in my thesis, okay? 14 00:00:45,340 --> 00:00:48,304 So tabu searches like that. Okay, so amazing thing, you know it was 15 00:00:48,304 --> 00:00:51,766 invented by you know Fred Glover. And the first time you look at this, you 16 00:00:51,766 --> 00:00:54,514 say, well this can't work right? So and then could and you see on your 17 00:00:54,514 --> 00:00:57,504 favorite problem these reserves that are coming up and are amazing most of the 18 00:00:57,504 --> 00:01:01,370 time right? So you say, wow this actually very, you 19 00:01:01,370 --> 00:01:04,728 know this is actually working. But it's so simple it's not even 20 00:01:04,728 --> 00:01:07,596 interesting right? And then afterwards, you spend your life 21 00:01:07,596 --> 00:01:08,820 working on tabu search. Right? 22 00:01:08,820 --> 00:01:10,940 So, this is, this is what tabu search can do to you. 23 00:01:10,940 --> 00:01:13,300 Okay? So, so I want to spend some time in 24 00:01:13,300 --> 00:01:18,583 telling you some of the richness of this particular meta heuristic. 25 00:01:18,583 --> 00:01:21,889 And, and, and all the issues that you have in trying to design the right 26 00:01:21,889 --> 00:01:26,730 compromise between different aspect of, of tabu search algorithm. 27 00:01:26,730 --> 00:01:29,802 So remember what we wanted to do is that we start from a point, we go back down to 28 00:01:29,802 --> 00:01:32,950 a local minimum. And then sometimes we go back up, and 29 00:01:32,950 --> 00:01:36,870 then, and we want, we have the ability to go back up and then to go down. 30 00:01:36,870 --> 00:01:40,458 If we don't have anything, typically you, you can't escape this local minimum, you 31 00:01:40,458 --> 00:01:43,430 would stay here all the time. Okay. 32 00:01:43,430 --> 00:01:46,370 So the idea of tabu search is that you know, one, once you have been to, to a 33 00:01:46,370 --> 00:01:49,480 particular state you consider it tabu. Okay? 34 00:01:49,480 --> 00:01:51,610 So you have seen it, you don't want to go back there. 35 00:01:51,610 --> 00:01:53,290 Okay? And then you can start going up to a 36 00:01:53,290 --> 00:01:57,508 particular node like you know, this one. And obviously when you are there you, you 37 00:01:57,508 --> 00:02:00,430 know, if you have something like a you know, greedy approach. 38 00:02:00,430 --> 00:02:03,030 This guy may be in the neighborhood and then you will want to go there. 39 00:02:03,030 --> 00:02:05,448 Okay? But since it's tabu you can't go there, 40 00:02:05,448 --> 00:02:10,080 so you will have to find the next best. If you have let's say a greedy approach. 41 00:02:10,080 --> 00:02:11,850 Okay? And this one may be the next best, and 42 00:02:11,850 --> 00:02:14,426 so, so you move up there. And once again, when you are up there, 43 00:02:14,426 --> 00:02:16,273 this guy will say, ooh, I want to be greedy. 44 00:02:16,273 --> 00:02:18,433 And he's going to look at this one, and of course the first one, and say, ooh, 45 00:02:18,433 --> 00:02:21,676 that's where I want to go. But once again, you can't do that because 46 00:02:21,676 --> 00:02:24,710 you are tabu and so you go up. And now you are the top of this, top of 47 00:02:24,710 --> 00:02:27,880 this landscape, and you can actually start going down. 48 00:02:27,880 --> 00:02:31,689 To to the ultimate solution, okay. So in a sense, the key abstract idea of 49 00:02:31,689 --> 00:02:34,874 tabu search is that you keyboard knows that you visited, okay, and you never go 50 00:02:34,874 --> 00:02:38,406 back there. Okay, so you have been there, seen them, 51 00:02:38,406 --> 00:02:42,366 no way you want to return to them, okay. So this is the pres, you know, the tabu 52 00:02:42,366 --> 00:02:46,059 search algorithm that I've shown you. The key aspect here is that you always 53 00:02:46,059 --> 00:02:50,470 skip this tabu list of all, essentially, the nodes that you have visited so far. 54 00:02:50,470 --> 00:02:54,364 This tool is that you increase every time you move to another, another, another 55 00:02:54,364 --> 00:02:57,280 state, okay? Now, one of the basic issues with the 56 00:02:57,280 --> 00:03:00,184 tabu-search algorithm is that, you know, if, if, you, you want to select the best 57 00:03:00,184 --> 00:03:02,990 configuration that is not tabu. Okay? 58 00:03:02,990 --> 00:03:05,494 So that's what we have seen. But one of the basic issues is that it's 59 00:03:05,494 --> 00:03:08,610 very expensive to maintain all these states that you been there. 60 00:03:08,610 --> 00:03:09,972 Right? So assume that you have, you know, 61 00:03:09,972 --> 00:03:12,480 thousands of variables. You would have to keep them, and you may 62 00:03:12,480 --> 00:03:15,606 visit, you know. So, as I've shown you last time you know, 63 00:03:15,606 --> 00:03:19,107 100's of 1000's of configuration. So you start using a lot of space and 64 00:03:19,107 --> 00:03:21,902 every time you have to try to, every time you select a neighbor, you have to say, 65 00:03:21,902 --> 00:03:25,454 oh, is it legal or not. So you have to compare it with all the 66 00:03:25,454 --> 00:03:28,020 stuff that you have varied. That you have seen. 67 00:03:28,020 --> 00:03:31,465 So it's very, you know, expensive from, let's say, a time and a space, you know, 68 00:03:31,465 --> 00:03:34,347 standpoint. So what you can do is to use what is 69 00:03:34,347 --> 00:03:37,870 called a Short-Term Memory. Instead of actually looking, keeping all 70 00:03:37,870 --> 00:03:40,768 these notes, you are going to only look at certain, you can only keep a subset of 71 00:03:40,768 --> 00:03:43,800 them. And essentially, the recent ones. 72 00:03:43,800 --> 00:03:46,190 You are looking at a subset of these two lists, okay? 73 00:03:46,190 --> 00:03:48,918 And so you, you look at the suffix of that list, which already knows that you 74 00:03:48,918 --> 00:03:52,115 have visited recently. And what you're basically saying, I don't 75 00:03:52,115 --> 00:03:54,570 want to go to the stuff that I've been recently, okay? 76 00:03:54,570 --> 00:03:57,518 So, because you have, you know, you, you can expect that, you know, the nodes that 77 00:03:57,518 --> 00:04:00,660 you haven't seen for a while, they are very far away. 78 00:04:00,660 --> 00:04:02,950 They are not inside your neighborhood, so you don't care about that. 79 00:04:02,950 --> 00:04:05,250 Okay? So if you keep, you know, if you keep a 80 00:04:05,250 --> 00:04:08,706 fixed length list, tabu list, okay, so you basically, you know, keep the last 81 00:04:08,706 --> 00:04:12,820 20, who knows if you have something like this, okay. 82 00:04:12,820 --> 00:04:16,832 Of course, in practice, you can dynamically increase or decrease this 83 00:04:16,832 --> 00:04:20,912 list to get a good compromise in not being stuck in a local minimum but not 84 00:04:20,912 --> 00:04:25,196 preventing, you know, not, not preventing, you know, you to actually 85 00:04:25,196 --> 00:04:32,860 diversify this this, the search too much. So you can decrease, for instance, the 86 00:04:32,860 --> 00:04:35,830 size of the list if the, the objective functions is, is degrading, or, you know, 87 00:04:35,830 --> 00:04:40,620 increasing it when the, when you actually improving the objective all the time. 88 00:04:40,620 --> 00:04:45,500 So you can use things like this, okay? So, so, the, the question that you have 89 00:04:45,500 --> 00:04:50,330 is that at that point you are still storing entire consideration. 90 00:04:50,330 --> 00:04:52,420 Okay? And that means still be too costly. 91 00:04:52,420 --> 00:04:54,395 Sometimes it's not. You can actually implement things like 92 00:04:54,395 --> 00:04:56,463 this. But sometimes you, you are going to say, 93 00:04:56,463 --> 00:04:59,597 wow, this is really costly. I have to store this entire state, I have 94 00:04:59,597 --> 00:05:02,550 to do all this comparison that's, you know, taking a lot of time. 95 00:05:02,550 --> 00:05:06,444 And my sense is that I want to, you know, valid, many, many configurations very, 96 00:05:06,444 --> 00:05:09,760 very quickly. So, so, what you can do is, is instead 97 00:05:09,760 --> 00:05:13,335 of, you know, storing these states, you are going to store an abstraction of this 98 00:05:13,335 --> 00:05:17,389 suffix, okay. And the way show this abstraction can be 99 00:05:17,389 --> 00:05:20,316 arbitrarily complicated or arbitrarily simple. 100 00:05:20,316 --> 00:05:23,602 But you have to find a way of very concisely abstracting these sets of nodes 101 00:05:23,602 --> 00:05:26,930 that you have visited recently. Okay? 102 00:05:26,930 --> 00:05:28,970 Now, many possibilities, and I'm going to show you some of them. 103 00:05:28,970 --> 00:05:30,640 Okay? So, this is the car sequencing 104 00:05:30,640 --> 00:05:34,056 applications that I've shown you before. Okay, once again, you have this assembly 105 00:05:34,056 --> 00:05:36,144 line. You can swap, you know, different 106 00:05:36,144 --> 00:05:40,407 different slots of the assembly line. And this is a, this is a greedy local 107 00:05:40,407 --> 00:05:44,329 improvement algorithm, and what you do is you select essentially a particular slot, 108 00:05:44,329 --> 00:05:48,466 which is, which has violation. You are violating some capacity 109 00:05:48,466 --> 00:05:50,641 constraint. You select another slot, that's a 110 00:05:50,641 --> 00:05:54,780 quadratic neighborhood, okay. And then you are basically saying, oh, I 111 00:05:54,780 --> 00:05:57,653 want to take the best of these moves, okay. 112 00:05:57,653 --> 00:06:00,773 And so you apply the move and it's improved the, the value of the object if 113 00:06:00,773 --> 00:06:03,930 you take it. Otherwise, you, you know, you, you're in 114 00:06:03,930 --> 00:06:06,650 a local minimum, so you break the search. Okay. 115 00:06:06,650 --> 00:06:11,200 So this is a greedy algorithm, okay. And so, what I want to do here is 116 00:06:11,200 --> 00:06:15,324 implement a tabu search algorithm. But I wan, I don't want to keep this 117 00:06:15,324 --> 00:06:18,807 configuration as I told you. We can you know, we can explore hundreds 118 00:06:18,807 --> 00:06:22,701 of thousands of them and then maybe you know, 300 you know, slots you know, they, 119 00:06:22,701 --> 00:06:27,604 they maybe come 300 slots or more. So this is a lot of space and a lot of 120 00:06:27,604 --> 00:06:30,410 time that you would spend just comparing these things. 121 00:06:30,410 --> 00:06:33,138 So what we're going to do is that instead of storing these states, we are going to 122 00:06:33,138 --> 00:06:36,240 store the transition not the state them self. 123 00:06:36,240 --> 00:06:38,250 And the transition in this particular case is what. 124 00:06:38,250 --> 00:06:41,746 I'm just swap 2 cars, okay. So you're basically saying okay so a move 125 00:06:41,746 --> 00:06:45,240 is swapping these 2 cars, okay ai and aj in the assembly line. 126 00:06:45,240 --> 00:06:49,110 And so what I'm going to store inside the tabu-list is these pairs, ai, aj okay. 127 00:06:49,110 --> 00:06:54,006 right actually I, I wrote ai, bi okay, so our basically you are remembering that 128 00:06:54,006 --> 00:07:00,730 you swap these 2, you know you swap these 2 slots on the assembly line. 129 00:07:00,730 --> 00:07:04,258 And the key idea is that you know in the future you don't want to re swap this two 130 00:07:04,258 --> 00:07:08,860 because you are going back to place where you have been, okay. 131 00:07:08,860 --> 00:07:12,668 So instead of keeping the state you are basically keeping the operation that have 132 00:07:12,668 --> 00:07:16,364 been moving you from state to state and in this particular case is basically the 133 00:07:16,364 --> 00:07:20,396 swaps, okay. And so configuration is going to be tabu 134 00:07:20,396 --> 00:07:24,204 in this particular abstraction if it can be obtained by swapping two things which 135 00:07:24,204 --> 00:07:28,964 are inside, inside the, the tabu list. So, so what you're going to do is that 136 00:07:28,964 --> 00:07:32,036 you're only going to look at the swaps essentially which are not inside the tabu 137 00:07:32,036 --> 00:07:33,599 list. Okay? 138 00:07:33,599 --> 00:07:36,880 So you can swap things that you have been swapping recently. 139 00:07:36,880 --> 00:07:39,180 That's basically the abstraction here. Okay? 140 00:07:39,180 --> 00:07:42,218 So in a sense, you are not storing the states, you are not really, you are not 141 00:07:42,218 --> 00:07:46,540 really actually abstracting them in a complete you know, exact fashion. 142 00:07:46,540 --> 00:07:50,050 But you are basically remembering some operations that you have done so far. 143 00:07:50,050 --> 00:07:52,170 And you don't want to apply these operations again. 144 00:07:52,170 --> 00:07:53,590 That's the kind of things that you do here. 145 00:07:53,590 --> 00:07:57,200 Okay, so how do we implement this. So, this is the basic idea. 146 00:07:57,200 --> 00:08:01,658 So what you do is you keep a counter IT. Which basically denotes the iterations 147 00:08:01,658 --> 00:08:05,403 that you are in inside the the algorithm. Okay, so every time you perform a move 148 00:08:05,403 --> 00:08:09,740 that counter is going to be incremented. So this is the IT you know counter. 149 00:08:09,740 --> 00:08:14,720 Then what you use is a data structure, tabu ij, okay where i and j are the 2. 150 00:08:14,720 --> 00:08:19,076 Two slots that you can, can, can swap and that data structure is going to represent 151 00:08:19,076 --> 00:08:25,110 the first iteration when it's going to be legal to actually swap i and j again. 152 00:08:25,110 --> 00:08:27,260 So, so think about, think about it this way. 153 00:08:27,260 --> 00:08:29,089 Okay? So i and j, you have just performed the 154 00:08:29,089 --> 00:08:31,030 swap between i and j. Okay? 155 00:08:31,030 --> 00:08:33,531 And you want to make sure that you're not going to sub these two guys for a bunch 156 00:08:33,531 --> 00:08:36,834 of iterations. So inside tabu ij, you remember, you, 157 00:08:36,834 --> 00:08:41,256 okay, you store the next, next iteration, where it will be legal to actually swap 158 00:08:41,256 --> 00:08:46,220 these two slots, okay. So, and, and, so, in, in the next two, 159 00:08:46,220 --> 00:08:50,219 two conditions here, I'm going to used a fixed tabu size of L. 160 00:08:50,219 --> 00:08:53,579 But you could, you know, you could have a dynamic on each side, so the same 161 00:08:53,579 --> 00:08:58,130 principle applies. Okay, so, so essentially, when is a move 162 00:08:58,130 --> 00:09:01,175 tabu? Okay, so a move is going to be tabu. 163 00:09:01,175 --> 00:09:04,833 Is the value tabu i,j so, i,j is going to be tabu if tabu i,j is actually greater 164 00:09:04,833 --> 00:09:07,580 the iteration number. Okay. 165 00:09:07,580 --> 00:09:11,675 So that means that [UNKNOWN] is only later than I will be allowed to actually 166 00:09:11,675 --> 00:09:15,975 swab these 2 guys. If the counter is smaller, that mean you 167 00:09:15,975 --> 00:09:18,390 okay can swap it. You know, it's allowed at this point. 168 00:09:18,390 --> 00:09:20,680 It's legal at this point to swap these 2 guys. 169 00:09:20,680 --> 00:09:24,390 So it's very easy here in constant time if you can find if a move is tabu. 170 00:09:24,390 --> 00:09:26,581 Okay. So, and, so when you apply a move, of 171 00:09:26,581 --> 00:09:29,668 course, you have to update the tabu status, okay, the tabu data structure of 172 00:09:29,668 --> 00:09:33,827 that particular move, okay? So and essentially if you are basically 173 00:09:33,827 --> 00:09:36,473 swapping i and j, tabu i and j is going to be the value of the iteration 174 00:09:36,473 --> 00:09:39,974 constant. You know counter plus L which is the size 175 00:09:39,974 --> 00:09:42,851 of the tabu list. Once again if the tabu list is dymanic 176 00:09:42,851 --> 00:09:46,480 you know L is changes over time but this doesn't matter right? 177 00:09:46,480 --> 00:09:50,448 So you are basically, basically saying [UNKNOWN] this is it plus L is the next 178 00:09:50,448 --> 00:09:54,782 time at which you can actually swap these 2 guys again. 179 00:09:54,782 --> 00:09:56,150 Okay. So that's the basic idea. 180 00:09:56,150 --> 00:09:59,209 So very simple in the a sense. So you keep track of when you can perform 181 00:09:59,209 --> 00:10:02,153 a move. And it's going to tabu, you still cannot 182 00:10:02,153 --> 00:10:05,174 perform the move. And when you actually perform the move, 183 00:10:05,174 --> 00:10:08,460 you make sure that you remember when is the next time which you can actually 184 00:10:08,460 --> 00:10:11,660 apply the move again. Okay? 185 00:10:11,660 --> 00:10:15,240 So this is essentially the algorithm. It's basically instrumenting, you know, 186 00:10:15,240 --> 00:10:18,672 the, the, the, the greedy local search that I've shown you within this sub-data 187 00:10:18,672 --> 00:10:22,327 structure, okay. And, so, so focus on the highlighted part 188 00:10:22,327 --> 00:10:25,488 there. And it's actually pretty reasonably 189 00:10:25,488 --> 00:10:28,073 simple right. So what you do is you compute the neighor 190 00:10:28,073 --> 00:10:30,617 root. You know as usual, and then what you have 191 00:10:30,617 --> 00:10:34,806 to do here is you have selection which is basically is basically trying to find out 192 00:10:34,806 --> 00:10:40,530 which of these neighor roots are legal. Which of them are not tabu. 193 00:10:40,530 --> 00:10:43,656 And they way you do this is you take these pairs and then you test. 194 00:10:43,656 --> 00:10:46,974 If the iteration counter is actually greater than the tabu values that is 195 00:10:46,974 --> 00:10:51,456 [UNKNOWN] for that particular move, okay? And then the next thing that you have to 196 00:10:51,456 --> 00:10:54,576 do is that when you actually perform a particular move you've to make sure that 197 00:10:54,576 --> 00:10:57,456 these counters are, these tabu data structure is updated with the right 198 00:10:57,456 --> 00:11:01,249 counter. And in this particular way, we are 199 00:11:01,249 --> 00:11:04,820 swapping i and j, right? So swapping i and j or swapping j and i 200 00:11:04,820 --> 00:11:08,788 is the same thing so we changed basically the, the, the, the, the tabu value of 201 00:11:08,788 --> 00:11:14,010 both of these move because they do the same thing, okay? 202 00:11:14,010 --> 00:11:16,380 And so, essentially, what, this is what you do. 203 00:11:16,380 --> 00:11:20,345 You always take, you know, you always take the, the, the neighborhood filters 204 00:11:20,345 --> 00:11:24,630 it that you only can keep the values which are not tabu. 205 00:11:24,630 --> 00:11:27,920 And when the, you know? When some of the moves are not tabu. 206 00:11:27,920 --> 00:11:31,704 You take the best one, you apply it. You had did this tabu data structure, 207 00:11:31,704 --> 00:11:35,106 such that this move becomes the, the, this move this particular move become 208 00:11:35,106 --> 00:11:39,080 tab, becomes tabu and then you keep iterating this. 209 00:11:39,080 --> 00:11:41,864 Of course, at every step you int, you know, you increment you know, the 210 00:11:41,864 --> 00:11:45,080 iteration counters which mean that some of the moves that are currently tabu are 211 00:11:45,080 --> 00:11:47,860 not tabu any more. Okay? 212 00:11:47,860 --> 00:11:50,950 So that's the basic idea. Very simple filtering and then updating 213 00:11:50,950 --> 00:11:53,080 the data structure. Okay? 214 00:11:53,080 --> 00:11:54,860 Now what happens if all the moves are tabu? 215 00:11:54,860 --> 00:11:57,080 What's going to happen? Are you going to get stuck forever? 216 00:11:57,080 --> 00:11:59,620 Well, you have this very nice iteration counter. 217 00:11:59,620 --> 00:12:01,540 Right? It's increasing all the time. 218 00:12:01,540 --> 00:12:04,904 So if all the moves you know are tabu what is you sit around and you wait a 219 00:12:04,904 --> 00:12:08,732 little until the counter has incremented eonugh such that some move is not tabu 220 00:12:08,732 --> 00:12:13,064 anymore. Okay, so you don't get stuck essentially 221 00:12:13,064 --> 00:12:17,680 you just have to wait, wait a little bit until the next move is not tabu. 222 00:12:17,680 --> 00:12:21,255 Okay, now in practice the schematic that I've shown has a lot of things that you 223 00:12:21,255 --> 00:12:25,470 can do a lot much better. So typically, you don't perform the 224 00:12:25,470 --> 00:12:27,739 swaps. Okay, to find the best ones, you're 225 00:12:27,739 --> 00:12:30,650 typically using chromountal data structure sets. 226 00:12:30,650 --> 00:12:32,740 You can evaluate these things very quickly. 227 00:12:32,740 --> 00:12:34,916 You never simulate the move and then [UNKNOWN] that's what the move is giving 228 00:12:34,916 --> 00:12:36,748 me. You always try to say [UNKNOWN] if I 229 00:12:36,748 --> 00:12:40,400 would perform that move that would be the value of the objective function. 230 00:12:40,400 --> 00:12:43,568 This is called differentiation in sense it allows you to explore many many more 231 00:12:43,568 --> 00:12:46,432 moves. And every one of these moves evaluations 232 00:12:46,432 --> 00:12:48,812 is much faster. And there are a lot of paper that are 233 00:12:48,812 --> 00:12:52,028 describing how you do that for various you know problems it's basically finding 234 00:12:52,028 --> 00:12:56,520 the right data structures to evaluate moves very quickly. 235 00:12:56,520 --> 00:13:00,876 and this is very important because in general you know tabu search is always 236 00:13:00,876 --> 00:13:05,622 somewhat greedy or semi greedy. You always try to find the best or some 237 00:13:05,622 --> 00:13:08,835 of the best algorithms the best neighbor to select. 238 00:13:08,835 --> 00:13:10,890 Okay? So that's a key aspect here. 239 00:13:10,890 --> 00:13:15,080 You are not evaluating all the moves in a systematic fashion. 240 00:13:15,080 --> 00:13:18,300 You are basically using differentiation and trying to evaluate them very quickly, 241 00:13:18,300 --> 00:13:21,520 not performing the actual move for actually evaluating it. 242 00:13:21,520 --> 00:13:23,316 Okay? Now what you, one of the things that you 243 00:13:23,316 --> 00:13:26,030 may say the, but, but what is this abstraction? 244 00:13:26,030 --> 00:13:30,117 Is it too strong, is it actually stronger than the, than the, than the, the suffix 245 00:13:30,117 --> 00:13:36,040 of the tabu list, or is actually weaker? And the answer is it's a bit of both. 246 00:13:36,040 --> 00:13:38,310 Right? So this is too weak because it cannot 247 00:13:38,310 --> 00:13:42,246 prevent cycling, right? So because you, you don't really keep the 248 00:13:42,246 --> 00:13:45,810 nodes, you, you also don't keep, you know, the entire list of states that you 249 00:13:45,810 --> 00:13:49,795 have visited, right? So you only consider a suffix, so, so you 250 00:13:49,795 --> 00:13:53,110 can still cycle here and go back to a state that you have seen. 251 00:13:53,110 --> 00:13:55,847 And then do a number of operation, go back to that state. 252 00:13:55,847 --> 00:13:57,960 Do a number operation go back and you cycle. 253 00:13:57,960 --> 00:14:02,990 Okay, so, so there is no way you really, your, it's a too weak in that sense. 254 00:14:02,990 --> 00:14:05,290 You can go back to state that you have seen before. 255 00:14:05,290 --> 00:14:08,470 When you do that, what do you do? Typical you increase you know the size of 256 00:14:08,470 --> 00:14:10,685 the tabu list. Okay, but it's too weak in this 257 00:14:10,685 --> 00:14:13,265 particular sense. It's also too strong because the only 258 00:14:13,265 --> 00:14:15,950 thing that you are remembering here are the moves. 259 00:14:15,950 --> 00:14:18,130 They are not really representing the states. 260 00:14:18,130 --> 00:14:20,000 Okay? So it may very well be that this move at 261 00:14:20,000 --> 00:14:23,250 this particular state, if you would apply them, would give you a state that you 262 00:14:23,250 --> 00:14:27,030 haven't seen before. The only thing that you remember is one 263 00:14:27,030 --> 00:14:29,240 of the moves that I have done. Okay? 264 00:14:29,240 --> 00:14:32,120 But you, you have applied your sequence of move, but when you are in this state 265 00:14:32,120 --> 00:14:35,590 applying maybe some of the first move, maybe completely fine. 266 00:14:35,590 --> 00:14:37,230 And give you another state. Okay? 267 00:14:37,230 --> 00:14:40,200 So that may happen. And so, what you have here is the fact 268 00:14:40,200 --> 00:14:42,930 that, in a sense, the tabu list here is too strong. 269 00:14:42,930 --> 00:14:46,310 It's actually preventing you from going to states that are actually nice, and 270 00:14:46,310 --> 00:14:49,520 where haven't, that you haven't visited before. 271 00:14:49,520 --> 00:14:52,710 And who can actually be pretty, and which can actually be pretty good. 272 00:14:52,710 --> 00:14:56,230 So, in that sense it's too strong it prevents you it's stronger than you know, 273 00:14:56,230 --> 00:14:59,805 keeping the entire list and keeping this you know, so that you don't go back to a 274 00:14:59,805 --> 00:15:05,129 state that you seen before okay. It's it can prevent you from going to 275 00:15:05,129 --> 00:15:09,456 states that have not been visited yet. Okay so what you can do to [INAUDIBLE] 276 00:15:09,456 --> 00:15:12,835 that is a essentially strengthening the abstraction. 277 00:15:12,835 --> 00:15:16,174 So instead of just storing the move you can say [UNKNOWN] but I'm going to store 278 00:15:16,174 --> 00:15:21,114 more features of these particular states. I can try to refine the way I'm basically 279 00:15:21,114 --> 00:15:24,749 capturing this state. So, one of the things that you can do 280 00:15:24,749 --> 00:15:28,580 easily, okay, is for instance, capture the objective values, okay? 281 00:15:28,580 --> 00:15:31,471 So you can say, okay, think about the, the, you know, the car sequencing 282 00:15:31,471 --> 00:15:34,942 algorithm again. You had slot ai and aj that you wanted to 283 00:15:34,942 --> 00:15:38,550 slot, to swap and bj, bi that you wanted to swap. 284 00:15:38,550 --> 00:15:42,393 What you can do is keep inside the tabu list, this kind of four face, right, so 285 00:15:42,393 --> 00:15:46,981 you can, you can store ai. You can store bi but you can also store 286 00:15:46,981 --> 00:15:51,260 the value of the objective function where you are now, okay? 287 00:15:51,260 --> 00:15:54,130 So this is fi, this particular function there. 288 00:15:54,130 --> 00:15:57,547 And you can also store the value that you divided the objective function that you 289 00:15:57,547 --> 00:16:01,970 would get if you performed the move. And this is denoted fi plus 1 there, 290 00:16:01,970 --> 00:16:04,360 okay, inside the tabu list. Okay. 291 00:16:04,360 --> 00:16:09,028 So this is fi plus 1 here. So, in a sense what you are saying is, if 292 00:16:09,028 --> 00:16:14,509 I'm in the state with evaluation function is fi and I want to swap ai and aj, and 293 00:16:14,509 --> 00:16:17,430 bi. Okay? 294 00:16:17,430 --> 00:16:21,021 And that would resort in a state that is the value of the objective function, 295 00:16:21,021 --> 00:16:24,620 which is fi plus 1. That move is doubled. 296 00:16:24,620 --> 00:16:26,390 Okay? Now, if that gives me a, an objective 297 00:16:26,390 --> 00:16:28,868 function which is different from fi plus 1. 298 00:16:28,868 --> 00:16:31,451 It's not tabu, because I know that this is not the state, this is not the value 299 00:16:31,451 --> 00:16:34,938 that I have performed before. So you can do something like that, so now 300 00:16:34,938 --> 00:16:38,310 the definition of the tabu search is, I'm in a particular state. 301 00:16:38,310 --> 00:16:41,116 This is the value of my objective function, I would perform this move and I 302 00:16:41,116 --> 00:16:44,211 would get to this value of the objective function. 303 00:16:44,211 --> 00:16:45,558 Okay? So these are the kind of things that you 304 00:16:45,558 --> 00:16:47,050 can start doing. Okay? 305 00:16:47,050 --> 00:16:50,735 So strengthening the abstraction. Okay? 306 00:16:50,735 --> 00:16:54,334 Now so, so the other things that you know, we can do is using this linear 307 00:16:54,334 --> 00:16:56,380 neighborhood. Okay? 308 00:16:56,380 --> 00:16:59,790 So this multistage heuristic that I've shown, that I've talked to you. 309 00:16:59,790 --> 00:17:02,456 You know, two lectures ago and the key idea is that they would do exactly the 310 00:17:02,456 --> 00:17:06,201 same thing in this particular case. You would take this particular car that 311 00:17:06,201 --> 00:17:09,209 you want to swap, okay and then you would take all the other, you know, and it has 312 00:17:09,209 --> 00:17:13,258 to have some violation. Then you would take all the other slots 313 00:17:13,258 --> 00:17:16,240 that you can swap that ca, that car with, okay? 314 00:17:16,240 --> 00:17:19,264 And essentially the tabu list would be exactly the same, you would consider 315 00:17:19,264 --> 00:17:21,200 pairs i and j. Okay? 316 00:17:21,200 --> 00:17:25,010 And you would be making sure to select only the ones that are not tabu. 317 00:17:25,010 --> 00:17:26,956 Okay? In this particular case, one of the 318 00:17:26,956 --> 00:17:29,904 things that you can do is that the move are not symmetrical anymore necessarily, 319 00:17:29,904 --> 00:17:34,190 so you update only one of them, okay? And so basically, putting your tabu 320 00:17:34,190 --> 00:17:37,510 search on top of that multi-set heuristic is very easy. 321 00:17:37,510 --> 00:17:40,900 It's essentially the same as in the quadratic neighborhood, okay? 322 00:17:40,900 --> 00:17:42,890 So let me talk a little bit about the Queens Problem. 323 00:17:42,890 --> 00:17:45,798 So you remember the Queens Problem. It's, what we did there was selecting a 324 00:17:45,798 --> 00:17:51,580 queen and then moving to a position where you reduce the valuation the most. 325 00:17:51,580 --> 00:17:53,154 Okay? So in this particular case, the 326 00:17:53,154 --> 00:17:55,996 particular neighbor root is taking a value, no, taking a variable and 327 00:17:55,996 --> 00:18:00,410 assigning a new value, taking a queen and moving it to a new position. 328 00:18:00,410 --> 00:18:02,662 Okay? So, what has to be the tabu search, and 329 00:18:02,662 --> 00:18:06,000 the tabu data structure in this particular case? 330 00:18:06,000 --> 00:18:08,700 Well, essentially the move is moving you know a particular queen to a new 331 00:18:08,700 --> 00:18:11,597 position, okay. So what, what, you know, if you go to 332 00:18:11,597 --> 00:18:16,150 that state, what is the thing that you want to avoid in the next iteration? 333 00:18:16,150 --> 00:18:19,990 Well, you want to avoid taking that, that queen and putting it back to initial 334 00:18:19,990 --> 00:18:23,692 position, right? So what essentially you are trying to do 335 00:18:23,692 --> 00:18:28,320 here is preventing the value of the queen to take its old value, right. 336 00:18:28,320 --> 00:18:31,659 And so, once again, what you're going to store here, are pairs, x, v, where x is a 337 00:18:31,659 --> 00:18:35,310 variable and v is a value for that variable, okay? 338 00:18:35,310 --> 00:18:37,940 So we store pairs, but they have, they have a different meaning here. 339 00:18:37,940 --> 00:18:41,372 It's basically, [UNKNOWN] I don't want this variable x to be assigned the value 340 00:18:41,372 --> 00:18:44,736 v for a while, okay? And that's what you store inside a tabu 341 00:18:44,736 --> 00:18:45,680 list. Okay? 342 00:18:45,680 --> 00:18:50,370 So this is essentially the search, once again, for, the queen's example. 343 00:18:50,370 --> 00:18:53,062 Okay? And what we do, is, basically, this is, 344 00:18:53,062 --> 00:18:55,870 this is, this is a mean conflict heuristic. 345 00:18:55,870 --> 00:18:59,400 You basically select a queen which appear in sum violation. 346 00:18:59,400 --> 00:19:03,630 Then you generate all the possible position for that particular queen. 347 00:19:03,630 --> 00:19:05,650 And you only the select the ones that are not tabu. 348 00:19:05,650 --> 00:19:08,761 Which basically means that you even had the, that value for the queen for a 349 00:19:08,761 --> 00:19:11,060 while. Okay? 350 00:19:11,060 --> 00:19:13,050 And, so. Then, afterwards, you know that, you 351 00:19:13,050 --> 00:19:16,100 select the best move. And then you apply this operation here. 352 00:19:16,100 --> 00:19:17,600 That's what you see there. Okay? 353 00:19:17,600 --> 00:19:20,435 Which basically means [UNKNOWN] I don't want in the future to return to that 354 00:19:20,435 --> 00:19:22,520 value for that queen. Okay? 355 00:19:22,520 --> 00:19:26,769 So use tabu i indexed to. So, you use the tabu data structure 356 00:19:26,769 --> 00:19:29,180 indexed by i. That is the queen you have selected. 357 00:19:29,180 --> 00:19:32,635 And then the value of the queen, at this point, which is queen c. 358 00:19:32,635 --> 00:19:36,405 Okay so and basically what you do is you basically say oh I don't want to give the 359 00:19:36,405 --> 00:19:40,175 value to, to do, for the queen to get the value that it currently has for a number 360 00:19:40,175 --> 00:19:44,816 of iterations. Okay and the rest of the procedure is 361 00:19:44,816 --> 00:19:48,470 basically the same, okay. So what you keep here is okay, I don't 362 00:19:48,470 --> 00:19:52,220 want to debt queen to get back to its original value. 363 00:19:52,220 --> 00:19:55,553 Okay? So once again, you know, we have a lot of 364 00:19:55,553 --> 00:20:00,514 choices in this tabu search algorithm. What I've shown you here is essentially 365 00:20:00,514 --> 00:20:03,538 oh, you know, I take a move, and I, and the abstraction is actually capturing 366 00:20:03,538 --> 00:20:06,760 that move. And making sure that we cannot do the 367 00:20:06,760 --> 00:20:09,200 reverse move, in a sense, here. Okay? 368 00:20:09,200 --> 00:20:11,990 So we take the move, I want to make sure that I don't take the reverse move, for 369 00:20:11,990 --> 00:20:14,850 actually getting back to the previous state. 370 00:20:14,850 --> 00:20:16,398 Okay? So in the swap, it was easy to move, 371 00:20:16,398 --> 00:20:20,332 where itself, the reverse move. Here, I'm basing the capturing the fact 372 00:20:20,332 --> 00:20:25,020 that, you know, I'm prevent, I'm putting in the tabu search, the reverse move. 373 00:20:25,020 --> 00:20:26,907 Okay? Now in practice, you may actually use 374 00:20:26,907 --> 00:20:29,450 abstraction, which are even more coarse, okay. 375 00:20:29,450 --> 00:20:32,714 It's really coarser abstraction. So one of the things that I may say, ooh, 376 00:20:32,714 --> 00:20:35,580 that variable, you know? I'm just changing it. 377 00:20:35,580 --> 00:20:38,700 I don't want to change it again for a bunch of iteration, okay? 378 00:20:38,700 --> 00:20:42,070 So instead of keeping the value that I, the, the reverse move. 379 00:20:42,070 --> 00:20:45,640 You are basically forbidding all the move that are involved with that variable. 380 00:20:45,640 --> 00:20:48,016 So this is something you could do. There is nothing that prevents you from 381 00:20:48,016 --> 00:20:50,556 doing that. Here, you are basically having a much, 382 00:20:50,556 --> 00:20:53,830 much, much more coarse approximation of the tabu list. 383 00:20:53,830 --> 00:20:59,100 But it's maybe very effective in diverse, you know, diversifying the search, okay? 384 00:20:59,100 --> 00:21:02,620 So essentially, if you put a variable which is tabu for a number of iteration, 385 00:21:02,620 --> 00:21:07,400 you can actually touch that particle variable for a while, okay? 386 00:21:07,400 --> 00:21:10,910 Now, so this is, once again, the basic of, of, of essentially keeping this tabu 387 00:21:10,910 --> 00:21:14,707 search, tabu list. But one of the things I have told you 388 00:21:14,707 --> 00:21:17,522 sometimes too weak or sometimes too strong. 389 00:21:17,522 --> 00:21:20,967 So when they asked too strong, you have the behavior that can happen is that you 390 00:21:20,967 --> 00:21:24,637 are in this state. And then you want to perform his move and 391 00:21:24,637 --> 00:21:28,093 then this move is so good that it will give the best solution ever that you have 392 00:21:28,093 --> 00:21:31,387 seen so far right and so you say the move, unfortunately stubble so you are 393 00:21:31,387 --> 00:21:37,650 like that that move is stubble with there I really want to go there. 394 00:21:37,650 --> 00:21:39,640 Okay. And of course we want to allow it. 395 00:21:39,640 --> 00:21:43,072 And so in tabu search you have this kind of you know technique which is called the 396 00:21:43,072 --> 00:21:46,620 aspiration criterion. And what you can do is that if the move 397 00:21:46,620 --> 00:21:49,820 is tabu but it's so good that you really want to take it, you basically over ride 398 00:21:49,820 --> 00:21:53,130 the tabu search, the tabu status. Okay. 399 00:21:53,130 --> 00:21:57,770 So essentially what you are, so you can implement some aspiration criterion. 400 00:21:57,770 --> 00:22:00,920 That are basically telling, yes, it's tabu but if it, if it's that good, just 401 00:22:00,920 --> 00:22:03,900 take it, okay? So, and that's what you see here. 402 00:22:03,900 --> 00:22:06,442 And the reason you can do things like this is because, once again, you know, 403 00:22:06,442 --> 00:22:10,040 that, to, that, what we keep is an obstruction of the tabu list. 404 00:22:10,040 --> 00:22:12,680 We are preventing the search from going to state that are really that we haven't 405 00:22:12,680 --> 00:22:15,490 visited so far and there is nothing you can really do. 406 00:22:15,490 --> 00:22:17,580 Otherwise, you would have to start the whole thing, right? 407 00:22:17,580 --> 00:22:21,200 So in, in this particular case, this is what we implement, the NotTabu. 408 00:22:21,200 --> 00:22:24,035 It's going to take all the particular configurations that, all the neighbors 409 00:22:24,035 --> 00:22:28,150 that we are considering and you'll see that we'll want to have two conditions. 410 00:22:28,150 --> 00:22:31,930 They don't have to be tabu or if they are tabu, the move is so good that it's 411 00:22:31,930 --> 00:22:35,830 better, you know better than the best solution so far and therefore you take it 412 00:22:35,830 --> 00:22:38,860 anyway. Okay. 413 00:22:38,860 --> 00:22:41,445 So in a sense, the neighborhoods are going to be all the move which are 414 00:22:41,445 --> 00:22:45,802 NotTabu plus the one that are so good that you've, you've got to take them. 415 00:22:45,802 --> 00:22:49,401 Okay, so you get to take them. Okay, so basically that's the idea behind 416 00:22:49,401 --> 00:22:52,331 you know, aspiration the aspiration criteria. 417 00:22:52,331 --> 00:22:55,979 You take moves that are tabu but they are so good that you know you really want to 418 00:22:55,979 --> 00:22:58,915 take them. Okay so 2 more techniques that I want to 419 00:22:58,915 --> 00:23:01,336 talk about and this is more long term memory. 420 00:23:01,336 --> 00:23:04,171 Okay, so what you can happen to this in this tabu search is that you start from 421 00:23:04,171 --> 00:23:08,776 the 1 and then you get good solution. And at some point, you start in, you 422 00:23:08,776 --> 00:23:14,180 start going in this kind of long, long walk, where nothing really improves. 423 00:23:14,180 --> 00:23:16,230 You improve, you improve. You degrade, you improve. 424 00:23:16,230 --> 00:23:18,658 Nothing happens, okay? So you have these long, long walk, 425 00:23:18,658 --> 00:23:21,299 nothing happens. But at some point, you were in a really 426 00:23:21,299 --> 00:23:23,700 good state. And you thought you would find a very 427 00:23:23,700 --> 00:23:26,398 high quality solution. So what you can do is what is called 428 00:23:26,398 --> 00:23:29,149 intensification. You keep a set of states that have been 429 00:23:29,149 --> 00:23:30,880 very good. You found them before. 430 00:23:30,880 --> 00:23:33,436 They are very good. And what you do is instead of going into 431 00:23:33,436 --> 00:23:36,460 this long, random work where nothing happens, you decide to go back to these 432 00:23:36,460 --> 00:23:39,799 and restart the search from then. Okay? 433 00:23:39,799 --> 00:23:43,872 So that's what is called intensification. You keep very high quality solution and 434 00:23:43,872 --> 00:23:47,058 when you are stuck in this long, long, long walk where nothing really is 435 00:23:47,058 --> 00:23:52,080 improving you know, over the best solutions you have found so far. 436 00:23:52,080 --> 00:23:55,440 You return to one of these things and you restart the search from there. 437 00:23:55,440 --> 00:23:57,342 Okay? Very useful technique in practice as 438 00:23:57,342 --> 00:23:59,742 well. And then, diversification is just the 439 00:23:59,742 --> 00:24:01,506 opposite. Okay, so in heuristics, in 440 00:24:01,506 --> 00:24:04,482 meta-heuristic, what is nice is that if you have a good idea, generally the 441 00:24:04,482 --> 00:24:08,020 inverse of the idea is also nice. Okay? 442 00:24:08,020 --> 00:24:10,280 So instead of intensify, you want to diversify. 443 00:24:10,280 --> 00:24:12,215 Okay? So what it's basically saying is that if 444 00:24:12,215 --> 00:24:15,230 you have not seen this improvement for a long time, you are working in this random 445 00:24:15,230 --> 00:24:19,578 work, not seeing anything interesting. What you can say is that wow, I made a 446 00:24:19,578 --> 00:24:21,960 configuration where something is really wrong. 447 00:24:21,960 --> 00:24:25,180 So I'm going to take part of this solution and completely change it. 448 00:24:25,180 --> 00:24:26,830 And that's what is called diversification. 449 00:24:26,830 --> 00:24:29,774 You can take, for instance, a bunch of, you know, in the, in the consequencing 450 00:24:29,774 --> 00:24:32,534 you would take an arbitrary number of swaps, and chance completely your 451 00:24:32,534 --> 00:24:35,520 configuration. Okay? 452 00:24:35,520 --> 00:24:38,481 In, in the queens, you can start moving queens around in a completely random 453 00:24:38,481 --> 00:24:41,077 fashion, okay? Or you can, you know, use more of the 454 00:24:41,077 --> 00:24:43,958 structure of the problem to actually have a more, you know, structure based, you 455 00:24:43,958 --> 00:24:47,740 know, diversification. But once again, this is very useful. 456 00:24:47,740 --> 00:24:51,400 So a lot of the tabu search algorithm will have an intensification phase. 457 00:24:51,400 --> 00:24:53,560 And then they will have also a diversification phase. 458 00:24:53,560 --> 00:24:56,435 When the intensification is, you know, exhausted in a a sense. 459 00:24:56,435 --> 00:24:58,690 Okay? And then there is this very interesting 460 00:24:58,690 --> 00:25:01,210 technique as we also use for the TTP, where it's typically in problems where 461 00:25:01,210 --> 00:25:05,400 you have both very difficult constraints and very difficult objective function. 462 00:25:05,400 --> 00:25:08,520 Typically what you do is to solve the constraint are becoming in the objective 463 00:25:08,520 --> 00:25:11,638 function, okay to drive the search of feasibility. 464 00:25:11,638 --> 00:25:14,614 And then you also want to have the object, the original objective of course 465 00:25:14,614 --> 00:25:18,622 to find, you know very good solution. And strategic oscillation is kind of 466 00:25:18,622 --> 00:25:21,758 scheme where you want to balance the time that you spend in the feasible and the 467 00:25:21,758 --> 00:25:24,580 infeasible region. Okay? 468 00:25:24,580 --> 00:25:26,990 And so you basically try to adjust the power meter. 469 00:25:26,990 --> 00:25:29,409 If you spend too much time in the in feasible region, you want to give more 470 00:25:29,409 --> 00:25:32,190 importance to the constraint that I have violated. 471 00:25:32,190 --> 00:25:34,270 To increase the weight of these constraints. 472 00:25:34,270 --> 00:25:36,766 Such that you go back and you spend more time in the feasible region in the hope 473 00:25:36,766 --> 00:25:40,280 of finding feasible solution that increase the best so far. 474 00:25:40,280 --> 00:25:42,774 If you spend too much time in the feasible region, you may actually not 475 00:25:42,774 --> 00:25:46,096 escape some local minima. So you may decide to, you know, let the, 476 00:25:46,096 --> 00:25:49,160 you know, give more weight to the objective function. 477 00:25:49,160 --> 00:25:51,890 You may go to the infeasible region with the hope that at some point you get back 478 00:25:51,890 --> 00:25:55,160 to feasibility, and a better objective function, okay? 479 00:25:55,160 --> 00:25:58,232 So once again these techniques are very useful in practice on some of the tabu 480 00:25:58,232 --> 00:26:01,578 search algorithm, okay. So final remark in this particular 481 00:26:01,578 --> 00:26:05,114 techniques like diversification, intensification and strategic oscillation 482 00:26:05,114 --> 00:26:08,552 are actually very useful in many different settings. 483 00:26:08,552 --> 00:26:11,932 They are very useful for simulating, they're needing for many other, for many 484 00:26:11,932 --> 00:26:15,766 other you know meta heuristic. So use them in those settings as well 485 00:26:15,766 --> 00:26:19,225 because they, they can make a big difference in practice. 486 00:26:19,225 --> 00:26:22,215 Okay? So this is basically finishing the local 487 00:26:22,215 --> 00:26:26,084 search part of the class. what we're going to do in the next couple 488 00:26:26,084 --> 00:26:28,749 of lectures is studying looking at mathematical programming, starting with 489 00:26:28,749 --> 00:26:31,430 linear programming, and integer programming. 490 00:26:31,430 --> 00:26:35,092 So, very, very different paradigm, but very exciting, too. 491 00:26:35,092 --> 00:26:37,240 Thank you.