0:00

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.