0:00

Welcome back this is Discrete Optimization Local Search part six.

Okay so what we're going to do today? Start talking about this topic of

escaping local minima. And we'll introduce a very important

notion which is connectivity. And talk a little bit about various

neighborhoods and how they relate to this, this notion.

the big goal here is that we are setting the stage for.

Introducing techniques that will allow us to actually find higher-quality solution,

not just producing, you know, move, that are improving all the time, but allowing

the search to do more interesting things. But a requirement, you know, in general,

is that you need some property of you neighborhood to do good things, okay?

So, remember, you know what we did, that the guarantee that we have is we apply,

you know, greedy moves inside a neighborhood.

Is that when we complete the search we are guaranteed that the value of the

configuration that we find is a local minimum.

Okay, so which basically means that if you are that position in that space, if

you look around there is no place you can go which is better.

That's what it means to be a local optimum, okay?

You can move to a place which is better, okay?

But that doesn't guarantee that this place is actually good in the grand

scheme of things. They could, there may be something really

good somewhere else, and you don't know how to get to it, okay?

So, we have no guarantees for optimality, and therefore, in practice escaping these

local minima of, of poor quality is a very important issue.

And once again, the next lecture will show you two really interesting

techniques to do that. What we are doing today is setting the

stage for that, okay? So this is a beautiful picture done by

Carlton, right? So you see this is kind of the

neighborhood, the entire regions of the space, okay?

So, so, so you see you know, in this particular case, you know.

Basically, this neighborhood is colored into you know, cold and hot region.

And hot means high quality, cold means terrible, right?

And so, local search dots for you a point.

You define the neighborhood of that point.

And then, what we have done so far is taken a direction which is improving, you

know, which is improving the, the move. And so we follow this, and then we can

continue finding a path. Oops, and hopefully.

We, you know, we get to a good region of the space, okay?

So that's what we have been doing so far, okay?

Now, the, the landscape of the objective function, okay, can be complex like this

one, right? So, so what you see here is the various,

the quality of the solutions, and we are minimizing, okay?

So this is essentially all a possible solution and this is the quality.

And what you see here is there is various local minimarts in that popular place,

right? So this is a local minimart this is also

a local minimart and you know this one is actually pretty interesting.

This is the global Minimum. Okay, so that's the global minimum in

this particular case. So we want to get there but the search

that we have seen so far are not going to get you there, right?

Now, one of the things that you really don't want to happen is this, okay?

So you can't define your problem, okay, in such a way that it's not connected,

which means that if you start from that particular point.

You can move inside that region right. And find a good point in that region

which is here. But you have no way to actually get

there. There is no move that will get you there

and that's terrible. The entire region here which is where the

good things are is not accessible if you start from there.

Okay, so we don't want that. This is not good okay?

So we have no way of moving from one side of the neighbor to the other one.

And so we want to avoid that and the connectivity requirements that I'm going

to talk about is exactly avoiding this. Okay, so this is a definition but

essentially what it means is that you want to be able go from any configuration

to at least one optimal solution. Okay, so in a sense you're going to say

that neighborhood N, and remember that a neighborhood is something which given a

configuration is going to give you a set of configuration where you can go, okay.

So neighborhood N is going to be connected if from every configuration S,

anywhere, okay? So there an optimal solution O that you

can reach by taking local move and what is a local move?

Well you start from s, OK that state at zero.

Okay, and then you can take a local move to go to a s1, then to s1, to s3 and so

on up to s n which is the optimal solution that you are looking for and

everyone of these configurations can be accessed by your local move.

Which basically means that SI is in the neighborhood of SI minus 1, right?

So this is the definition of connectivity, intuitively it's very

simple. It basically means that you can apply

local move from any configuration to get to the optimum.

It doesn't mean that you will get there right?

It must means that there is a path, okay? Afterwards we need to find that path.

But what we know is that for sure there is one path to an optimum solution, okay?

Now, connectivity doesn't guarantee optimality as I just tell, told you,

right? Because so far, our local search has been

greedy, okay? So, what happens when you are greedy,

okay? When you are greedy, let's say this is

the starting point. When you are there, you're going to prove

you're not going to, you're going to take move that are basically improving, okay?

So, if you take move, that are improving, you're going to get to this local minima.

Okay, so you think, another point over there, beautiful point, you go down,

drop, that's where you get. You don't get here, right.

Because if you try to improve all the time, you're not going to get there.

You will have to go up the hill and then go down, right?

Which is not something that we have been able to do so far.

And obviously, you know, you have all these points here that are basically

bringing, oops, I want to show you that, because they are so beautiful, right.

So that are going to all these places, but they don't get to the global, to the

global optimum. Okay, so in a sense, connectivity doesn't

guarantee optimality, but it's still a very good property to have.

Because once we entry some of the techniques that we'll see, you know, in

the next lecture, you know, in connected neighbourhoods you may have more hope and

actually in some cases guarantees to get. two of the actual optimal solution.

So, what you see here is graph coloring. Remember, we had this beautiful problem

where you would color these, all these vertices, such that two adjacent nodes

were colored by had to colored by a different color.

Okay so and the neighborhood that we chose was very simple, right?

It was changing the color of a note. And usually that neighborhood is

connected, and I'm going to give you a simple algorithm, and this is actually

very interesting because we are heating like hell, but this is what you do when

you want a sure that something is connected, right?

So what you have to do is you start from the configuration.

And you have to show a path, you know, that indicates that you know, that brings

you to the optimal solution. But, we can do a really nice assumption.

We can actually postulate that we know the optimal solution, so if I know the

optimal solution and I'm in a particular configuration, I can design a very simple

algorithm to get to the optimal solution. What do I know?

I look at every note and if that note okay, doesn't have the right value that

means that it's value is different from the value in the configuration simply

assign it's value which each value which is in the optimal solution.

So I do that for all the notes okay, this, they are all legal, right?

And then essentially I get to the ultimate solution.

So, this is very easy, right? So, but all the connectivity groove are

like that. So, you, you suppose that, you basically

assume that you have the objective, the optimal solution.

And then you have a particular configuration.

And you show you can actually get there. No, this is a very simple one, right?

Some of them are very complicated, okay, but this gives you the essence of these

kinds of proofs, okay? Now, remember car sequencing, okay?

So car sequencing once again we were scheduling these cars on the assembly

line. The production unit that is to put these

options while the cars were moving, right?

And we had to satisfy the capacity constraints on this production unit to

make sure that we could put the options. On the cars, right?

So, what we designed was this beautiful neighborhood, right?

where we would basically look at the cars and swap them, okay?

And here you see the options of the various car, okay?

So we have a swap neighborhood And this swap neighborhood is connected, okay?

And why, let's look at the algorithm. So actually, let's go back and look at

the sequence right? So we can take this sequence and look at

the values and either you have the right type of car there or you don't, okay?

If you don't have the right type of car, what are you going to do?

Well, there is your type of car somewhere inside the sequence.

You can swap them, and now what do you have?

Well, the first slot is right. You move to the next one, okay?

The next one you say, well, you look. Is it right, or not?

Is it the value that you have in the optimum solution?

If it is fine, you move to the third one. If it's not, you look for the right type

of car, and you solve these two thing, okay?

And so you can continue doing that, and that's how you show connectivity, okay?

So, once again, that's what you see there.

You have an algorithm which iterates from you know, the first to the last load of

the assembly line. Then you look essentially it's the value

for the configuration s, you know, s i is the same as the value of that part, of

the slot you know, of position i in the ultimate solution that's o i.

If they are different, what you do is you look for a particular config.

[SOUND] A particular configuration inside, a particle type of car inside the

sequence S, you know, and, and further away, obviously, which is of the type,

the same time as the value which is inside the automobile solution.

And you swap these two things. And you continue like that, and

obviously, you know that you will find one, right, because it's in the optimum

solution. And therefore, you, you solve all these

things and you get an observable solution at the end.

So what I'm showing you here is a very, is essentially that by, by, by doing

swaps, you will always get to the optimal solution by a sequence of move.

Now once again, I want to repeat this. It doesn't mean that your algorithm is

going to find that sequence, right? Because we are always trying to find

improving moves and things like this. We would have to do other things.

So in practice, some of these steps here huh, may be degrading tremendously the

quality of your solution. At that's what is the challenge in local

search, right? So, let me, let me look at something

which is a little bit more complex, right.

So this is the traveling salesman problem.

Remember We had all these cities that we had to visit exactly once, okay.

And trying to minimze the total distance. And we introduce this simple

neighborhood, that's one of the simplest that [UNKNOWN] 2-OPT.

Now remember 2-OPT was basically taking two edges and replacing them by two other

edges. And the question that you may be asking

yourself, that is this neighborhood connected, okay?

So, very simple question. Because it has only two possible answer,

right? Yes or no?

So, think about it. Is it connected or not?

10:36

So, to actually find that out, so look at this thing, okay?

So, look at this particular tour. Is there another way to view this?

Well first let's, let's start numbering these guys so we have all the vertices

and the name of these vertices. Okay, and know a two, you see the two.

You know, starting from one, moving to five, then to nine, then to ten, then to

six, three and so on. Okay, so when you look at this tool, this

tool is really like a sequence, right? So you see the sequence here.

You know, one, five, nine, ten, three and so on, okay?

So basically the two here can be viewed as a sequence Right?

Now remember, what you know, two opt does is removing two edges and replacing it by

two other edges that you see over there, right?

So I have a sequence here and you know, what is going to be my sequence for this

thing, okay? So, essentially, what you know is that in

this two, right, so you were basically going to to, to, to six and, and six was

going to three, right? So what we going to do is remove this and

replace it by an edge to seven. And then we going to revert essentially

all these edges that you see on that right side.

And then connect that with an edge going from three to two.

So, we are basically taking these things, okay?

So, the edges that we are removing in the edges going from six to three, okay?

So this is the edge that you see somewhere here okay, and then we have to

revert that so we are basically reverting the sequence.

So what you really get here is that particular sequence there.

So you see you see the original sequence over there and you see the sequence which

is here, which is essentially the same sequence we have here except for we have

revert All the, the ordering. We, we basically reverse that particular

sequence, right? And that's what you see over there, okay?

So essentially what I'm telling you is that 2-opt can be view on sequence and

you isolate a sub-sequence here and what you do is you basically reverse it.

But keep it the same position, but reverse it, okay?

Now, instead of moving from six to three, you move to six to seven.

And then to 11 and eight and four and so on.

And that's what you see over there, right?

So essentially, what you do is you select a six sequence, and you reverse it, okay?

Now, I'm asking you the question. Is this neighborhood connected or not?

Okay, well, we can use a very simple algorithm again, right?

If we know the ultimate solution, okay, and we can posulte that we know it, and

we have a configuration right now, what are we going to do?

Now, assume that, for instance, this guy is the optimum solution, okay?

Which is probably not the case, but never mind.

Okay, but if we look at this thing, what we're going to say, okay, so you know, we

have 1, 5, 9, 10, 6 and this is the same in this supposedly alternate solution.

But then we see here that there is a different between these two guys, right?

There is a difference, okay? So there is one that is starting at

three, okay. This subsequence is starting with three

and that one is starting at seven, okay? So, what do we do?

Well, we say okay, so I'm going to select a move by what?

Well, I want a seven, right? So, this is what I want, okay?

And I have a three, so I'm going to look until I find a seven and then I'm

going to apply a two opt and that 2-OPT is basically going to revert that

sequence, okay? And I will obtain this [INAUDIBLE], okay?

And what is nice about this now is that I can move to the next element.

So this is all correct, okay? And then I can move inside a sequence and

try to do the same kind of things for the subsequent vertices.

So in a sense what I just told you is that I have a very simple algorithm,

okay? Which goes to the various elements of the

sequence very much like I did for the consequence example.

Any particular value in the two, I'm considering now is they're not the same

as the value in the optimum solution. I find the sequence starting at I, which

basically ends with the value in the optimal solution With the city inside the

optimal solution, right? So I have a subsequence, no?

And what do I do? [NOISE], I reverse it, okay?

And that's what you see over there. So I go up to si, I take the sequence

which brings me to the particular point that I wanted, I reverse it so I start

with that guy, which is no correct. I have all the sequence which is there,

and I have my new sequence which is correct.

Not only up to a si-, not only up to s i minus 1, but now also to s i, okay?

And I continue doing that, until I find until I get to the optimum solution.

So once again, very simple algorithm, to move from a particular configuration to

an optimum solution, okay? Now, you know, unless you, I'm going to

leave you with an interesting homework. Remember the TPP, the traveling [UNKNOWN]

problem, okay? So I will show you this beautiful

neighborhood, right, with five moves, sub homes, sub teams, sub rounds, sub partial

teams, sub partial home, okay? The question for your homework.

Is essentially, is this neighborhood connected?

And you, if you find the answer, okay, call me.

You can call me if you find the answer. I'm very interested in knowing if you

actually can find the answer to this particular problem.

Thank you very much, see you next time.