0:00

Okay guys, so this is the set covering assignment which is not really assignment

Â and so this is a novelty in this session.

Â And the key idea here what were trying to do is to have an assignment that kind of

Â a thick assignment which people can submit their solutions and can share quote okay?

Â So you can share code you can share ideas but not code on the other assignment.

Â But here what we want to do is to make sure that you guys can actually share code

Â and show code on a particular assignment so

Â that people can say this is really how you do local set,

Â this how can you do it contrary programming software and so on, okay?

Â Sometimes it's like in programming.

Â Looking at the code of somebody else can actually help you

Â thinking about how you can actually implement something yourself and

Â this is what we are trying to achieve here, okay?

Â So I'm going to describe the set covering assignment and then I'm going to

Â talk about some of the ways you can share that later on in this video, okay?

Â Now set covering itself is a very interesting problem that pops up

Â everywhere, okay?

Â I'm going to use one real life example here, but there are many,

Â many other examples.

Â And this actually is a problem that pops up in a lot of other actually

Â real applications.

Â Either it's on its own,

Â but generally as a sub path of a more complex algorithm, okay?

Â 1:15

So this is an example using a fire station that has to cover a region.

Â So what you see here is a big geographic region, okay?

Â And everyone of the big dot there, the black dot,

Â is a location where you can set up a fire station.

Â And the key idea is that you have to cover all the small region there.

Â They are numbered like zero, one, and so on and so forth.

Â You have to cover 80% of these things in seven minutes, okay?

Â And so once you get, that's requirement for emergency services.

Â And so what you want to do is select a subset of them so

Â that you basically cover the entire region at the minimum cost, okay?

Â This is a for instance [INAUDIBLE] solution, okay?

Â So you see here,

Â this particular fire station is covering this part of the entire global region and

Â these subregions over there, okay, and so on and so forth, okay?

Â And so in this particular case, you have six selected fire station

Â that basically satisfy the legal requirements of the entire region, okay?

Â And you try to do that of course at the minimum cost, okay?

Â Satisfying the legal requirement, getting to the people in the time that is

Â specified by law but also the minimum cost.

Â So this is how we can model this thing more formally, okay?

Â So in a sense, all the regions that you have seen in the particularly

Â in the example that I have shown are going to be called item, okay?

Â So we are basically given a number of n items, and

Â we will have to cover these items, okay?

Â How do cover them?

Â We cover them by Set, that's why this is called Set Cover, okay?

Â So in this particular case to set a fire station, okay?

Â And it's essentially a fire station is defined, or

Â a set in the more abstract version, is defined by two things.

Â It's cost, that's the cost it takes you to actually build it, okay?

Â And then the items that it cover.

Â You know, when you have a fire station you will know which of the regions

Â you will cover in seven minutes.

Â 80% of which you can cover in seven minutes, okay?

Â And so when we look at the abstract version of the problem, for

Â every one of these sets, we know which item they cover.

Â We get this SI, the set SI which tells you that

Â 3:23

set i is actually covering that many items.

Â Okay.

Â And then so this is the data, these four things there I'm listing out is the data.

Â And then the only decision variable that you need in this particular problem is

Â find out if you select set i or not, okay?

Â So Xi one if you select set I think fire station.

Â I am selecting fire station i.

Â And zero otherwise you don't select fire station i, okay?

Â And so now once you have this decision variable in this data you can

Â formulate the problem mathematically, okay?

Â And what you see there is what you want to do is minimize a linear sum again.

Â And this is the sum of the cost of opening everyone of the fire station.

Â So this is ci which is the cost of set i times xi which is zero if you don't open,

Â if you don't select that set or one if you don't select that set okay?

Â So you basically have the cost of all the sets that you are selected or

Â all the fire stations that you are building if you want, okay?

Â And then you have two constraints, the first one, actually one constraints,

Â the one constraint that you have is that every one of the item has to be selected.

Â How do you do that?

Â Well, the sets they belong to, okay?

Â You have to make sure that for

Â every one the item there is at least one set that it belongs to which is selected.

Â So you basically make sure that the sum of of the variable xi

Â that cover that particular item is greater or equal to one.

Â An item can be, they can be covered by two different sets and that's fine, but it has

Â to be covered by at least one and that's what this constraints is expressing.

Â And of course you build the entire fire station on that so

Â this is a binary zero one variable, okay?

Â So that's basically the formulation there.

Â The input is a little bit more interesting.

Â The only thing that you would have is a essentially the number of items that

Â you need to cover and then the number of sets that can be used for covering them.

Â And the rest of the data of the instants are really related to the sets, okay?

Â They're going to specify the cost of every one of the set, and then for every one of

Â these set you will have a list of all the items that they cover, okay?

Â So essentially every one of these lines here may have different number of

Â elements because they represent for

Â every set what are the items that are covered by that set, okay?

Â So in a sense to summarize you have the number of items you have the number

Â of set, you have one line per set, you have the cost of the set, and

Â then the list of the items that are covered by that set, okay?

Â The output is very simple, once again, objective function,

Â whether it's subtimal or not and then which of these sets have been selected.

Â That's the decision variable, that's the values that we want to see, okay?

Â So it's a zero one variable for every one of these sets, okay?

Â This is an example of an instance, you see the number of items,

Â you see the number of sets, five and four, okay.

Â So you obviously have four lines since you have four items, okay?

Â The first one is telling you that this is the cost of 12, and

Â then that particular set is covering item zero and item two, okay?

Â And so you can see that item zero is only covered by that set, so we know for

Â sure that that particular set will have to be selected, okay?

Â This is an example of a solution okay?

Â So it's a cost of 24, it's not optimal, it's not prove optimal, okay?

Â So what you see there is that we select set 0, set 1,

Â we don't select set 2, but we select set 3, okay?

Â So that's essentially the output,

Â very simple output which sets are you selecting, okay?

Â So as I said, the key point about this assignment, it's not a real assignment,

Â it's something which is open source, you can share your code, okay?

Â So we give you some code, some simple greedy solver, some constraint programming

Â software, you can look at that code, and you can get inspired by it, okay?

Â It also shows you how you can code an external tool, okay?

Â So go and look at this, okay?

Â So this will give you a sense of how these kinds of software are organized.

Â And it can give you some inspiration when you actually build your own, okay?

Â So you start from something and

Â you can actually see how it works on this particular example, okay?

Â Now you can design your own code and then share it with some of your friends, okay?

Â So you can use GitHub for this optimization and

Â share your code with your colleagues.

Â If you get a better local search,

Â a better constraint for running shoulder, a better mathematical for

Â running, a model accurate for solving this problem, just share it, okay?

Â You can do this and your colleagues you classmates can actually look at this and

Â get inspired by it, okay?

Â So once again, the goal here is to share information so that people can get

Â started, people who don't have experience in optimization can look at some code and

Â know how to actually build some more complex solvers, okay?

Â