1
00:00:00,520 --> 00:00:05,920
Okay guys, so this discrete optimization
and facility location assignment.

2
00:00:05,920 --> 00:00:06,160
Okay?

3
00:00:06,160 --> 00:00:08,950
So what I'm going to do is go over the
assignment, okay?

4
00:00:08,950 --> 00:00:12,030
And go over the details of the input
output.

5
00:00:12,030 --> 00:00:12,280
Okay?

6
00:00:12,280 --> 00:00:14,900
So this is a very intuitive assignment in
the sense, so

7
00:00:14,900 --> 00:00:17,490
what you have is a bunch of customers, so
this is

8
00:00:17,490 --> 00:00:20,000
the black dots that you see on the cree,
the screen,

9
00:00:20,000 --> 00:00:22,630
and what, so, and this is data, this is
given to you.

10
00:00:22,630 --> 00:00:23,070
Right?

11
00:00:23,070 --> 00:00:26,460
And so the second thing is that you get a
set of location that you see there.

12
00:00:26,460 --> 00:00:29,660
These are location for the facilities, and
your goal

13
00:00:29,660 --> 00:00:32,680
is to actually find out where you build
these facilities.

14
00:00:32,680 --> 00:00:32,940
Okay?

15
00:00:32,940 --> 00:00:35,650
And there are two cost that will come into
play.

16
00:00:35,650 --> 00:00:39,180
Every time you open a facility, it will
cost you a fixed cost.

17
00:00:39,180 --> 00:00:41,960
And then obviously, there will be also the
cost of

18
00:00:41,960 --> 00:00:45,470
delivering goods from that facilities to
the various customers, okay?

19
00:00:45,470 --> 00:00:47,490
And that's the variable cost, which
depends

20
00:00:47,490 --> 00:00:49,480
on how far the customer is located.

21
00:00:49,480 --> 00:00:50,180
Okay?

22
00:00:50,180 --> 00:00:53,280
And so in a sense, you have this tension
between the fixed cost, if

23
00:00:53,280 --> 00:00:57,380
there would be no fixed cost, you would
open many of these warehouses, okay?

24
00:00:57,380 --> 00:01:00,800
And this, you know, and the variable cost,
the, the distribution

25
00:01:00,800 --> 00:01:05,390
cost of actually shipping the good to the
particular customers, okay?

26
00:01:05,390 --> 00:01:10,354
Now, every one of these facilities will
also have a particular capacity and

27
00:01:10,354 --> 00:01:15,030
that will tell you how many of these
customers it can actually serve, okay?

28
00:01:15,030 --> 00:01:17,442
So basically tension between the fixed and

29
00:01:17,442 --> 00:01:20,122
the variable cost, and also tension,
because

30
00:01:20,122 --> 00:01:24,668
every one of these facilities will have a,
will have a fixed capacity, okay?

31
00:01:24,668 --> 00:01:27,860
A fixed number of customers that it can
serve.

32
00:01:27,860 --> 00:01:28,470
Okay?

33
00:01:28,470 --> 00:01:29,444
So this is a solution, okay?

34
00:01:29,444 --> 00:01:31,756
We open two of these facilities, and you

35
00:01:31,756 --> 00:01:34,955
see the customers are located to these two
facilities.

36
00:01:34,955 --> 00:01:36,130
Okay?

37
00:01:36,130 --> 00:01:37,070
So that's the goal.

38
00:01:37,070 --> 00:01:38,990
Of course we want to do that for thousands

39
00:01:38,990 --> 00:01:42,890
and thousands of customers and hundreds
and hundreds of facilities.

40
00:01:42,890 --> 00:01:43,940
Okay?

41
00:01:43,940 --> 00:01:47,380
So this is a description of the problem,
okay, I'm going to go over it.

42
00:01:47,380 --> 00:01:49,030
It's a terrible model, okay?

43
00:01:49,030 --> 00:01:50,630
There are actually very few [UNKNOWN] who
can

44
00:01:50,630 --> 00:01:53,930
actually express this model, as I'm
stating it here.

45
00:01:53,930 --> 00:01:57,140
And the reason I'm doing this is because I
don't want to influence you

46
00:01:57,140 --> 00:02:01,320
on the kind of formulations that you will
want to use for solving this problem.

47
00:02:01,320 --> 00:02:01,950
Okay?

48
00:02:01,950 --> 00:02:04,660
So we'll have n facilities and m
customers.

49
00:02:04,660 --> 00:02:05,290
Okay?

50
00:02:05,290 --> 00:02:08,220
So every customers will have a demand dc.

51
00:02:08,220 --> 00:02:08,510
Okay?

52
00:02:08,510 --> 00:02:09,570
For customer c.

53
00:02:09,570 --> 00:02:10,080
Okay?

54
00:02:10,080 --> 00:02:12,720
That's how much good the customer c wants

55
00:02:12,720 --> 00:02:15,450
to get delivered to, to, to his facility,
okay?

56
00:02:15,450 --> 00:02:18,960
To his, you know, ware, you know, to, to
his, its location.

57
00:02:18,960 --> 00:02:22,380
And then you will have for every facility
where you can actually build a warehouse.

58
00:02:22,380 --> 00:02:23,010
Okay?

59
00:02:23,010 --> 00:02:25,680
For every site where you can build a
facility in a sense.

60
00:02:25,680 --> 00:02:25,870
Okay?

61
00:02:25,870 --> 00:02:28,740
So you have a cost, that's the cost of the
building the facility.

62
00:02:28,740 --> 00:02:29,260
Okay?

63
00:02:29,260 --> 00:02:31,090
And then you have a capacity which is the,

64
00:02:31,090 --> 00:02:34,080
how many customers that capa, that
facility can actually serve.

65
00:02:34,080 --> 00:02:34,630
Okay?

66
00:02:34,630 --> 00:02:38,470
So this is sf and then cap, capf, okay,
that you see over there.

67
00:02:38,470 --> 00:02:39,180
Okay?

68
00:02:39,180 --> 00:02:40,910
Then there will be a cost, you know, for

69
00:02:40,910 --> 00:02:44,110
transporting goods from the facility to
the customer, okay?

70
00:02:44,110 --> 00:02:46,140
And we're going to use this thing here to
actually

71
00:02:46,140 --> 00:02:49,350
model that cost, so this is dist(f,c),
which tells

72
00:02:49,350 --> 00:02:51,640
you the distance between the, the distance
and also

73
00:02:51,640 --> 00:02:54,900
the cost, between the facility and the
customer c, okay?

74
00:02:54,900 --> 00:02:57,628
And then, essentially the only decision
variables

75
00:02:57,628 --> 00:02:59,364
in the model that I'm showing you

76
00:02:59,364 --> 00:03:03,574
here is going to be the set of customers
which are allocated to facility f, okay?

77
00:03:03,574 --> 00:03:08,173
So af is going to be the set of customers
that are allocated to facility f.

78
00:03:08,173 --> 00:03:09,878
Once you have that, once you have all

79
00:03:09,878 --> 00:03:12,518
these decision variables, essentially you
have all you

80
00:03:12,518 --> 00:03:14,278
need to actually compute a cost and you

81
00:03:14,278 --> 00:03:17,840
know, things, and, and verify the
constraints are satisfied.

82
00:03:17,840 --> 00:03:18,550
Okay?

83
00:03:18,550 --> 00:03:22,120
So the, the, so I'm going to go over the,
over the mathematical formulation.

84
00:03:22,120 --> 00:03:24,130
Once again, keep in mind that, you know,
this

85
00:03:24,130 --> 00:03:26,980
is probably not something that you want to
use, okay?

86
00:03:26,980 --> 00:03:28,980
So what we are trying to do is minimize

87
00:03:28,980 --> 00:03:31,930
for every one of the facilities two
things, okay?

88
00:03:31,930 --> 00:03:34,760
The fixed cost and then the variable cost,
okay?

89
00:03:34,760 --> 00:03:36,128
The fixed cost is what?

90
00:03:36,128 --> 00:03:38,520
Well, you pay it, you pay the fixed cost,
so you build

91
00:03:38,520 --> 00:03:42,780
a facility if at least one customer is
assigned to the facility, okay?

92
00:03:42,780 --> 00:03:45,790
So if you know that the set of customers

93
00:03:45,790 --> 00:03:50,030
assigned to that particular facility is
not empty, okay?

94
00:03:50,030 --> 00:03:52,090
So that particular expression here is
going to

95
00:03:52,090 --> 00:03:54,550
be true, okay, you multiply that by

96
00:03:54,550 --> 00:03:58,720
the, by the cost of the fixed cost and you
get essentially the fixed cost.

97
00:03:58,720 --> 00:04:02,910
If no customer is allocated to that
facility, this expression is 0, okay?

98
00:04:02,910 --> 00:04:03,940
So that's the fixed cost.

99
00:04:03,940 --> 00:04:06,460
When you actually assign something to a
facility, you

100
00:04:06,460 --> 00:04:08,880
have to open it and you pay the fixed
cost.

101
00:04:08,880 --> 00:04:11,040
And then the second part is essentially
looking at all

102
00:04:11,040 --> 00:04:14,720
the customers which are allocated to that
particular facility and

103
00:04:14,720 --> 00:04:18,060
you compute a distance between that
customer and the particular,

104
00:04:18,060 --> 00:04:21,480
and the particular facility and you get
the variable cost.

105
00:04:21,480 --> 00:04:23,070
Okay, so that's the objective function.

106
00:04:23,070 --> 00:04:24,350
Two part, once again.

107
00:04:24,350 --> 00:04:26,640
The fixed cost and the variable cost.

108
00:04:26,640 --> 00:04:27,990
And then you have the two constraints.

109
00:04:27,990 --> 00:04:31,720
The first one is making sure that no
capacity constraints are violated.

110
00:04:31,720 --> 00:04:36,080
For every one of the facility, you make
sure that all the customers

111
00:04:36,080 --> 00:04:38,850
which are allocated to that popular
facility

112
00:04:38,850 --> 00:04:41,660
ever demands which doesn't exceed the
capacity.

113
00:04:41,660 --> 00:04:43,500
So you take all the customer associated
with

114
00:04:43,500 --> 00:04:46,000
the facility, you sum the demand of all
these

115
00:04:46,000 --> 00:04:48,220
customers, and you make sure that this is
small

116
00:04:48,220 --> 00:04:51,340
or equal to the capacity of that facility,
okay?

117
00:04:51,340 --> 00:04:52,670
That's the first constraint.

118
00:04:52,670 --> 00:04:54,340
The second constraint is obvious.

119
00:04:54,340 --> 00:04:57,190
You want to serve every one of your
customer, okay?

120
00:04:57,190 --> 00:05:00,840
So you make sure that for a particular
customer, if you look at all the

121
00:05:00,840 --> 00:05:03,600
facilities, at least one of them has the

122
00:05:03,600 --> 00:05:06,860
customer as one of its served customer,
okay?

123
00:05:06,860 --> 00:05:08,800
So that's what this constraint is doing,
okay?

124
00:05:08,800 --> 00:05:12,210
Once again, you know, don't implement that
mode, it's terrible, okay?

125
00:05:12,210 --> 00:05:17,180
But this is a mathematical expression,
precise expression of the problem, okay?

126
00:05:17,180 --> 00:05:19,290
Now let me go over the input output, okay?

127
00:05:19,290 --> 00:05:21,890
So this is the input that we are giving
you, okay?

128
00:05:21,890 --> 00:05:24,210
It is pretty simple in this problem, okay?

129
00:05:24,210 --> 00:05:26,900
So you have the number of facilities, the
number of customers, okay?

130
00:05:26,900 --> 00:05:30,250
So that's the first two numbers that
you're going to get, okay?

131
00:05:30,250 --> 00:05:32,930
And then essentially afterwards you get
all the information about

132
00:05:32,930 --> 00:05:36,590
the facilities, and then all the
information about the customers, okay?

133
00:05:36,590 --> 00:05:38,530
For the facilities, what do you get?

134
00:05:38,530 --> 00:05:39,990
Well you get the fixed cost, you get

135
00:05:39,990 --> 00:05:42,710
the capacity, and then you get the
location, okay?

136
00:05:42,710 --> 00:05:47,050
The geographic location, which is, you
know, a point in Euclidean space here.

137
00:05:47,050 --> 00:05:47,700
Okay?

138
00:05:47,700 --> 00:05:48,810
So that's what you get.

139
00:05:48,810 --> 00:05:50,870
And you get that, obviously, for, you
know, all the

140
00:05:50,870 --> 00:05:54,400
particular facilities that you have, and
they are n of them.

141
00:05:54,400 --> 00:05:56,210
And then afterwards, you'd have the same,

142
00:05:56,210 --> 00:05:58,440
well, roughly the same information for the
customers,

143
00:05:58,440 --> 00:06:02,530
what you get for them is essentially the
demand that they have in terms of goods.

144
00:06:02,530 --> 00:06:05,600
And then the location once again or where
they are in the plane.

145
00:06:05,600 --> 00:06:06,330
Okay?

146
00:06:06,330 --> 00:06:07,810
And so this is essentially the input.

147
00:06:07,810 --> 00:06:09,240
So the input is very simple, right?

148
00:06:09,240 --> 00:06:11,800
The capacity and the fixed costs for every
one

149
00:06:11,800 --> 00:06:15,440
of the l, for the facilities including
their location.

150
00:06:15,440 --> 00:06:17,420
And then for the customers, the same
thing.

151
00:06:17,420 --> 00:06:19,670
You have the demand in terms of the goods.

152
00:06:19,670 --> 00:06:20,350
Okay?

153
00:06:20,350 --> 00:06:23,170
And then you have the locations of the
various customers.

154
00:06:23,170 --> 00:06:23,430
Okay?

155
00:06:23,430 --> 00:06:24,540
So that's our input.

156
00:06:24,540 --> 00:06:28,530
The output is what you see there, so we
want something very, very simple.

157
00:06:28,530 --> 00:06:31,780
We want the objective function and whether
it's optimal or not, okay?

158
00:06:31,780 --> 00:06:33,320
Many of these problems here, you will be

159
00:06:33,320 --> 00:06:35,640
able to prove optimality, so this is
important.

160
00:06:35,640 --> 00:06:38,180
Not all of them, probably, but almost all
of them.

161
00:06:38,180 --> 00:06:42,680
And then, what you see there is basically
the list of the customer, the, the list

162
00:06:42,680 --> 00:06:45,600
of the cust, way the customers, which
facility

163
00:06:45,600 --> 00:06:47,280
are assigned to every one of the
customers.

164
00:06:47,280 --> 00:06:49,370
So for every one of the customers who want

165
00:06:49,370 --> 00:06:52,120
to know which facility they are assigned
to, okay?

166
00:06:52,120 --> 00:06:53,170
So that's the output, okay?

167
00:06:53,170 --> 00:06:56,690
For every one of the customer, which is
the facility that the customer is

168
00:06:56,690 --> 00:07:01,290
assigned to, and we can deduce obviously
from that which facilities are being used.

169
00:07:01,290 --> 00:07:01,960
Okay?

170
00:07:01,960 --> 00:07:05,210
So this is an example of a particular
instance, okay?

171
00:07:05,210 --> 00:07:08,660
So you have three facilities for
customers, okay?

172
00:07:08,660 --> 00:07:10,360
Really baby instance here.

173
00:07:10,360 --> 00:07:12,640
You see the various numbers for the fixed
costs,

174
00:07:12,640 --> 00:07:15,930
for the capacity, and the locations of
these two things.

175
00:07:15,930 --> 00:07:20,870
And for the customers that the same thing,
you see the demand, 50, 50, 75, 75.

176
00:07:20,870 --> 00:07:23,130
And you see the location in the plane,
okay?

177
00:07:23,130 --> 00:07:27,230
In this particular case, this is the out,
this is one of the output, okay?

178
00:07:27,230 --> 00:07:28,520
One possible output.

179
00:07:28,520 --> 00:07:31,210
You see the value of the objective
function there

180
00:07:31,210 --> 00:07:38,830
250, you know, 2550.013, okay, and then
it's not optimal.

181
00:07:38,830 --> 00:07:43,800
And then you see a, you know you see where
this particular customers are located.

182
00:07:43,800 --> 00:07:47,520
You see that customer 0 and customer 1 are
located to facility 1.

183
00:07:47,520 --> 00:07:49,260
Customer 2 to facility 0.

184
00:07:49,260 --> 00:07:50,700
Customer 3 to facility 2.

185
00:07:50,700 --> 00:07:53,950
So the, the, essentially the assignments
that you have

186
00:07:53,950 --> 00:07:55,880
here is the one that you see over there.

187
00:07:55,880 --> 00:08:00,090
Which basically tells you that the
facility 0 is serving customer 2.

188
00:08:00,090 --> 00:08:03,100
Facility 1 is serving customer 0 and 1.

189
00:08:03,100 --> 00:08:07,380
And facility 2 is serving customer 3,
that's the last thing that you see there.

190
00:08:07,380 --> 00:08:08,250
Okay?

191
00:08:08,250 --> 00:08:08,990
So this is

192
00:08:11,020 --> 00:08:13,650
this is a description of input/output,
okay?

193
00:08:13,650 --> 00:08:15,770
Now we talked a lot about warehouse
location

194
00:08:15,770 --> 00:08:18,110
in the lecture, look at this as one, okay?

195
00:08:18,110 --> 00:08:20,730
They are different formulation, okay?

196
00:08:20,730 --> 00:08:22,870
Whatever you do, there will be different
way of

197
00:08:22,870 --> 00:08:25,830
modeling this problem, whatever the
approach that you take, okay?

198
00:08:25,830 --> 00:08:28,020
And different formulation will have
different efficiency.

199
00:08:28,020 --> 00:08:31,950
So this is an interesting problem in
actually the modeling the various point.

200
00:08:31,950 --> 00:08:33,720
Okay, so you have to think about what is

201
00:08:33,720 --> 00:08:36,450
a good formulation in every kind of the
models, right?

202
00:08:36,450 --> 00:08:40,050
So what is a good formulation for
mathematical programming system?

203
00:08:40,050 --> 00:08:42,310
Okay, remember, you know, we talked about
that.

204
00:08:42,310 --> 00:08:44,930
What is a good formulation for a local
search algorithm?

205
00:08:44,930 --> 00:08:47,040
Okay, so the two main approach that I
would

206
00:08:47,040 --> 00:08:51,470
suggest looking at are local search and
mathematical programming, okay?

207
00:08:51,470 --> 00:08:54,730
And if you do local search, one of the
critical thing in this particular

208
00:08:54,730 --> 00:08:56,890
assignment is going to be the speed at

209
00:08:56,890 --> 00:08:58,780
which you can actually explore the
neighborhood.

210
00:08:58,780 --> 00:08:59,360
Okay?

211
00:08:59,360 --> 00:09:00,960
So the faster you can explore this

212
00:09:00,960 --> 00:09:04,300
neighborhood, the more configuration you
can explore, okay?

213
00:09:04,300 --> 00:09:07,260
And in this particular example, there is a
beautiful data

214
00:09:07,260 --> 00:09:10,630
structure that you can use to speed this
up tremendously, okay?

215
00:09:10,630 --> 00:09:12,390
So think about that, okay?

216
00:09:12,390 --> 00:09:13,230
So good luck.

217
00:09:13,230 --> 00:09:13,810
Okay?

218
00:09:13,810 --> 00:09:16,950
So this is an amazing assignment, very
interesting assignment, okay?

219
00:09:16,950 --> 00:09:21,210
It's sufficiently simple, such that you
can understand it completely, but it's

220
00:09:21,210 --> 00:09:23,890
also challenging, and various approaches
with

221
00:09:23,890 --> 00:09:25,350
give you different, you know, trade-offs.

222
00:09:25,350 --> 00:09:27,310
So it's a very interesting assignment,
okay?

223
00:09:27,310 --> 00:09:28,650
Have fun, good luck.

224
00:09:28,650 --> 00:09:31,630
And so, you know, we'll see how, how well
you do,

225
00:09:31,630 --> 00:09:33,680
and we'll just get that in some of the
mailbox later on.

226
00:09:33,680 --> 00:09:34,270
Okay?

227
00:09:34,270 --> 00:09:34,680
Bye, guys.

228
00:09:34,680 --> 00:09:35,090
Thank you.