Okay discrete optimization, but I can tabu search. so I want to spend a little bit of time on tabu search because this is very interesting and I want to, I want to tell you a little bit of a story before. So, so, John Hooker once told me that, for every invention, there are very, there are three stages. Okay, so the first stage is that people are going to look at the invention, and say oh, this can't work, okay, this is all wrong, okay? And so that's the first stage and then you go to the second stage where people realize that this is actually working, but then would say, oh, but this is trivial, okay? So, that's the second phase of an invention, people will say it's trivial. And of course that lasts for a while and then the third stage is the most interesting one. People will say, oh, that invention, I invented it. Okay, i'ts a footnote in my thesis, okay? So tabu searches like that. Okay, so amazing thing, you know it was invented by you know Fred Glover. And the first time you look at this, you say, well this can't work right? So and then could and you see on your favorite problem these reserves that are coming up and are amazing most of the time right? So you say, wow this actually very, you know this is actually working. But it's so simple it's not even interesting right? And then afterwards, you spend your life working on tabu search. Right? So, this is, this is what tabu search can do to you. Okay? So, so I want to spend some time in telling you some of the richness of this particular meta heuristic. And, and, and all the issues that you have in trying to design the right compromise between different aspect of, of tabu search algorithm. So remember what we wanted to do is that we start from a point, we go back down to a local minimum. And then sometimes we go back up, and then, and we want, we have the ability to go back up and then to go down. If we don't have anything, typically you, you can't escape this local minimum, you would stay here all the time. Okay. So the idea of tabu search is that you know, one, once you have been to, to a particular state you consider it tabu. Okay? So you have seen it, you don't want to go back there. Okay? And then you can start going up to a particular node like you know, this one. And obviously when you are there you, you know, if you have something like a you know, greedy approach. This guy may be in the neighborhood and then you will want to go there. Okay? But since it's tabu you can't go there, so you will have to find the next best. If you have let's say a greedy approach. Okay? And this one may be the next best, and so, so you move up there. And once again, when you are up there, this guy will say, ooh, I want to be greedy. And he's going to look at this one, and of course the first one, and say, ooh, that's where I want to go. But once again, you can't do that because you are tabu and so you go up. And now you are the top of this, top of this landscape, and you can actually start going down. To to the ultimate solution, okay. So in a sense, the key abstract idea of tabu search is that you keyboard knows that you visited, okay, and you never go back there. Okay, so you have been there, seen them, no way you want to return to them, okay. So this is the pres, you know, the tabu search algorithm that I've shown you. The key aspect here is that you always skip this tabu list of all, essentially, the nodes that you have visited so far. This tool is that you increase every time you move to another, another, another state, okay? Now, one of the basic issues with the tabu-search algorithm is that, you know, if, if, you, you want to select the best configuration that is not tabu. Okay? So that's what we have seen. But one of the basic issues is that it's very expensive to maintain all these states that you been there. Right? So assume that you have, you know, thousands of variables. You would have to keep them, and you may visit, you know. So, as I've shown you last time you know, 100's of 1000's of configuration. So you start using a lot of space and every time you have to try to, every time you select a neighbor, you have to say, oh, is it legal or not. So you have to compare it with all the stuff that you have varied. That you have seen. So it's very, you know, expensive from, let's say, a time and a space, you know, standpoint. So what you can do is to use what is called a Short-Term Memory. Instead of actually looking, keeping all these notes, you are going to only look at certain, you can only keep a subset of them. And essentially, the recent ones. You are looking at a subset of these two lists, okay? And so you, you look at the suffix of that list, which already knows that you have visited recently. And what you're basically saying, I don't want to go to the stuff that I've been recently, okay? So, because you have, you know, you, you can expect that, you know, the nodes that you haven't seen for a while, they are very far away. They are not inside your neighborhood, so you don't care about that. Okay? So if you keep, you know, if you keep a fixed length list, tabu list, okay, so you basically, you know, keep the last 20, who knows if you have something like this, okay. Of course, in practice, you can dynamically increase or decrease this list to get a good compromise in not being stuck in a local minimum but not preventing, you know, not, not preventing, you know, you to actually diversify this this, the search too much. So you can decrease, for instance, the size of the list if the, the objective functions is, is degrading, or, you know, increasing it when the, when you actually improving the objective all the time. So you can use things like this, okay? So, so, the, the question that you have is that at that point you are still storing entire consideration. Okay? And that means still be too costly. Sometimes it's not. You can actually implement things like this. But sometimes you, you are going to say, wow, this is really costly. I have to store this entire state, I have to do all this comparison that's, you know, taking a lot of time. And my sense is that I want to, you know, valid, many, many configurations very, very quickly. So, so, what you can do is, is instead of, you know, storing these states, you are going to store an abstraction of this suffix, okay. And the way show this abstraction can be arbitrarily complicated or arbitrarily simple. But you have to find a way of very concisely abstracting these sets of nodes that you have visited recently. Okay? Now, many possibilities, and I'm going to show you some of them. Okay? So, this is the car sequencing applications that I've shown you before. Okay, once again, you have this assembly line. You can swap, you know, different different slots of the assembly line. And this is a, this is a greedy local improvement algorithm, and what you do is you select essentially a particular slot, which is, which has violation. You are violating some capacity constraint. You select another slot, that's a quadratic neighborhood, okay. And then you are basically saying, oh, I want to take the best of these moves, okay. And so you apply the move and it's improved the, the value of the object if you take it. Otherwise, you, you know, you, you're in a local minimum, so you break the search. Okay. So this is a greedy algorithm, okay. And so, what I want to do here is implement a tabu search algorithm. But I wan, I don't want to keep this configuration as I told you. We can you know, we can explore hundreds of thousands of them and then maybe you know, 300 you know, slots you know, they, they maybe come 300 slots or more. So this is a lot of space and a lot of time that you would spend just comparing these things. So what we're going to do is that instead of storing these states, we are going to store the transition not the state them self. And the transition in this particular case is what. I'm just swap 2 cars, okay. So you're basically saying okay so a move is swapping these 2 cars, okay ai and aj in the assembly line. And so what I'm going to store inside the tabu-list is these pairs, ai, aj okay. right actually I, I wrote ai, bi okay, so our basically you are remembering that you swap these 2, you know you swap these 2 slots on the assembly line. And the key idea is that you know in the future you don't want to re swap this two because you are going back to place where you have been, okay. So instead of keeping the state you are basically keeping the operation that have been moving you from state to state and in this particular case is basically the swaps, okay. And so configuration is going to be tabu in this particular abstraction if it can be obtained by swapping two things which are inside, inside the, the tabu list. So, so what you're going to do is that you're only going to look at the swaps essentially which are not inside the tabu list. Okay? So you can swap things that you have been swapping recently. That's basically the abstraction here. Okay? So in a sense, you are not storing the states, you are not really, you are not really actually abstracting them in a complete you know, exact fashion. But you are basically remembering some operations that you have done so far. And you don't want to apply these operations again. That's the kind of things that you do here. Okay, so how do we implement this. So, this is the basic idea. So what you do is you keep a counter IT. Which basically denotes the iterations that you are in inside the the algorithm. Okay, so every time you perform a move that counter is going to be incremented. So this is the IT you know counter. Then what you use is a data structure, tabu ij, okay where i and j are the 2. Two slots that you can, can, can swap and that data structure is going to represent the first iteration when it's going to be legal to actually swap i and j again. So, so think about, think about it this way. Okay? So i and j, you have just performed the swap between i and j. Okay? And you want to make sure that you're not going to sub these two guys for a bunch of iterations. So inside tabu ij, you remember, you, okay, you store the next, next iteration, where it will be legal to actually swap these two slots, okay. So, and, and, so, in, in the next two, two conditions here, I'm going to used a fixed tabu size of L. But you could, you know, you could have a dynamic on each side, so the same principle applies. Okay, so, so essentially, when is a move tabu? Okay, so a move is going to be tabu. Is the value tabu i,j so, i,j is going to be tabu if tabu i,j is actually greater the iteration number. Okay. So that means that [UNKNOWN] is only later than I will be allowed to actually swab these 2 guys. If the counter is smaller, that mean you okay can swap it. You know, it's allowed at this point. It's legal at this point to swap these 2 guys. So it's very easy here in constant time if you can find if a move is tabu. Okay. So, and, so when you apply a move, of course, you have to update the tabu status, okay, the tabu data structure of that particular move, okay? So and essentially if you are basically swapping i and j, tabu i and j is going to be the value of the iteration constant. You know counter plus L which is the size of the tabu list. Once again if the tabu list is dymanic you know L is changes over time but this doesn't matter right? So you are basically, basically saying [UNKNOWN] this is it plus L is the next time at which you can actually swap these 2 guys again. Okay. So that's the basic idea. So very simple in the a sense. So you keep track of when you can perform a move. And it's going to tabu, you still cannot perform the move. And when you actually perform the move, you make sure that you remember when is the next time which you can actually apply the move again. Okay? So this is essentially the algorithm. It's basically instrumenting, you know, the, the, the, the greedy local search that I've shown you within this sub-data structure, okay. And, so, so focus on the highlighted part there. And it's actually pretty reasonably simple right. So what you do is you compute the neighor root. You know as usual, and then what you have to do here is you have selection which is basically is basically trying to find out which of these neighor roots are legal. Which of them are not tabu. And they way you do this is you take these pairs and then you test. If the iteration counter is actually greater than the tabu values that is [UNKNOWN] for that particular move, okay? And then the next thing that you have to do is that when you actually perform a particular move you've to make sure that these counters are, these tabu data structure is updated with the right counter. And in this particular way, we are swapping i and j, right? So swapping i and j or swapping j and i is the same thing so we changed basically the, the, the, the, the tabu value of both of these move because they do the same thing, okay? And so, essentially, what, this is what you do. You always take, you know, you always take the, the, the neighborhood filters it that you only can keep the values which are not tabu. And when the, you know? When some of the moves are not tabu. You take the best one, you apply it. You had did this tabu data structure, such that this move becomes the, the, this move this particular move become tab, becomes tabu and then you keep iterating this. Of course, at every step you int, you know, you increment you know, the iteration counters which mean that some of the moves that are currently tabu are not tabu any more. Okay? So that's the basic idea. Very simple filtering and then updating the data structure. Okay? Now what happens if all the moves are tabu? What's going to happen? Are you going to get stuck forever? Well, you have this very nice iteration counter. Right? It's increasing all the time. So if all the moves you know are tabu what is you sit around and you wait a little until the counter has incremented eonugh such that some move is not tabu anymore. Okay, so you don't get stuck essentially you just have to wait, wait a little bit until the next move is not tabu. Okay, now in practice the schematic that I've shown has a lot of things that you can do a lot much better. So typically, you don't perform the swaps. Okay, to find the best ones, you're typically using chromountal data structure sets. You can evaluate these things very quickly. You never simulate the move and then [UNKNOWN] that's what the move is giving me. You always try to say [UNKNOWN] if I would perform that move that would be the value of the objective function. This is called differentiation in sense it allows you to explore many many more moves. And every one of these moves evaluations is much faster. And there are a lot of paper that are describing how you do that for various you know problems it's basically finding the right data structures to evaluate moves very quickly. and this is very important because in general you know tabu search is always somewhat greedy or semi greedy. You always try to find the best or some of the best algorithms the best neighbor to select. Okay? So that's a key aspect here. You are not evaluating all the moves in a systematic fashion. You are basically using differentiation and trying to evaluate them very quickly, not performing the actual move for actually evaluating it. Okay? Now what you, one of the things that you may say the, but, but what is this abstraction? Is it too strong, is it actually stronger than the, than the, than the, the suffix of the tabu list, or is actually weaker? And the answer is it's a bit of both. Right? So this is too weak because it cannot prevent cycling, right? So because you, you don't really keep the nodes, you, you also don't keep, you know, the entire list of states that you have visited, right? So you only consider a suffix, so, so you can still cycle here and go back to a state that you have seen. And then do a number of operation, go back to that state. Do a number operation go back and you cycle. Okay, so, so there is no way you really, your, it's a too weak in that sense. You can go back to state that you have seen before. When you do that, what do you do? Typical you increase you know the size of the tabu list. Okay, but it's too weak in this particular sense. It's also too strong because the only thing that you are remembering here are the moves. They are not really representing the states. Okay? So it may very well be that this move at this particular state, if you would apply them, would give you a state that you haven't seen before. The only thing that you remember is one of the moves that I have done. Okay? But you, you have applied your sequence of move, but when you are in this state applying maybe some of the first move, maybe completely fine. And give you another state. Okay? So that may happen. And so, what you have here is the fact that, in a sense, the tabu list here is too strong. It's actually preventing you from going to states that are actually nice, and where haven't, that you haven't visited before. And who can actually be pretty, and which can actually be pretty good. So, in that sense it's too strong it prevents you it's stronger than you know, keeping the entire list and keeping this you know, so that you don't go back to a state that you seen before okay. It's it can prevent you from going to states that have not been visited yet. Okay so what you can do to [INAUDIBLE] that is a essentially strengthening the abstraction. So instead of just storing the move you can say [UNKNOWN] but I'm going to store more features of these particular states. I can try to refine the way I'm basically capturing this state. So, one of the things that you can do easily, okay, is for instance, capture the objective values, okay? So you can say, okay, think about the, the, you know, the car sequencing algorithm again. You had slot ai and aj that you wanted to slot, to swap and bj, bi that you wanted to swap. What you can do is keep inside the tabu list, this kind of four face, right, so you can, you can store ai. You can store bi but you can also store the value of the objective function where you are now, okay? So this is fi, this particular function there. And you can also store the value that you divided the objective function that you would get if you performed the move. And this is denoted fi plus 1 there, okay, inside the tabu list. Okay. So this is fi plus 1 here. So, in a sense what you are saying is, if I'm in the state with evaluation function is fi and I want to swap ai and aj, and bi. Okay? And that would resort in a state that is the value of the objective function, which is fi plus 1. That move is doubled. Okay? Now, if that gives me a, an objective function which is different from fi plus 1. It's not tabu, because I know that this is not the state, this is not the value that I have performed before. So you can do something like that, so now the definition of the tabu search is, I'm in a particular state. This is the value of my objective function, I would perform this move and I would get to this value of the objective function. Okay? So these are the kind of things that you can start doing. Okay? So strengthening the abstraction. Okay? Now so, so the other things that you know, we can do is using this linear neighborhood. Okay? So this multistage heuristic that I've shown, that I've talked to you. You know, two lectures ago and the key idea is that they would do exactly the same thing in this particular case. You would take this particular car that you want to swap, okay and then you would take all the other, you know, and it has to have some violation. Then you would take all the other slots that you can swap that ca, that car with, okay? And essentially the tabu list would be exactly the same, you would consider pairs i and j. Okay? And you would be making sure to select only the ones that are not tabu. Okay? In this particular case, one of the things that you can do is that the move are not symmetrical anymore necessarily, so you update only one of them, okay? And so basically, putting your tabu search on top of that multi-set heuristic is very easy. It's essentially the same as in the quadratic neighborhood, okay? So let me talk a little bit about the Queens Problem. So you remember the Queens Problem. It's, what we did there was selecting a queen and then moving to a position where you reduce the valuation the most. Okay? So in this particular case, the particular neighbor root is taking a value, no, taking a variable and assigning a new value, taking a queen and moving it to a new position. Okay? So, what has to be the tabu search, and the tabu data structure in this particular case? Well, essentially the move is moving you know a particular queen to a new position, okay. So what, what, you know, if you go to that state, what is the thing that you want to avoid in the next iteration? Well, you want to avoid taking that, that queen and putting it back to initial position, right? So what essentially you are trying to do here is preventing the value of the queen to take its old value, right. And so, once again, what you're going to store here, are pairs, x, v, where x is a variable and v is a value for that variable, okay? So we store pairs, but they have, they have a different meaning here. It's basically, [UNKNOWN] I don't want this variable x to be assigned the value v for a while, okay? And that's what you store inside a tabu list. Okay? So this is essentially the search, once again, for, the queen's example. Okay? And what we do, is, basically, this is, this is, this is a mean conflict heuristic. You basically select a queen which appear in sum violation. Then you generate all the possible position for that particular queen. And you only the select the ones that are not tabu. Which basically means that you even had the, that value for the queen for a while. Okay? And, so. Then, afterwards, you know that, you select the best move. And then you apply this operation here. That's what you see there. Okay? Which basically means [UNKNOWN] I don't want in the future to return to that value for that queen. Okay? So use tabu i indexed to. So, you use the tabu data structure indexed by i. That is the queen you have selected. And then the value of the queen, at this point, which is queen c. Okay so and basically what you do is you basically say oh I don't want to give the value to, to do, for the queen to get the value that it currently has for a number of iterations. Okay and the rest of the procedure is basically the same, okay. So what you keep here is okay, I don't want to debt queen to get back to its original value. Okay? So once again, you know, we have a lot of choices in this tabu search algorithm. What I've shown you here is essentially oh, you know, I take a move, and I, and the abstraction is actually capturing that move. And making sure that we cannot do the reverse move, in a sense, here. Okay? So we take the move, I want to make sure that I don't take the reverse move, for actually getting back to the previous state. Okay? So in the swap, it was easy to move, where itself, the reverse move. Here, I'm basing the capturing the fact that, you know, I'm prevent, I'm putting in the tabu search, the reverse move. Okay? Now in practice, you may actually use abstraction, which are even more coarse, okay. It's really coarser abstraction. So one of the things that I may say, ooh, that variable, you know? I'm just changing it. I don't want to change it again for a bunch of iteration, okay? So instead of keeping the value that I, the, the reverse move. You are basically forbidding all the move that are involved with that variable. So this is something you could do. There is nothing that prevents you from doing that. Here, you are basically having a much, much, much more coarse approximation of the tabu list. But it's maybe very effective in diverse, you know, diversifying the search, okay? So essentially, if you put a variable which is tabu for a number of iteration, you can actually touch that particle variable for a while, okay? Now, so this is, once again, the basic of, of, of essentially keeping this tabu search, tabu list. But one of the things I have told you sometimes too weak or sometimes too strong. So when they asked too strong, you have the behavior that can happen is that you are in this state. And then you want to perform his move and then this move is so good that it will give the best solution ever that you have seen so far right and so you say the move, unfortunately stubble so you are like that that move is stubble with there I really want to go there. Okay. And of course we want to allow it. And so in tabu search you have this kind of you know technique which is called the aspiration criterion. And what you can do is that if the move is tabu but it's so good that you really want to take it, you basically over ride the tabu search, the tabu status. Okay. So essentially what you are, so you can implement some aspiration criterion. That are basically telling, yes, it's tabu but if it, if it's that good, just take it, okay? So, and that's what you see here. And the reason you can do things like this is because, once again, you know, that, to, that, what we keep is an obstruction of the tabu list. We are preventing the search from going to state that are really that we haven't visited so far and there is nothing you can really do. Otherwise, you would have to start the whole thing, right? So in, in this particular case, this is what we implement, the NotTabu. It's going to take all the particular configurations that, all the neighbors that we are considering and you'll see that we'll want to have two conditions. They don't have to be tabu or if they are tabu, the move is so good that it's better, you know better than the best solution so far and therefore you take it anyway. Okay. So in a sense, the neighborhoods are going to be all the move which are NotTabu plus the one that are so good that you've, you've got to take them. Okay, so you get to take them. Okay, so basically that's the idea behind you know, aspiration the aspiration criteria. You take moves that are tabu but they are so good that you know you really want to take them. Okay so 2 more techniques that I want to talk about and this is more long term memory. Okay, so what you can happen to this in this tabu search is that you start from the 1 and then you get good solution. And at some point, you start in, you start going in this kind of long, long walk, where nothing really improves. You improve, you improve. You degrade, you improve. Nothing happens, okay? So you have these long, long walk, nothing happens. But at some point, you were in a really good state. And you thought you would find a very high quality solution. So what you can do is what is called intensification. You keep a set of states that have been very good. You found them before. They are very good. And what you do is instead of going into this long, random work where nothing happens, you decide to go back to these and restart the search from then. Okay? So that's what is called intensification. You keep very high quality solution and when you are stuck in this long, long, long walk where nothing really is improving you know, over the best solutions you have found so far. You return to one of these things and you restart the search from there. Okay? Very useful technique in practice as well. And then, diversification is just the opposite. Okay, so in heuristics, in meta-heuristic, what is nice is that if you have a good idea, generally the inverse of the idea is also nice. Okay? So instead of intensify, you want to diversify. Okay? So what it's basically saying is that if you have not seen this improvement for a long time, you are working in this random work, not seeing anything interesting. What you can say is that wow, I made a configuration where something is really wrong. So I'm going to take part of this solution and completely change it. And that's what is called diversification. You can take, for instance, a bunch of, you know, in the, in the consequencing you would take an arbitrary number of swaps, and chance completely your configuration. Okay? In, in the queens, you can start moving queens around in a completely random fashion, okay? Or you can, you know, use more of the structure of the problem to actually have a more, you know, structure based, you know, diversification. But once again, this is very useful. So a lot of the tabu search algorithm will have an intensification phase. And then they will have also a diversification phase. When the intensification is, you know, exhausted in a a sense. Okay? And then there is this very interesting technique as we also use for the TTP, where it's typically in problems where you have both very difficult constraints and very difficult objective function. Typically what you do is to solve the constraint are becoming in the objective function, okay to drive the search of feasibility. And then you also want to have the object, the original objective of course to find, you know very good solution. And strategic oscillation is kind of scheme where you want to balance the time that you spend in the feasible and the infeasible region. Okay? And so you basically try to adjust the power meter. If you spend too much time in the in feasible region, you want to give more importance to the constraint that I have violated. To increase the weight of these constraints. Such that you go back and you spend more time in the feasible region in the hope of finding feasible solution that increase the best so far. If you spend too much time in the feasible region, you may actually not escape some local minima. So you may decide to, you know, let the, you know, give more weight to the objective function. You may go to the infeasible region with the hope that at some point you get back to feasibility, and a better objective function, okay? So once again these techniques are very useful in practice on some of the tabu search algorithm, okay. So final remark in this particular techniques like diversification, intensification and strategic oscillation are actually very useful in many different settings. They are very useful for simulating, they're needing for many other, for many other you know meta heuristic. So use them in those settings as well because they, they can make a big difference in practice. Okay? So this is basically finishing the local search part of the class. what we're going to do in the next couple of lectures is studying looking at mathematical programming, starting with linear programming, and integer programming. So, very, very different paradigm, but very exciting, too. Thank you.