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.