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.

Â