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.