0:00

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.