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?