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.