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.