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.