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. 
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.