Okay guys, so this is the set
covering assignments, which is not really
assignment,
and so this is a novelty in this in this
session, and the key
idea here, what we are trying to do is
have an assignment, a kind
of a fake assignment where people can
submit their solutions and can share code.
Okay?
So, you can share code, you can share id's
but not code in the other assignments.
But here, what we wanted to do is make
sure that you guys
can actually share code, And show code on
a particular assignment said that
people can say, oh, this is really how you
do a local search,
oh, this is how you can do constraint
programming solver and so on.
Okay, sometimes, you know, it's like in
programming, looking at the code of
somebody else
can actually help you Thinking about you
know 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 going to talk about
some
of the ways you can share that later on
in, in, 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 example, and this actually is a
problem that pop ups in a
lot of other, you know, actually a real
application either as, on its
own, but generally as a sub, you know,
sub-part of more complex algorithm, okay?
So, so this is an example using fire
stations that have to cover a,
a region, so what you see here Is a, is a
big geographic region, okay?
And every one 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, they are numbered like zero, one,
and And so on and so forth.
You have to cover 80% of these things in
seven minutes.
Okay?
And so once you get, you know, that's
requirement for emergency services.
And so what you want to do is to select a
subset of them so
that you, you know, basically cover the
entire region, you know, at the minimum
cost.
Okay?
This is a, for instance, a popular
solution.
So you see here, this particular fire
station is covering this
part of the entire global region, and
these sub-regions over there, okay?
And so on and so forth, okay?
And so in this particular case, you have
six selected fire
stations that basically satisfy the legal
requirements of the entire region, okay?
And you try to do that, you know, in, Of
course, the minimal cost, okay?
Covering, you know, satisfying the legal
requirement, getting to the people, it's,
you
know, 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 particular, you
know, in the example that I have shown,
I'm going to be called item, okay?
So this, so we are basically given a
number of item
and items, and we were left to cover these
items, okay?
How do we cover them?
We cover them by.
Set, that's why this is called set cover.
Okay?
So in this particular case the set of fire
station.
Okay?
And essentially a fire station is defined,
or a set in,
you know, in the more abstract version, is
defined by two things.
Its 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, you know, when we look at the up
front
version of the problem, for every one of
these sets we know
which item they cover, we get this SI,
okay, this set SI which tells
you that Set i is actually covering that
many items.
Okay?
And then, so one, so this is the data.
These four things there that I'm listing
are, 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 is one, if you select set I, think
fire station, I'm
selecting fire station I, and zero
otherwise, you don't select fire station
I.
Okay?
And so now once you have these decision
variable
and these data, you can formulate the
problem mathematically.
Okay?
And what you see there is that what you
want to do is minimize the linear sum
again, and this is the sum of the cost of
opening every one of the fire station.
So this is ci which is the cost of set i
times x i which is zero if
you don't open, you know, if you don't
select
that set on 1, if you select that set.
Okay, So you basically have the cost of
all the, 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, well, actually one constraints.
The one constraint that you have is that
every one
of the, every one of the item has to be
selected.
How do you do that?
Well, you know the sets they belong to,
okay?
So, you have to make sure that for every
one of the item
There is at least one set that it belongs
to, which is selected.
So you basically make sure that the sum of
the variable
x i that cover that particular item, is
greater equal to 1.
You know, an item can be, you know, it can
be covered by two two different sets, and
that's fine.
But it, it has to be covered by at least
one.
And that's what this constraint is
expressing.
And of course, you know, you build the
entire fire station
on nought so this is a binary 0, 1
variable, okay?
So that's basically the formulation there.
The input is a little bit more
interesting.
The only thing that you will have is
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 instance
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 sets, you will have a list of all
of the items that they cover, okay?
So essentially every one of these lines
here
may have different number of elements,
because essent,
that, 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, of sets,
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 optimal or not,
and then which of these sets are being
selected?
That's the decision variable, that's the
values that we want to see.
Okay.
So it's a 0, 1 variable for every one of
these of these, of these sets.
Okay, this is an example Of an instance,
you know, 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
a cost of
12, and then that particular set is
covering item zero and item two.
Okay?
And so you, you can see that item 0 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.
Use, it's not prove the optimal, okay?
So what you see there is that we select,
set zero,
set one, we don't select set two but we
select set three.
Okay?
So that's essentially the output very
simple output which sets are you
selecting.
Okay?
So, as I said, the key point about these
assignments is 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 solver,
you can look at that code, and you can get
inspired by it, okay?
It's all, it also show you how you can
code an external tool, okay?
So go and look at this, okay?
So this will give you a sense Of what you
can, what, how these, these kinds of
servers 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, you can design your own code
and then share it with some of your
friends, okay.
So you can use github for discrete
optimization
and share your code with your, with your
colleagues.
If you get a better looking search, a
better constraint programming server.
A better mathematical programming, you
know model
for actually solving this problem, just
share it.
Okay?
You can do this, and you, your, your
colleagues, your, your,
your classmates can actually, look at this
and get inspired by it.
Okay?
So once again, the goal here is to share
information such that people can get
started, people who don't
have experience in, in optimization can
look at some code
and know how to actually build Some more
complex solvers.
Okay?
Don't list results, we don't care about
the
results here, this is really about sharing
the code.
Okay?
So, you know, having a lookup table, you
know, is the most boring algorithm ever.
Okay?
Now you can submit any solution as well,
inside, you know,
the, the, on all the instants in the
dataset, that's also good.
Okay, so you, you different algorithm can
be compared.
And then people can say, oh, this
algorithm is really cute I
want to see what it does, what is the code
doing now, right.
So you can do that.
And you can view, you know, the, their
leaders on, as well, like in any other
assignment.
So I found this is an assignment that you
can share with other people, where
you can discuss the various techniques,
where you
can go into the detail of the code.
So this is something that, you know, was,
was recommended to
us last year, and I think it can make a
difference
for people who are really starting in this
[UNKNOWN] optimization and
want to look at various code before they
start their own.
Okay?
Have fun, guys.
This is a very simple assignment.
No pressure at all, so you can see code,
you can
share code, so this is an interesting
novelty in this particular session.
Okay.
Have fun, guys.
See you.