1
00:00:00,410 --> 00:00:02,070
Okay guys, so this is the set

2
00:00:02,070 --> 00:00:04,180
covering assignments, which is not really
assignment,

3
00:00:04,180 --> 00:00:08,490
and so this is a novelty in this in this
session, and the key

4
00:00:08,490 --> 00:00:12,120
idea here, what we are trying to do is
have an assignment, a kind

5
00:00:12,120 --> 00:00:16,520
of a fake assignment where people can
submit their solutions and can share code.

6
00:00:16,520 --> 00:00:17,130
Okay?

7
00:00:17,130 --> 00:00:21,610
So, you can share code, you can share id's
but not code in the other assignments.

8
00:00:21,610 --> 00:00:24,220
But here, what we wanted to do is make
sure that you guys

9
00:00:24,220 --> 00:00:28,710
can actually share code, And show code on
a particular assignment said that

10
00:00:28,710 --> 00:00:31,780
people can say, oh, this is really how you
do a local search,

11
00:00:31,780 --> 00:00:34,950
oh, this is how you can do constraint
programming solver and so on.

12
00:00:34,950 --> 00:00:37,300
Okay, sometimes, you know, it's like in

13
00:00:37,300 --> 00:00:39,460
programming, looking at the code of
somebody else

14
00:00:39,460 --> 00:00:41,650
can actually help you Thinking about you

15
00:00:41,650 --> 00:00:44,540
know how you can actually implement
something yourself.

16
00:00:44,540 --> 00:00:46,240
And this is what we are trying to achieve
here.

17
00:00:46,240 --> 00:00:46,770
Okay?

18
00:00:46,770 --> 00:00:48,820
So I'm going to describe the set covering

19
00:00:48,820 --> 00:00:50,990
assignment and then going to talk about
some

20
00:00:50,990 --> 00:00:54,790
of the ways you can share that later on
in, in, in this video.

21
00:00:54,790 --> 00:00:55,430
Okay?

22
00:00:55,430 --> 00:00:56,980
Now set covering itself is a

23
00:00:56,980 --> 00:00:59,180
very interesting problem that pops up
everywhere.

24
00:00:59,180 --> 00:00:59,440
Okay?

25
00:00:59,440 --> 00:01:02,630
I'm going to use one real life example
here, But there are many, many

26
00:01:02,630 --> 00:01:05,730
other example, and this actually is a
problem that pop ups in a

27
00:01:05,730 --> 00:01:09,870
lot of other, you know, actually a real
application either as, on its

28
00:01:09,870 --> 00:01:15,280
own, but generally as a sub, you know,
sub-part of more complex algorithm, okay?

29
00:01:15,280 --> 00:01:19,660
So, so this is an example using fire
stations that have to cover a,

30
00:01:19,660 --> 00:01:24,220
a region, so what you see here Is a, is a
big geographic region, okay?

31
00:01:24,220 --> 00:01:26,550
And every one of the big dot there, the
black dot,

32
00:01:26,550 --> 00:01:29,780
is a location where you can set up a fire
station.

33
00:01:29,780 --> 00:01:31,950
And the key idea is that you have to cover
all the small

34
00:01:31,950 --> 00:01:34,980
region, they are numbered like zero, one,
and And so on and so forth.

35
00:01:34,980 --> 00:01:38,000
You have to cover 80% of these things in
seven minutes.

36
00:01:38,000 --> 00:01:38,780
Okay?

37
00:01:38,780 --> 00:01:43,070
And so once you get, you know, that's
requirement for emergency services.

38
00:01:43,070 --> 00:01:45,700
And so what you want to do is to select a
subset of them so

39
00:01:45,700 --> 00:01:47,840
that you, you know, basically cover the

40
00:01:47,840 --> 00:01:51,780
entire region, you know, at the minimum
cost.

41
00:01:51,780 --> 00:01:52,000
Okay?

42
00:01:52,000 --> 00:01:53,930
This is a, for instance, a popular
solution.

43
00:01:53,930 --> 00:01:57,840
So you see here, this particular fire
station is covering this

44
00:01:57,840 --> 00:02:02,840
part of the entire global region, and
these sub-regions over there, okay?

45
00:02:02,840 --> 00:02:04,160
And so on and so forth, okay?

46
00:02:04,160 --> 00:02:07,460
And so in this particular case, you have
six selected fire

47
00:02:07,460 --> 00:02:12,430
stations that basically satisfy the legal
requirements of the entire region, okay?

48
00:02:12,430 --> 00:02:17,550
And you try to do that, you know, in, Of
course, the minimal cost, okay?

49
00:02:17,550 --> 00:02:19,130
Covering, you know, satisfying the legal

50
00:02:19,130 --> 00:02:21,010
requirement, getting to the people, it's,
you

51
00:02:21,010 --> 00:02:25,330
know, in the time that is specified by
law, but also the minimum cost.

52
00:02:25,330 --> 00:02:29,810
So this is how we can model this thing
more formally, okay?

53
00:02:29,810 --> 00:02:33,400
So in a sense, All the regions that you
have seen in the particular, you

54
00:02:33,400 --> 00:02:36,420
know, in the example that I have shown,
I'm going to be called item, okay?

55
00:02:36,420 --> 00:02:39,100
So this, so we are basically given a
number of item

56
00:02:39,100 --> 00:02:42,800
and items, and we were left to cover these
items, okay?

57
00:02:42,800 --> 00:02:43,750
How do we cover them?

58
00:02:43,750 --> 00:02:44,580
We cover them by.

59
00:02:44,580 --> 00:02:46,660
Set, that's why this is called set cover.

60
00:02:46,660 --> 00:02:47,290
Okay?

61
00:02:47,290 --> 00:02:49,810
So in this particular case the set of fire
station.

62
00:02:49,810 --> 00:02:50,070
Okay?

63
00:02:50,070 --> 00:02:53,630
And essentially a fire station is defined,
or a set in,

64
00:02:53,630 --> 00:02:56,690
you know, in the more abstract version, is
defined by two things.

65
00:02:56,690 --> 00:03:01,060
Its cost, that's the cost it takes you to
actually build it Okay?

66
00:03:01,060 --> 00:03:03,030
And then the items that it cover.

67
00:03:03,030 --> 00:03:06,480
You know, when you have a fire station you
will know which of the regions

68
00:03:06,480 --> 00:03:08,680
you will cover in seven minutes, 80% of

69
00:03:08,680 --> 00:03:10,960
which you can cover in seven minutes,
okay?

70
00:03:10,960 --> 00:03:12,940
And so, you know, when we look at the up
front

71
00:03:12,940 --> 00:03:15,960
version of the problem, for every one of
these sets we know

72
00:03:15,960 --> 00:03:21,170
which item they cover, we get this SI,
okay, this set SI which tells

73
00:03:21,170 --> 00:03:26,710
you that Set i is actually covering that
many items.

74
00:03:26,710 --> 00:03:26,980
Okay?

75
00:03:26,980 --> 00:03:29,250
And then, so one, so this is the data.

76
00:03:29,250 --> 00:03:32,330
These four things there that I'm listing
are, is the data.

77
00:03:32,330 --> 00:03:34,630
And then the only decision variable that
you need in this

78
00:03:34,630 --> 00:03:37,980
particular problem is find out if you
select set i or not.

79
00:03:37,980 --> 00:03:38,498
Okay?

80
00:03:38,498 --> 00:03:42,650
So XI is one, if you select set I, think
fire station, I'm

81
00:03:42,650 --> 00:03:45,050
selecting fire station I, and zero

82
00:03:45,050 --> 00:03:47,060
otherwise, you don't select fire station
I.

83
00:03:47,060 --> 00:03:47,780
Okay?

84
00:03:47,780 --> 00:03:49,770
And so now once you have these decision
variable

85
00:03:49,770 --> 00:03:53,530
and these data, you can formulate the
problem mathematically.

86
00:03:53,530 --> 00:03:53,810
Okay?

87
00:03:53,810 --> 00:03:57,770
And what you see there is that what you
want to do is minimize the linear sum

88
00:03:57,770 --> 00:04:02,910
again, and this is the sum of the cost of
opening every one of the fire station.

89
00:04:02,910 --> 00:04:07,940
So this is ci which is the cost of set i
times x i which is zero if

90
00:04:07,940 --> 00:04:09,810
you don't open, you know, if you don't
select

91
00:04:09,810 --> 00:04:11,690
that set on 1, if you select that set.

92
00:04:11,690 --> 00:04:14,350
Okay, So you basically have the cost of
all the, the sets

93
00:04:14,350 --> 00:04:17,210
that you are selected, or all the fire
stations that you are building.

94
00:04:17,210 --> 00:04:18,440
If you want, okay?

95
00:04:18,440 --> 00:04:19,860
And then you have two constraints.

96
00:04:19,860 --> 00:04:21,750
The first, well, actually one constraints.

97
00:04:21,750 --> 00:04:24,490
The one constraint that you have is that
every one

98
00:04:24,490 --> 00:04:27,440
of the, every one of the item has to be
selected.

99
00:04:27,440 --> 00:04:28,510
How do you do that?

100
00:04:28,510 --> 00:04:30,940
Well, you know the sets they belong to,
okay?

101
00:04:30,940 --> 00:04:33,930
So, you have to make sure that for every
one of the item

102
00:04:33,930 --> 00:04:38,160
There is at least one set that it belongs
to, which is selected.

103
00:04:38,160 --> 00:04:41,150
So you basically make sure that the sum of
the variable

104
00:04:41,150 --> 00:04:46,530
x i that cover that particular item, is
greater equal to 1.

105
00:04:46,530 --> 00:04:48,310
You know, an item can be, you know, it can

106
00:04:48,310 --> 00:04:51,660
be covered by two two different sets, and
that's fine.

107
00:04:51,660 --> 00:04:54,310
But it, it has to be covered by at least
one.

108
00:04:54,310 --> 00:04:56,410
And that's what this constraint is
expressing.

109
00:04:56,410 --> 00:04:59,180
And of course, you know, you build the
entire fire station

110
00:04:59,180 --> 00:05:02,400
on nought so this is a binary 0, 1
variable, okay?

111
00:05:02,400 --> 00:05:04,590
So that's basically the formulation there.

112
00:05:04,590 --> 00:05:06,900
The input is a little bit more
interesting.

113
00:05:06,900 --> 00:05:09,650
The only thing that you will have is
essentially

114
00:05:09,650 --> 00:05:12,010
the number of items that you need to
cover.

115
00:05:12,010 --> 00:05:15,150
And then the number of sets that can be
used for covering them.

116
00:05:15,150 --> 00:05:19,260
And the rest of the data of the instance
are really related to the sets, okay?

117
00:05:19,260 --> 00:05:23,350
They're going to specify the cost of every
one of the set, and then for every one

118
00:05:23,350 --> 00:05:27,060
of these sets, you will have a list of all
of the items that they cover, okay?

119
00:05:27,060 --> 00:05:29,160
So essentially every one of these lines
here

120
00:05:29,160 --> 00:05:31,890
may have different number of elements,
because essent,

121
00:05:31,890 --> 00:05:34,680
that, they represent for every set what
are

122
00:05:34,680 --> 00:05:36,790
the items that are covered by that set?

123
00:05:36,790 --> 00:05:39,910
Okay, so in a sense, to summarize, you
have the number

124
00:05:39,910 --> 00:05:43,100
of items, you have the number of, of sets,
you have one

125
00:05:43,100 --> 00:05:45,570
line per set, you have the cost of the
set, and

126
00:05:45,570 --> 00:05:48,540
then the list of the items that are
covered by that set.

127
00:05:48,540 --> 00:05:49,170
Okay?

128
00:05:49,170 --> 00:05:50,390
The output is very simple.

129
00:05:50,390 --> 00:05:53,570
Once again, objective function, whether
it's optimal or not,

130
00:05:53,570 --> 00:05:55,720
and then which of these sets are being
selected?

131
00:05:55,720 --> 00:05:58,490
That's the decision variable, that's the
values that we want to see.

132
00:05:58,490 --> 00:05:59,010
Okay.

133
00:05:59,010 --> 00:06:03,640
So it's a 0, 1 variable for every one of
these of these, of these sets.

134
00:06:03,640 --> 00:06:07,230
Okay, this is an example Of an instance,
you know, you see the

135
00:06:07,230 --> 00:06:10,900
number of items, you see the number of
sets, five and four, okay.

136
00:06:10,900 --> 00:06:14,680
So you obviously have four lines, since
you have four items, okay.

137
00:06:14,680 --> 00:06:16,800
The first one is telling you that this is
a cost of

138
00:06:16,800 --> 00:06:21,360
12, and then that particular set is
covering item zero and item two.

139
00:06:21,360 --> 00:06:22,360
Okay?

140
00:06:22,360 --> 00:06:26,100
And so you, you can see that item 0 is
only covered by that set,

141
00:06:26,100 --> 00:06:30,050
so we know for sure that that particular
set will have to be selected, okay?

142
00:06:30,050 --> 00:06:32,580
This is an example of a solution, okay?

143
00:06:32,580 --> 00:06:33,490
So it's a cost of 24.

144
00:06:33,490 --> 00:06:35,300
It's not optimal.

145
00:06:35,300 --> 00:06:37,700
Use, it's not prove the optimal, okay?

146
00:06:37,700 --> 00:06:41,090
So what you see there is that we select,
set zero,

147
00:06:41,090 --> 00:06:44,250
set one, we don't select set two but we
select set three.

148
00:06:44,250 --> 00:06:44,940
Okay?

149
00:06:44,940 --> 00:06:46,600
So that's essentially the output very

150
00:06:46,600 --> 00:06:49,170
simple output which sets are you
selecting.

151
00:06:49,170 --> 00:06:49,890
Okay?

152
00:06:49,890 --> 00:06:53,300
So, as I said, the key point about these
assignments is not a

153
00:06:53,300 --> 00:06:55,190
real assignment, it's something which is
open

154
00:06:55,190 --> 00:06:57,190
source, you can share your code, okay?

155
00:06:57,190 --> 00:06:58,900
So we give you some code, some

156
00:06:58,900 --> 00:07:01,490
simple greedy solver, some constraint
programming solver,

157
00:07:01,490 --> 00:07:04,810
you can look at that code, and you can get
inspired by it, okay?

158
00:07:04,810 --> 00:07:08,780
It's all, it also show you how you can
code an external tool, okay?

159
00:07:08,780 --> 00:07:10,220
So go and look at this, okay?

160
00:07:10,220 --> 00:07:13,480
So this will give you a sense Of what you

161
00:07:13,480 --> 00:07:17,710
can, what, how these, these kinds of
servers are organized.

162
00:07:17,710 --> 00:07:20,940
And it can give you some inspiration when
you actually build your own.

163
00:07:20,940 --> 00:07:23,460
Okay, so you start from something and you
can

164
00:07:23,460 --> 00:07:26,830
actually see how it works on this
particular example, okay.

165
00:07:26,830 --> 00:07:28,850
Now you can, you can design your own code

166
00:07:28,850 --> 00:07:31,450
and then share it with some of your
friends, okay.

167
00:07:31,450 --> 00:07:34,200
So you can use github for discrete
optimization

168
00:07:34,200 --> 00:07:36,890
and share your code with your, with your
colleagues.

169
00:07:36,890 --> 00:07:39,940
If you get a better looking search, a
better constraint programming server.

170
00:07:39,940 --> 00:07:42,350
A better mathematical programming, you
know model

171
00:07:42,350 --> 00:07:44,980
for actually solving this problem, just
share it.

172
00:07:44,980 --> 00:07:45,540
Okay?

173
00:07:45,540 --> 00:07:48,190
You can do this, and you, your, your
colleagues, your, your,

174
00:07:48,190 --> 00:07:52,160
your classmates can actually, look at this
and get inspired by it.

175
00:07:52,160 --> 00:07:52,700
Okay?

176
00:07:52,700 --> 00:07:54,730
So once again, the goal here is to share

177
00:07:54,730 --> 00:07:57,400
information such that people can get
started, people who don't

178
00:07:57,400 --> 00:08:00,800
have experience in, in optimization can
look at some code

179
00:08:00,800 --> 00:08:04,640
and know how to actually build Some more
complex solvers.

180
00:08:04,640 --> 00:08:06,120
Okay?

181
00:08:06,120 --> 00:08:08,340
Don't list results, we don't care about
the

182
00:08:08,340 --> 00:08:10,810
results here, this is really about sharing
the code.

183
00:08:10,810 --> 00:08:11,390
Okay?

184
00:08:11,390 --> 00:08:16,260
So, you know, having a lookup table, you
know, is the most boring algorithm ever.

185
00:08:16,260 --> 00:08:17,060
Okay?

186
00:08:17,060 --> 00:08:20,130
Now you can submit any solution as well,
inside, you know,

187
00:08:20,130 --> 00:08:24,070
the, the, on all the instants in the
dataset, that's also good.

188
00:08:24,070 --> 00:08:26,920
Okay, so you, you different algorithm can
be compared.

189
00:08:26,920 --> 00:08:29,090
And then people can say, oh, this
algorithm is really cute I

190
00:08:29,090 --> 00:08:31,690
want to see what it does, what is the code
doing now, right.

191
00:08:31,690 --> 00:08:32,400
So you can do that.

192
00:08:33,840 --> 00:08:35,240
And you can view, you know, the, their

193
00:08:35,240 --> 00:08:38,660
leaders on, as well, like in any other
assignment.

194
00:08:39,780 --> 00:08:43,080
So I found this is an assignment that you
can share with other people, where

195
00:08:43,080 --> 00:08:44,830
you can discuss the various techniques,
where you

196
00:08:44,830 --> 00:08:46,970
can go into the detail of the code.

197
00:08:46,970 --> 00:08:50,270
So this is something that, you know, was,
was recommended to

198
00:08:50,270 --> 00:08:52,530
us last year, and I think it can make a
difference

199
00:08:52,530 --> 00:08:55,370
for people who are really starting in this
[UNKNOWN] optimization and

200
00:08:55,370 --> 00:08:57,770
want to look at various code before they
start their own.

201
00:08:57,770 --> 00:08:58,300
Okay?

202
00:08:58,300 --> 00:08:59,050
Have fun, guys.

203
00:08:59,050 --> 00:09:00,400
This is a very simple assignment.

204
00:09:00,400 --> 00:09:03,200
No pressure at all, so you can see code,
you can

205
00:09:03,200 --> 00:09:07,510
share code, so this is an interesting
novelty in this particular session.

206
00:09:07,510 --> 00:09:08,020
Okay.

207
00:09:08,020 --> 00:09:08,680
Have fun, guys.

208
00:09:08,680 --> 00:09:09,040
See you.