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.