0:00

So, this is Discrete Optimization, Local Search Part three, okay?

And things are going to get more and more interesting.

So, we're going to see two interesting problems today.

One is warehouse location, very, you know, well-studied problem.

And then we're going to see the traveling salesman problem, which is probably the

most studied programming optimization. So the key point here is to start doing

optimization, look and search for optimization problems.

Okay? So let's start with the warehouse

location. So what you have here is you have a set

of warehouse, you know, place, a set of locations where you can place a

warehouse. And then you have a.

Large set of customers and your goal is to actually choose the location of the

warehouses. So that you minimize two things.

Okay, the cost of setting up the warehouse.

And then the transportation cost from the warehouses to the customers.

Okay, so this for instance, one particle of configuration.

You can decide, oh I'm opening one warehouse.

And then all the customers have to connect to that particular warehouse.

Okay? So whatever's cheap cost for opening the

warehouse, but of course there are customers that are really far and they

have to travel very, you know they have to travel a lot before you know, being

served by the warehouse, okay? So in a sense.

You can have another configuration where you open two warehouses, so the fixed

cost of the warehouses are going to increase.

But now, the customers are closer to the warehouses, so the distribution cost, the

transportation cost are decreasing. So this is one configuration with two

warehouses open. Okay, this is another one.

The two different warehouses, and two different assignments of the customers.

Okay, so formally, this is what the warehouse location problem is.

Okay? So we have a set of warehouse locations

that we can actually build a warehouse on.

And for every one of these locations we'll have a fixed cost.

Okay, so fw that you see over there is essentially the cost of opening and

maintaining your warehouse, okay. Now you also have set of customer, c,

okay? And for every one of the warehouse and

every one of the customers you have a transportation cost from the customers to

the warehouse. Okay and what you want to do is to find

which warehouse to open such that you minimize the two things.

The transportation cost from the customers to the warehouse and then the

fixed cost of opening these warehouses. Okay?

So that's the problem. Okay, now its a beautiful problem because

what, you know, they are new constraints. Okay, so essentially.

You have, the only, well, essentially the only implicit constraint is that, you

know customers have to be connected to a warehouse which is open.

But this is not really a constraint, right, in that sense.

So, the decision variables in these, in these problems are going to be which

warehouse I'm opening, okay? Or closing, okay?

So there, there's is a for every one of the warehouse, I will have a decision

variable, 0/1, which decide whether the warehouse is open or not.

And then for every customers, okay, I'm going to assign one warehouse, and that

warehouse has to be open, okay. So in a sense when you think about it

from a local search standpoint, it, you know, there are essentially no

constraints. What is the objective, this is the

objective, okay? So the objective is minimizing the sum

for every one of the warehouses of the fixed cost of the warehouse's times, you

know? Whether the warehouse is open or not.

And then the transportation cost. How much does it cost to move from one

customer to a warehouse or vice versa? Okay?

So that's the objective function that we are minimizing.

Now one of the key observation here that you have to realize is that.

Once you open a warehouse, it's very easy to decide where the customer should be

allocated, which warehouse they should be allocated to.

And the reason is that, you know, there, basically what you want is to minimize

the transportation cost. And therefore, once, once you know which

warehouses are open, a customer should be assigned to the warehouse, which is as

close as possible. And the reason is that there are no

capacity constraints on these warehouses, okay?

So, in a sense, the objective can be view of, okay, so which are the warehouses

that I'm opening, knowing that essentially afterwards.

You know assigning the customers is easy. You want to assign the customers to the

warehouse which is, you know, which is open and which is as close as possible to

the customer. So in a sense for every customer what you

want is to minimize, to find the transportation cost which is the smallest

given the warehouses which are open, okay?

So once you know the warehouses its very easy to know which, how the customers

have to be allocated and you can compute this cost easily.

Okay? Now, what is the neighborhood?

Okay, so what kinds of neighborhoods are we going to consider for the warehouse

location problem, okay? Now many possibilities, but let me just,

you know, mention two of them. One of them, is that you can have the

most simplest neighborhood ever. The only thing you do is you decide

whether, you know, decide to change the value of a warehouse, okay?

If it was open you close it, if its closed you open it, okay?

That's the, that's the simplest neighborhood you can imagine for, right?

You decide whether you open or you close, you change the value of a warehouse, you

know? Flipping it's value, essentially.

From zero to one, or from one to zero, okay?

So, that's a very simple neighborhood. But you will say, yeah, but this is tough

sometimes, you know? It makes no sense to close a warehouse,

you probably want to open a, another at the same time, and you can usually do

that, okay? So.

You can think of a neighborhood which has two neighborhoods, one of them is

going to flip close or open a warehouse okay?

And the other one is something where you will simply decide that you have one

warehouse which is open, another one which is closed and you going to swap

there values. Okay, so you open the warehouse which is

closed and you close the warehouse which is open, okay?

So you can use these two neighborhoods and so on and you can, you know, you can

try to decide for yourself. What would be good and the efficiency of

these various neighborhoods, okay? So that's essentially what you can do for

warehouse location. Now, I want to talk about the Traveling

Salesman problem now because the neighborhoods here are going to be

really, really interesting, okay? So what you see for the warehouse

location is a set of cities that you have to visit, okay?

And the goal is that you have one salesman and, you know, one traveling

salesman problem and that salesmans have to visit every one of these cities

exactly once. And, and, and wants to minimize the total

distance that it will travel. Okay?

So, you know, Bill Cook, who is an expert in this, in this area, would always model

with this example by saying this is the Santa Claus problem.

Right? So, you you know, this is, you know, all

the cities are actually children, you know, who have to receive presents.

And the goal of Santa Claus is to visit them you know one, you know exactly once

and minimize this travel distance that time its going to take for traveling.

The and and bring these presents to everyone.

Okay, so its this one of the that we can do.

Okay one of the two that Santa Claus can do.

Okay so you see, you know, you see basically

You see basically the various the various cities that are being visited exactly

once. Okay?

And, and this is another tour. OK which looks better than the first one.

So which one is actually the shortest one is probably this one.

But that's what you want to find out. So you want to find out which is the

tour, which is basically visiting all these, all these cities.

Exactly once, and, and minimize the travel distance, the overall travel

distance. Okay?

So formally, you have a set of cities to visit, and you have a symmetry, you know,

distance matrix, which is telling you the distance between every two cities.

Okay? The fact that it's a symmetry distance

matrix is actually pretty important. Okay?

so what we want to do is to find a minimum, a tour of minimal cost.

Which is visiting every city once. Okay, so you never want to come back to

the same city twice, okay? And you are basically you basically want

to minimize the sum of the, the distances between the cities that you're visiting,

okay? as I said before, the traveling salesman

problem is probably the most studied problems in all combinatorial

optimization. And there are a lot of beautiful results

in using many different approaches on this, on this particular problem.

So this is essentially a very high level constraint programming model for this

particular example. Okay?

And is very similar to what we did for, you know?

Euler Knight problems where, you know, we had this knight that had to move across

the chess board and visit every one of the squares exactly once.

Okay, so what you see here is that we have a set of cities.

Okay, these are the cities that we want to visit.

We have a distance matrix between everyone of these cities.

That tells you, you know, how far these two cities, how far apart these two

cities are. And then the decision variables start to

say well for every one of these cities what is the next city that you, you will

be visiting, that the traveling salesman will visit.

Okay? And what you minimize is the sum, the sum

of the travel distance. Okay, so which is.

Which is essentially the only thing that you have to do is to take for every

cities what is the distance to the next cities that the traveling salesmens have

to visit from that popular city. And that's what this is denoting here,

okay? And that eventually you want to have a

circuit which means that you visit. Every city once and come back to the, to

your starting point. Okay, so we're going to ignore the

circuit constraints basically because we are going to assume that it's always

satisfied, we maintain the circuit. So, essentially we will always be in a

circuit like that, in a tour like this and the goal for us will be to move from,

you know. But, you know, long tour to shorter and

shorter and shorter tours, okay? And so what I want you to think about, is

what is going to be the neighborhood in this particular case, okay?

And so this is a problem when the neighborhoods start getting more

interesting, right? So what is going to be the neighborhood

for the traveling salesman problem? Okay, so think about it a little bit.

Okay, now you will see that there are a lot of possible neighborhoods and this is

one of them. It's called 2-OPT, okay, and the basic

idea as I've told you before we want a tour, okay, we want to stay in you know

this tourist you know, we always want to keep a feasible tour.

So, what we going to do is select two edges, okay, inside our tour.

And we going to replace them by two other edges, okay?

So look at this. This is one of the tours that you see,

okay? So you start from there, you move, you

move, you move, you go up, you go there, and then you know, you go back.

Okay? So and, and what is interesting in this

particular case is that you see that there is a crossing there, you know, for

this particular problem. The way I phrase it.

This is always bad as soon as you have crossing.

You know that you are not optimal. So you can decide to remove two edges,

like these two edges over there. Right?

So, these ones that were basically crossing.

Okay? And then what you can do is to replace

them by two other edges. And you have to make sure that you get a

tour back. Okay?

So, what you see here is essentially the tour and the edges that we are removing.

You replace them by two other edges. Okay?

So you see the two new you see the two new edges that we have inserted here.

Okay, so this one and that one okay? And of course when you look at the actual

specification of the tour and when you look at the tour here you know you see

that some of the edges no are not in the right direction so you will have to fix

them. But essentially what you do is select two

edges, you replace them by two edges you fix the different direction of some of

the edges. Such that you get another two.

Okay, and that's essentially the 2-OPT neighborhood, okay?

So what you do is you select two edges, okay?

These two edges you know, will be removed from the two.

Will be replaced by two other edges, okay?

And then you will have to fix a little bit the tour in between the two edges

that you've selected such that. You know, you get a two back, okay?

So that's the 2-OPT neighborhood, okay? So in a sense, you know, you start from a

tour and the neighborhood is all the set of tours that can be reached by swapping

two edges. And, and by swap, by swapping out two

edges and bringing two new edges inside the, inside, inside the tour.

11:49

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.