Okay? Now, you may say yeah, that's a

neighborhood, but you know, why not swapping three edges.

Okay? I want to remove three of them, and then

essentially replace by three other edges. Okay?

So that's, that's obviously a nice neighborhood.

This is called 3-OPT. Okay?

And you see the idea here, you see the pattern, right?

So, this point scientists love this, because now we can write infinitely many

papers, right? We can do 2-OPT, 3-OPT, 4-OPT, 5-OPT.

Okay? So this is nice.

Okay? So so this is this is 2-OPT okay?

So remember, you know, I told you before crossings are terrible so you can remove

these things, okay? You can remove these two edges, replace

them by two other edges, okay? That one and this one, okay?

And now you have an, so that's basically 2-OPT, okay, and you are to replace, you

know, the orientation of the edges around, around that part of the cycle,

okay? Now, 3-OPT is going to be removing three.

Edges, okay? So you see this one, you see this one,

you see that one. Okay?

So this out of three edges that we remove, and know we are three edges 1, 2,

and 3 here. which are basically the three edges that

we are replacing the original edges by. Okay?

Now this is a 3-OPT, we have to reverse the direction of that edge and you get

another nice two, okay? So we saw 2-OPT, we saw 3-OPT.

Okay? And you may wonder, you know, what is the

difference between them? Well, usually 3-OPT is going to be better

because it, it contains 2-OPT as a, as a, as a, as, as, as a sub-neighborhood.

It's in general much better than 2-OPT, okay, in quality.

But it's also more expensive because now we have to.

Examine, you know, a much larger set of, of combinations, okay?

I told you that, you know, computer scientists love this thing because now we

can, we can start investigating 4-OPT and typically, if you do that you will find

out obviously 4-OPT is going to be. Better in quality but now it's become

really, really, really more expansive. And then you may say, okay but what about

5-OPT, and at that point there is this genius which is basically killing the

entire, you know, set of paper, okay? Because it's going to define K-OPT, okay?

And basically the key ID here, is instead of looking at these neighborhoods one at

a time, you may say well you know. Typically there will be a good k but I

don't know what it is, okay? And so essentially what I want to do is

replace the notion of, okay I'm basically doing a swap.

We've a sequence of swaps. I'm going to look at a sequence of swaps

that I can do and for and, and, and then dynamically I will choose which

sub-sequence is really nice. Okay?

So, of course I won't search the, the entire set of sequences, they are way too

many of them. But I'm going to explore the seq, you

know I am going to build the sequence dynamically, and try to find an amazingly

avoid, for instance, selecting. The same cities twice and things like

this. So I'm going to build only one sequence

in an incremental fashion and trying to have, to build a sequence over certain

quality but at a high level this is what you do.

Right,so you start with. One possible, one possible move and then

you start exploring all at once and you move along this shunt.

And so at the beginning you know by performing more swaps, by being, you

know, making several swaps in sequence. I may actually, weaken the quality of a

solution but at some point it can be really become very good and then it can

deteriorate. It can actually deteriorate the quality

of the solution. And then at some point, you know, you

stop because you have selected everything.

And so the key idea of K-OPT is that you, you, you explore this sequence.

And then you step back and you say, well, but what was the best sub-sequence?

And in this particular case, you'll find it here.

This is where the best improvement was obtained.

And so what you now that you have to do is basically perform these sub-sequence

of move and, if you do so, you will have the best improvement here, okay?

So the key point is to try to build incrementally this sequence.

And then, when you have built the entire thing, you look back at the best

sub-sequence and you execute that, okay? So, how do we do that?

Essentially, you want to find, you know, essentially what, if you, I try to

summarize what we just did. We tried to find you know, the key, key

moves that are really good, okay? Dynamically while trying to do that,

okay? We are not trying to fix K at the

beginning. We are trying to find a good, you know,

set a good sequence of moves that will improve the cost, you know,

significantly. And so we are basically exploring, you

know, sub-sequence of higher and higher, you know, longer and longer sizes.

Okay, so this is, this is what K-OPT does.

Okay, so if we look at these slides you won't understand anything.

If you don't see a picture, it's not going to work but this is let me just go

over so as to get an intuition of what we are trying to do.

So what we'll do is we'll take a vertex and that vertex is a successor.

That, that we have an edge there and let's assume that this edge is very long

okay? So what we're going to do is we're

going to look at the next vertex in the sequence and we going to try to select

another edge which is very sharp. So the basic idea is that we want to swap

these two edge okay? Of course, when you do that there is

another edge which was pointing to that success so we have to remove it.

And then essentially you can connect the first one to the, the vertex that we just

disconnected. And then you have a two, okay?

So you have essentially a two-swap move, okay?

So let's look at that visually, okay? So we come back to this slide afterwards.

Okay? So we select t1, right, okay?

So that's what we have, okay, and we select t2, okay?

So that's basically, we select this edge. And this edge is long.

So we say, maybe we can actually find something which is shorter than that,

okay? So we select another vertex t3, okay?

So that's you see over here, okay? And then this edge here is short compared

to the edge so we're going to remove that and put that edge.

Okay? Obviously now, we have these edges here

which, you know, we have two edges going that are going to t3.

That's not good. So, t4 there, we have to remove that

edge, okay? And now, the key point is that if we take

t1, okay, and we connect it to the, to, to, to t4 here, we would have.

we would have another tour. Right, so this is what we see on this

one. Okay, so and the key ID is that we could

do that. Okay, so this is a two-swap move.

But we won't do it. Okay so we won't, we won't connect t1 to

t4. Okay, because the reason is that we want

to explore this sequences of move. Okay, so if we look at the slides that

I've shown you before which was impossible to understand for anyone.

You know, in his own mind. So the only, so you see now that we have

these two edges, you know X1 and X2, so that was the long one and the short one,

okay? And then, essentially, what i was telling

you is that when we connect T4 to T1 we have a tour again, okay?

But what I'm saying, what I'm telling you to do now is that you compute the cost of

this, this is, you know, in the beautiful sequence that I've shown you, that's one

of the cost. But we don't want to connect them.

No, we don't. We are going to continue doing

interesting things, okay? So what are we going to do?

Okay? We going to simply consider, you know,

basically swap t4 with t2 in the slides that I've shown you.

So we basically restart the process but the edge that we select, no is not

between t1 and t2, it's going to be t1 and t4.

That's a long edge, most likely. And therefore we try to see if we can

connect t4 to something which is smaller, okay?

And that's what we do here, right? So we have these long edges, no?

Okay? Between t1 and t4.

And what we want to do is, can I find a shorter edge, and do the same process

again, okay? And of course here we connect, for

instance, t4 to t5. Okay?

And then, no of use, the, there are two things pointing to t5, okay, so we have

to remove one of them, okay? So we remove this guy, okay?

And now, what we do, is basically, once again, what would be nice now is that, we

could connect actually t6 and t1. Okay?

Or t1 and t6, okay? And get, that's what you see over there,

and get another two. Okay?

Now, do we want to do it? No, no, no, no, we don't want to connect

at this point. We just want to compute the cost and say

wow, this is like, a 3-OPT, okay? I have the cost of this 3-OPT, no I have

the cost of 2-OPT, I have the cost of 3-OPT, okay?

I can compare which one is better, but I don't want to stop there.

Right? Once again, what I'm going to do is, do

the same algorithm that I've shown you. But instead of starting with t1 and t2,

I'm starting with t1 and t6. Of course, that edge doesn't exist, but I

just pretend it's there. And then from t6, I'm trying to find out

if there is a shorter edge to this t1, t6 edge.

Okay? And that's what I do.

Okay? So, I looked at a.

T6 over here. Okay?

And I tried to see if there is a smaller edge.

That's what you see over there. Right?

And once again, I have to remove you know, the other edge that was pointing to

t7. Okay?

So, which was this guy over here. Right?

And now, I can you know, once again connect it to t8.

Okay? T1 to t8.

Okay? And now, I have a 4-OPT.

Okay? So, what you see, what you are seeing me

doing here is doing, okay, I have a 2-OPT.

Then I continue to search, I get 3-OPT [SOUND], I continue and I get 4-OPT and

in this particular case I'm going to be stuck at this point because from t8 I

won't find and edge which is smaller than that, okay?

And so I can stop and this is my sequence.

Then I can look at the various tour that I seen, you know, the 2-OPT, the 3-OPT,

the 4-OPT and select the one which is better.

Okay? The key point here is that I'm not

exploring the entire neighborhood for 4-OPT or the entire neighborhood of the

sequence. The only that I am doing is building the

sequence of move, one step at a time. And then I look back, I step back and I

say which one was the best? Okay?

And that's the one that we select. Okay?

For the first iteration. And let's assume that this was the last

one because this looks like an i two, right?

So, at this point, I've done one iteration, I've found one sequence, and

the best move in that sequence. Now, I start the second sequence.

Okay? So, I start the second iteration.

Okay? And let's say that I, that my t1 is over

there, this is t2. I decide to link t2 to this guy because

that's a very short edge. So, it's smaller than this one.

And then I do the same. And this is essentially the first

configuration that I get. And then I take another edges, you know

from t4 to t5 I get the t6 over there. I reconnect this.

And this is the beautiful tour that I get afterwards.

Is it better than the previous one? Well we would have to compare the cost.

But essentially no. I'm basically showing you how this

sequence will work. Have, have been working, right?

So you select the first sequence. That's the sequence of move.

You select the best of them. Okay?

Then you move to another iteration. You select another vertex, you select

these edges. And you keep selecting this sequence and

then the sub-sequence which is optimal. And that's K-OPT.

Okay? So, you see, what we have done here

essentially. Is looking at neighborhoods that are much

more sophisticated at just assigning a variable to a variable, or assigning, you

know, swapping two values. Okay?

So, we are trying essentially to find a good sequence of moves.

Okay? And this is a very, very effective

neighborhood for this traveling salesman problem, okay, so, summary here, okay?

We saw two problems, which were optimization problem.

We looked at one which is warehouse location where there were very simple

neighborhoods. We looked at a TSP which has essentially,

a variety of neighborhoods that you can apply.

Okay? And they will have different strengths

and K-OPT is something that is focusing on essentially finding a sequence of

move. Not a sequence, not a single move.

Okay? Thank you very much, and next time we'll

see graph coloring.