Okay. So this is Discrete Optimization, Greedy
Algorithm Part 2. So what we want to do here today, okay,
is basically looking again at greedy algorithm, okay, on a very simple problem
called set covering. Of course it's NP-hard, so it's not that
simple. Okay?
And then demonstrating, essentially, the essence of the class, which is building,
you know solutions in an incremental fashion.
every one of them improving on the previous one.
We're going to illustrate on the greedy algorithm, but it applies all the
technologies that we cover in our class. You start from the basis, you see how the
basis behave, you [INAUDIBLE] identify the bottlenecks, and then, you try to
improve it. Whether it is constant programming, local
search, mixed integer programming. You know, it's always, you know, always
starts with some models and try to see how you can improve it.
And, typically, while looking at what, you know, the algorithm is doing, you can
identify these bottle necks. But what we do today is a very simple
illustration of that on the set covering problem.
Okay. So what is a set covering problem?
Okay. You have a set of item, okay, and you
want to collect them all. Okay?
the way you can collect them all is that by looking at sets that you can actually
get, okay? Everyone of these set is a sub, you know
contains a subset of the items, you know, that, you know, from 1 to N.
Okay? So in a sense you have these set, these
subset of these, of these items. And you have to choose as few of them,
okay? So as that you take all the items, okay?
So in a sense, what is the smallest of, [INAUDIBLE] smallest set of subset which
contains all the all the, all the items. That's what you are trying to do, okay?
So let me give you an example because this is always easier to explain on, on
an example. Here, you have all the items from 1 to 9,
okay? That's what you see over there.
And then, you have the various sets that you can select.
Okay? So the first set, S1 is covering item 1
and item 4. Okay?
So if you pick up that set, you, you know, you, you would have item 1 and item
4. If you look at set S2, you would have
item 1 through 3, and then item 6 and 7 here, and then you have item 9.
Okay. So you cover six items here, but you
don't cover the same one, exactly the same one as the first time.
Okay? And so on and so forth, for all the
other, you know, all the other subset. So your goal is that how many of these
guys do I have to select, okay? such that I cover all the items.
Okay? So you can look at this and try to find
out how many you need, okay. So what we going to do is build a couple
of greedy algorithm that will, you know, be more and more refined in how we can
find you know in, in actually, you know, optimizing this problem.
Okay? So one of the things that you have to
understand here is, obviously, if you want to select item 1, you know that you
will have to select either Set 1 or Set 2 or Set 5.
Okay? So these are the only three [INAUDIBLE],
the only three sets that are covering item 1.
So you know for sure that one of them has to be selected.
Okay? So, same thing for of use before item 2,
now it's you know, set 2, set 3 or set 6. Okay?
And this is the same for every one of these items.
Okay? So you know exactly which of these
subsets, you know, can be selected for covering that particular item.
Okay? So, we're going to do a first idea which
is trivial. We're going to look at the set in
sequence, okay? Until we have covered all the items,
okay? This is amazingly simple, okay?
So, the first idea that comes to mind, okay?
So, we look at this, but once we have done that, we have a sense of, you know,
of how, you know, how easy this problem is solved, how hard it is.
Alright? So we start with the S1 you know, you
know we cover two items that what you see over there, okay.
So this is all we going to, you know, illustrate the algorithm.
You take the next one. Then, you cover all lot of the items so
there are only two missing, you take the next one you don't cover anything, you
take the second one you cover one more and then you have this one which cover
everything. So you have a Greedy Algorithm here that
will select five of these things, right? Okay, so that's what you see.
Okay, better than six but barely, right? So, item 2 is to say okay, okay.
So, you know, I was doing [INAUDIBLE] something which is completely stupid.
So what I can do now is look at the, this sequence of subset but take the one that
covered the most item first. Okay?
So, in a sense, you know, this is one of the things that this class is, is always
going to, is one of the things that this class is focusing on.
When you start choosing phase, you have to choose carefully.
Okay. So, you basically think, okay, so if, if
I am choosing a subset, I have to try to choose that subset, you know, that, that
makes sense for the, you know, the problem, you know, for the, you know,
using the nature of the problem. Okay?
So in the sense, the intuition here is that we would cover many more elements,
so you hope that you will do better. Okay?
Once again, we look at these sets, we compute how many elements they are
actually they are actually storing, okay? That's what you see over here.
So, some of them ask/g, you know, are covering 6, some of them are covering 5,
and so on. You take the one that covers the most,
okay? And then, you see all these items, which
have been covered. Okay?
You take the next one, you know, which is 5 here.
You take the subsequent one, which is also five items covered, and then, you
take the one that cover 4. And now, basically, with four sets, you
can cover all the items. Okay?
It's a little bit better, okay, 4. Okay, not, you know, not much but at
least you know this give you a better solution.
Okay? Now, obviously, at that point you have
realized that, well, you know, the first one I select probably, you know, nicely.
But when I look at the second one that I selected, okay, it may already cover many
of the elements that I have already covered.
And that should not be contact, So, what you want is to basically look at the
greedy algorithm which, at every step, is not only looking at all the items, but
only the one that haven't been covered so far, okay?
So, we take the very similar ideas that we have done for, you know, the greedy
algorithm number 2, but now we upgrade it by updating the various elements, which
are actually covered by the sets. Okay?
So, we start out with [INAUDIBLE], you know, the biggest set here because it's
the only one covering six items, okay? Now, you see all these items which are
being covered. The only thing that we should really care
at this point are items which have not been covered.
So, we update the number here. Okay?
In such a way that [UNKNOWN] is represent the number of item, which are not yet
covered, that the sets are covering. Okay?
Another, the item which is the most valuable is item S5 because S5 is
basically covering two items that have not been covered so far.
So that's the, that's the second set that we going to cover and in this particular
case almost all the item has been selected except one.
Okay? So, usually, we update this table again,
okay? And there are basically only two sets
that are covering this particular item. Okay?
And therefore, we select one of these two.
And we have a solution with three items, okay?
So what you have here is a greedy algorithm which covered, you know, three
sets. And this greedy algorithm, in fact, has
some performance guarantee. You can prove that it's never completely,
you know, outrageous in the quality of the solution.
I won't go into the detail, okay? But this is a greedy algorithm that
actually has performance guarantee, okay? But, once again, you know, the principle
here was saying, okay, so we move and we try to design this greedy algorithm in
step wise refinement using more and more of this structure of the problem.
Okay. Now so this are the various steps, of
course, every one of these algorithm is more complex than the previous one.
Okay? They are typically, now we are doing
things which are dynamic recomputing, what is the best set dynamically, so the
complexity increases but the quality also increases.
And so, you know, one of the things that you try to do in optimization is always
trying to find the good trader between the time it takes and then the quality
that it gives you. Okay?
So, can we do better? Is three, is optimal?
Okay. In this particular case three is not
optimal. You know, I'm sure you have noticed that,
you know, the sets you know, S5 and S6 were really complementary.
If you're setting the two, you cover everything.
So, that was the optimal solution. So, a greedy algorithm is typically is
not going to give you the optimal solution, but you can start you know,
looking at how good it is. Okay?
And understanding that as well. Okay?
Now, so once you have these greedy algorithms, one of the things you can
start to do is to say, okay, so can I actually move to another technology and
which technology, you know, is going to be appropriate?
Okay? In this particular case you can start
looking at this problem and say oh, but you know, there are dominance.
There are some set are really dominated by other ones.
Okay? So, for instance, in this particular
problem here set S2 and S3, okay, are really closely related.
You know, S3, okay, is covering only a subset of the item that S2 is covering.
So there is never, never, never any reason to consider S3 because taking S2
is always better. So you could say, okay, so S2 dominates
S3, we can get rid of this. Okay?
So symmetries and dominates are very important, you know, optimization
properties, that you want to, you know, use in practice.
Okay? And in this particular case, we can get
rid of one set. We'll never have to consider that set.
Okay? Now there is another kinds of properties
that we are looking at, okay? So look at this, okay?
So if we look at item 5, there is only one set which covers item 5.
So what do you know? You immediately know that you have to
select, you know, set, you know, S5. Okay?
As soon as you select S5, okay, you're going to select not only item 5, but item
4, item 1, and so on and so forth. Okay?
And in a sense, you reduce the size of the problem tremendously.
Okay? So, once again, you have to do this.
Because you do this, you reduce the size of the problem tremendously.
And so, this is a really nice property to exploit.
Okay? So in a sense, so what I'm showing you
here is try, is exploiting properties of the solution.
Okay? And this is one of the typical thing that
you do, for instance, on Constraint Programming.
You look at how you can actually eliminate many of the possibilities
quickly, kay, using, let's say, symmetries or dominence or things that
you necessarily have to do. This is a property that every solution
will have. Every solution has to pick up item 5,
therefore, will contain set S5. Okay?
Now the other way that you typically can turn a greedy algorithm into a constraint
program, for instance, is by saying, you know, I made a choice of the first set,
what if I had taken another set, okay, instead?
And now, you can start exploring other alternatives.
So in the sense of a constraint program, you can think of it as like a greedy
algorithm where you explore many things at every one of these steps.
So you will basically prune the search base using various different kind of
techniques. So these things are not as completely
separated as you may think of. Okay?
So this is essentially, you know the way you can build, you know, greedy
algorithm. You can build, you know, optimization
programs step by step. Okay?
And, and this is a little bit the kind of metholodologies that you have to follow
when you are trying to tackle a new optimization problem.
Okay. Thank you and good luck.