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.

Â