Okay discrete optimization or greedy algorithms.
So what we want to do in the next two lectures is basically cover greedy
algorithm which is essentially the first step.
You can always try it when you are trying to solve an optimization problem.
Okay? Very simple, okay?
Heuristic, mostly, no guarantees. But it's the starting point, okay so what
we want to define is what is a greedy algorithm and then you know very
informally, right. And then essentially how to go beyond
greedy and that's the things that, that's essentially what we going to cover, okay?
So, so the, the biggest assumption that we are making in this lecture and the
next one is that its very easy to actually find a feasible solution the
real problem here is optimizing, okay? So, when it's tough to find feasible
solution you know, we, we can use other techniques and, and some of them I'll
discuss in, you know constraint programming or local search to actually
transform that in a, in a problem where the finding the solutions are easy, okay?
But here we are basically assuming that finding a feasible solution is easy,
okay? We focus on the objective function.
Okay, and the key idea behind a greedy algorithm is that your going to look at
the variable, the decision variable one step at a time okay and your going to
assign a value for every one of them and in a sense you choose that value to
minimize the value of the objection function, locally.
Okay at this point your choosing a value such that the objection function increase
the least. If we are minimizing.
Okay? So in a sense, we are looking at the
particular variable, we are trying to assign a value, and minimizing the impact
on the objective function. That's what the greedy algorithm here,
okay? Now called greedy algorithm or heuristic,
you know, essentially they are basically making decision one at a time based on
local information. Okay?
So we're going to illustrate that on the TSP problem.
The TSP problem is one, is probably the most famous combinatorial optimization
problem. Okay?
And the key, you know, the key aspect of the traveling salesman problem is that
you have a bunch of cities that you have to visit and you have to visit them
exactly once, okay? So you have to move from one city to the
next and so on. You visit them exactly once and what you
want to do is minimize the travel distance that you have to travel for you
know, visiting all these, for visiting all these sites or these customers you
can think of. Okay?
So this is a solution to the travelling salesman problem okay, so you start here,
you know you, you visit this, this, this particular city you go the next one and
you follow this very nice path and that's essentially a solution to the travelling
salesman problem. Every city is visiting, is visited
exactly once and then you measure you know the distances that you are
travelling and that's what you are trying to optimize, this is another solution it
looks better or probably shorter, okay And so this is once again, you visit all
of the cities once, okay? And in this particular case it seems that
the distance is smaller. I haven't computed it, but it looks
better. So now, what is the greedy algorithm
going to do? So once again, what we want to do is
build a solution step-by-step. So we start from the vertex and we know
that, that vertex, that you have to go to some place from that part of the vertex,
okay? So that part of the city, okay?
So we take the, you know we take its closest neighbor okay, and that's where
we going to go. So you say okay, we start here and we go
there. That's the closest neighbor, Okay?
Then in the next step we are basically saying, okay so you know what is the we,
we, we, we have moved to this particular position and we ask us that exactly the
same thing where is the next place where I can do, where I can go which is
going to cost me the least, okay, what is the nearest neighbour, okay and so in
this particular case you got to that particular you know you, you go to that
particular location once again, you repeat the process: you say what is the
nearest neighbor where I have to go, ok? In this particular case you can say, "Oh,
but it's this guy." So you can visit this city only exactly once, so you will be
able only to go back to this [UNKNOWN] the first location.
When you have visited everything else okay so what is the nearest neighbor
which is not something that I have already been too okay.
And that brings you to that particular location and then you continue okay.
And you built this beautiful tour here okay once step at a time and when you
arrive to the last location. You just return to your starting point,
okay so that's how you do a greedy algorithm with everyone of the step you
are looking oh, what is the next city that I can visit which costs me the
least, okay and does the idea of the nearest neighbour, now you look at the
students here but this is pretty good, right but you know of course that these
problems are [UNKNOWN] hot so there will be cases were these things are not
going to be good, this is one example, okay same instances but we just changed a
little bit the position of two vertices Okay, and the key idea is that we have
done this maliciously, right, just to make sure the greedy algorithm is not
going to work. What's happened, you know, you start from
the same place, you visit the first thing.
You get to this nice location there and then you take the, you know, the closest
location to nearest neighbor to that particular location.
And it's not this point because it has moved, no?
It's this point, so you go down and you do the same thing at this point, this is
the closest neighbor so you go there, and this guy now is left alone at this point.
OK? So we don't really know when we are going
to visit it. We continue, we think we are doing the
right thing at every point, and then we get to this point.
Usually at this point we would like to go back to the depot but we can't, right?
Because we haven't visited all of the cities.
So we are forced to go back to this long location that we avoided going to before.
And then we have to go back to the depot. Now you see that this is a terrible tour
of your state, because we have many crossings, and you have this
long-distance trip here which I completely avoided.
So this is where these greedy algorithms are breaking.
They're going to work sometimes, and they're not going to work other times.
That the essence of these, these algorithms.
There are many greedy algorithms, this is another one, which actually has some
performance guarantees, okay, not very good one in metric space but they have
some. Okay so the key idea here is that,
instead of moving from one vertex to another one, from one city to the closest
one. Here we are going to build the two with
two cities and then we going to extend it to three cities, and then four cities,
and then five cities and so on and so forth, okay?
So we basically look at this particular, this particular two with two cities here,
okay and now we select another city lets say this one, okay and we are basically
asking you asking ourselves okay what is the easiest way to actually insert that
particular city, okay? And the basic idea here is that we have
to remove this edge and insert to other edges, okay and now we have a two wishes
three cities and what we have to do next is try to insert another city, okay?
So we are going to consider this city and we are going to say oh, you know what is
the best way to insert that particular city.
And by best way, what I mean is that the cheapest way to insert that city, okay?
Now you may say, oh, but that seems to be very complicated, but it's not right?
So there are only so many place where you can actually insert this, this particular
city, right? So you can say oh, I'm going to go from
here and then back there and then go back here.
Or you can insert in between of these two.
You can do this, and then go there or back there, okay?
Or you can go actually from here. To this, and then go there, and then you
have a tour of four cities, and this is actually a better tour in this particular
place, okay. So what you are trying to look at every
step is, what is the best insertion point for a city which is not inside my tour
again, okay. If you see this one, for instance, it's
going to be doing this, right. So when you see this guy, he's probably
going to be doing this, this, and that. This guy's going to be doing this and
this. And so you basically build your tour
starting from, you know a tour of two cities, three cities, four cities and at
every point you have a greedy algorithm which insert the next city as best as,
you know, you know in the cheapest possible way, okay?
So that's to know the greedy algorithm, okay?
You going to tell me oh, yeah, yeah but which one I have to use, okay?
Well, you know it's not clear which one i have to use on particular input but one
of the things that you have noticed here is that these algorithm are easy to
actually you know they are, they, they are very fast to run.
So you could actually use several of these and take the best solutions.
And that's, you know that gives you a particular, you know the first
approximation to your particular problem, okay?
So, in a sense, summarizing, there are many greedy algorithms that you can
conceive, even for something like the traveling salesman problem, and I've only
shown you, you know two of them, but there are many more, okay?
Some will do better than others on all inputs, or some, you know, will do better
on some inputs and not on other ones. OK?
It really depends on the partial input, as we have just shown you on one
particular instance. Okay?
The advantage of greedy algorithm, typically quick to design, quick to
implement. You know, they are fast, they typically
are fast when you run them. Okay, now the problem is that typically
you have no guarantees, you know, the insertion method that I have shown you
has guarantee in the case of, you know Euclidean space, okay?
But in general you probably don't have any guarantee, okay?
So, there are some cases where these greedy algorithms have some guarantees
but not always okay, then the quality may vary tremendously depending on different
types of input, okay? Once again, you know you don't really
know, we can't prove things really. It's a starting point, okay?
And of course, we have assumed that it is easy to find a feasible solution.
If it is not easy to find a feasable solution, one of the things that you can
do is to put some of the constraints inside the objective, and then it is easy
to find solution. Then you optimize this function, and try
to get as close as possible to a feasible solution, okay?
So the the greedy algorithm there would tell you, okay, so this is a solution
which is as close as possible to the, you know, to a feasible solution using this
greedy algorithm, okay? So, the essence of the class is that you
can always start with a greedy algorithm, okay?
It gives you a starting point that you can improve afterwards.
And then you can look at the techniques that are presented in this class you know
constraint programming dynamic programming you know local search and
mixed integer programming to try and improve the value its giving you by
degree. So really the class is about how to do
better than a simple greedy algorithm, okay?
But a greedy algorithm is going to give you a certain starting points and you'd
starting on this tending what the problem is really about and sometimes these
greedy algorithm can be transformed easily okay in constraint programming
solutions, okay? There is one step that you can apply and
then it moves to a you know particular constraint programming solution, okay?
So, you know inside in the class what you learn is finding you know, ways of
finding high quality solution. Feasible solution and finding high
quality solution which are robust across many inputs.
That's what optimization is going to bring to you.
And obviously we have techniques where we can actually give you guarantees.
You can come back and tell you know and tell you know oh, I have a solution and I
know that it's not worse that let's say you know 2% of the optimal value that I
could ever find. Okay so in a sense what the class is
covering you is how to find you know, you know feasible solution in complex when
there are complex constraints. Find high quality solution which are
robust across a large spectrum of instances and then give you performance
guarantee, quality guarantees on the algorithm that you have, okay?
So this is greedy one you know come back to see greedy two.
We'll, we'll, we'll go into a little bit more details on how you move from a
greedy algorithm to other kinds of techniques, okay?
Thank you.