Okay, welcome back. This is supplemental material for the assignments. I'm really happy to see you here. Okay? we are going to talk about the traveling salesman problem, which is a really challenging, you know optimization problem. So this is a challenging assignment. and we're going to review some of the concept here. And some of the things that we do in these assignments is actually simplifying your life and I want to go over some of them because you can actually use some of these things on other assignments as well. So remember, you know, what a traveling salesman problem is, is that you have a bunch of points and what you want to do is to find a tool which is visiting every one of these points exactly once. Okay, and minimize the overall travel distance. Or cost, whatever. Okay? So, this is a beautiful tool that you see on that side, you know? It's a tool doing 0, 4, 8, 9, 5 and so on, okay? So an interesting point here is that you can essentially see a tool as a permutation of all the vertices, okay? And this is nice because, you know, it basically tells you how you can actually, you know, output a solution. And you can also think that this is good representation, but it may not be. Right? So, this is one of the things we'll need to discuss at some point. Okay? So, so in this, in this particular assignment, we are going to focus on a very specific class of traveling salesman problem. They are going to be Euclidean, it's a metric space, so computationally these problems are easier. And also they have a big, you know, very nice features that, you know, I will, you know, I will tell you about in a in a moment. Okay? So, it will help you tremendously actually, the fact that we're looking only at Euclidean TSPs. Okay? So, in Euclidean TSPs, essentially, everyone of the points is the coordinates, you know, is a coordinate. Okay, so you see for instance, you know, that point 0, vertex 0, as you know, coordinates 17 and 27. And this is essentially going to be the input of your problem. Okay? And once you have that, we'll be able to compute a distance between any of these two points. And that's going to be the distance that we will be using when we are trying to evaluate the, the, the, the length of a particular tour that we are trying to compute. Okay. So in a sense, the only thing that the input will be concerned with is giving you these coordinates for the point, and from that, we, we don't have to compute this big, you know, give you this big distance matrix. You can actually compute it yourself. Okay? So, so essentially once you want to find out what is the distance between, you know, 0 and 4, you will use the formula that you see here, okay? Which is basically, actually you, you, and you see, you know, the actual values on the bottom. You'll take the x coordinates of the two points. Okay? Subtract, you know, one from the other. Square it. Do the same thing for the y coordinate, you know, square it. Sum them. and then take the square root of the whole thing. And that basically is giving you the distance. Between, let's say .0 and 4. Okay? So what you do is you take 17 subtract 42, square that. You take, you know, 27 and, and, and subtract 56, square that and take the overall square root. And that gives you the distance of 38.2 288 which is the distance between these two points. the Euclidean distance between these two points. Okay? So, what is important here is that we will only give you the coordinate. you know, of the, of the various vertices. And you can compute easily using this formula, the distance between any pair of vertices. Okay? And so essentially, this is summarizing what I told you. The only thing that we really need to tell you is what is the,you know, what are the coordinates between all the vertices and that is going to be the input of your problem. From there you can deduce everything else. Okay, so this is a formulation of the travelling salesmen problem where you see the objective function computing all these distances between all the various cities in the tour, okay. So we are basically modelling here, okay, the tour as a permutation of the vertices. Okay. this doesn't mean that you have to model your problem like this, okay. So in these supplemental materials sometimes we use model. You know, we make no guarantee that these are good models. Okay? It's probably not a very good idea to recompute all these things all the time. Okay? So you may think of other representation. It may also not be a very good idea to model the problem as a permutation. Okay? So some technology may not like that. Okay? And some may. Okay? So, in a sense, you know, every time we put a description of the problem we, we typically make no guarantees whatsoever on whether it's good or not. Its just a particular formalization of the problem. Typically the Python script may use that formalization to give you a basic solution, but, you know, don't make any assumption that this is a good formulation. Don't be, you know, misled by the fact that we are putting that formulation. It may be completely crappy from a computational standpoint. It's just very convenient for stating the problem. Okay? So, in a sense what I need to tell you now is essentially what the input and output should be for this particular assignment. Okay? So the input is very simple. Okay? So I'm telling you how many points there are. Okay? And some of these problems, you know, may have, you know, 50 points, some other ones will have many more. Okay? And then for every one of these points, we'll basically give you the x and y coordinates. Okay? And as I told you, using the formula that you've seen before, we can compute a distance between any of these, any two points. Okay? The output, you know, is basically the format that we are using systematically, okay, so you have to specify the objective function, whether you have, you know, proved optimality or not. And then, in this particular case, we ask you to put, you know, a sequence, which is a permutation of all the vertices, okay? So this is basically describing the tour that you have if you connect the last one to the first one, okay? So in a sense here we ask you the permutation of the end, once again it doesn't mean that your modeling is to use that, okay? You can use a modeling where the decision variables are very different. Okay, but at the end you will have to, you will have to transform this decision variables into something which is a sequence. Okay. this is a particular example, okay. So you basically see here inside a input five vertices and the various coordinate. The first point is 0 0, the second one is 0 you know and 0.5 okay and so on and so forth. And then you see a solution here which has a length of 5.2 and the tour is, you know, 0 4 1 3 2, and so back to back to 0 at the end, okay. And so essentially you see a permutation of the vertices here, okay. And you see the value of the objective function. Okay? So that's what you'll need to output. Okay? Obviously once again and I will repeat that ever and ever, you know, forever, is that we can obviously compute the value of the objective function for this permutation, and that's one of the things we'll check in the script. Okay? So, now one of the really important features of the traveling salesman problem, okay. And especially the Euclidean traveling salesman problem, and the fact that we are actually giving you these coordinates, is the fact that you will be able to visualize what you're doing. Okay? So, you can use the location of these points you know, in the plane to actually see you know, to actually visualize your tour, see where they are, visualize your tour. So, this beautiful output that you thought was very great, if you try to visualize it, this is what it gives you. And this is pretty, pretty crappy, right? So as soon as you have edges that are crossing each other, bad news, okay? So that means that you are very far from optimality, okay? So one of the things that you want to do in this particular, in this particular assignment is visualize how good your tour is when you are using different techniques. And that will help you a lot, because it will identify bottlenecks, things that your algorithm is not doing well, things that you should focus on. And things like this. Okay. Now, the TSP is very nice for doing this. But in most of the assignments this is something that I highly recommend. If you can build a visualization to see how your algorithm is doing. You know? Modeling various aspects of the problems. The objective functions. You know? The various aspects of your algorithm. If it's a constraint programming algorithm iii. If it's a, if it's a local search algorithm, you know? What is the sequence of solutions that it gets your fast. You know? It goes down. Whether it stays at the same place many times, okay? Things like that. If you are using mathematical programming, what is the relaxation? How good is it? Okay. So these things you want to visualize because there will give you a lot of insight on your algorithms, and I'm speaking from experience, you know. I spent, you know hours and hours looking at a screen of you know, data. And sometimes the simple visualization will give you the haha, the wow factor that you need to actually understand what your algorithm is not doing well. So this is a good example here, it's actually pretty easy to do. Build this visualization, it will help you. And this is of use if you think oh, this is a pretty nice tool, right. And so assignment tips. Okay? So there are a lot of assignment tips on this particular problem. There are a lot of things you can do. Okay? Here are a couple of ones. Okay? So first, if you, if you implement a local search, one of the things you need to focus on is, how quickly can I explore the neighborhood? Okay? So, we can have, you know, a lot of very sophisticated neighborhood or a lot of very simple neighborhood but we may want to explore them and they may be very large. How you do that very quickly, okay? So this is a key aspect of, you know, the TSP. Symmetries and dominance, there are plenty in these problems as well. You have to think about them, okay? Can you actually avoid, you know, av-, you know, exploring sub paths and things like that that are dominated by others, or they are symmetrical to others, you know, try to think about that. Now, one of the things in this problem as well is that essentially, every city if you are you know, visiting cities can be connected to every other city. Okay, every vertex can be connected to every other vertex. But do you need all of them? Okay, so think about it you know. You are trying to do a tour of you know, the United States. Are you going to connect Miami to Seattle? You are trying to do a tour of Australia, are you going to connect Perth and Brisbane? Okay, think about that. Okay, so are you going to do that? And also, can you prove that you don't need these edges, okay. So, that's, that's one of the things that you can think about. if you do a complete search, think about the various ways you can actually compute lower bounds. There are many, many ways of computing lower bounds. Different trade offs between you know, speed of computation and quality of the lower bound. And then, as I said, you know, visualize, look at the solution. Look at what your algorithm is doing. What about the algorithm that you are going to do. Sometimes you will be surprised at what it does. And it may be useful to actually visualize, to see. Some of the aspects that you can improve. Okay? I find this is an amazing assignment, okay? And people have, you know as I told you this is one of the most studied problem in optimization. Its very interesting that you actually try you know some of the techniques on this one. So look its very specific, you know a lot of different techniques and different fields you know have been applied to this problem. Okay, good luck.