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?