1
00:00:00,190 --> 00:00:03,060
Okay guys, welcome back, discrete
optimization.

2
00:00:03,060 --> 00:00:06,420
But still the knapsack problem, but today
we're going to talk about modeling.

3
00:00:06,420 --> 00:00:09,050
Okay, so whatever I'm going to say today
is going to

4
00:00:09,050 --> 00:00:11,900
seem very, very simple, but there are some
deep

5
00:00:11,900 --> 00:00:14,810
truths and deep knowledge in what I'm
going to talk

6
00:00:14,810 --> 00:00:17,680
about, but they will seem to be completely
natural.

7
00:00:17,680 --> 00:00:20,120
But we'll come back to them later on, and
you'll see why

8
00:00:20,120 --> 00:00:23,430
some of the things that I'm going to say
today are actually important, okay?

9
00:00:23,430 --> 00:00:25,380
So the first thing we're going to do is
talk

10
00:00:25,380 --> 00:00:29,370
about how to formalize an optimization
task as a mathematical model.

11
00:00:29,370 --> 00:00:32,570
This is the key, okay, so this is the key
for actually solving these problems.

12
00:00:32,570 --> 00:00:35,170
You have to be able to model them
mathematically

13
00:00:35,170 --> 00:00:36,908
why, you know, let me give me an example.

14
00:00:36,908 --> 00:00:39,380
You talk with industry, you talk to
people, they start

15
00:00:39,380 --> 00:00:42,660
describing your problem, and you think you
understand it, okay?

16
00:00:42,660 --> 00:00:44,650
And then you come back with a beautiful
solution and

17
00:00:44,650 --> 00:00:48,350
tell you you know you can't do this,
that's the constraints.

18
00:00:48,350 --> 00:00:50,790
But they didn't express it the right way
or they forgot

19
00:00:50,790 --> 00:00:51,770
to tell you.

20
00:00:51,770 --> 00:00:53,000
And essentially you come up with this

21
00:00:53,000 --> 00:00:55,670
beautiful algorithm that really doesn't
apply in practice.

22
00:00:55,670 --> 00:00:58,220
So what you have to do first is always
find

23
00:00:58,220 --> 00:01:01,060
a description of the problems that
everybody can agree upon.

24
00:01:01,060 --> 00:01:02,440
Okay?
This is the first step.

25
00:01:02,440 --> 00:01:04,160
What is it that we are trying to solve?

26
00:01:04,160 --> 00:01:05,850
And that's what I'm going to talk about
today.

27
00:01:05,850 --> 00:01:08,930
Okay, so lets do that for the knapsack
which is very simple, but that's

28
00:01:08,930 --> 00:01:12,210
going to give you an idea on how we do
that for a very complex problem.

29
00:01:12,210 --> 00:01:15,850
So, we start with a set of item, capital
I, that's all the items

30
00:01:15,850 --> 00:01:17,870
that we can actually put in the knapsack
and

31
00:01:17,870 --> 00:01:20,770
then for every one of these item, I, okay.

32
00:01:20,770 --> 00:01:22,880
We will have two piece of information,
okay?

33
00:01:22,880 --> 00:01:25,640
That's what we've seen in the greedy
algorithm so far, right.

34
00:01:25,640 --> 00:01:29,240
The weight of the item, okay, and the
weight of the item, and the

35
00:01:29,240 --> 00:01:32,230
volume of the item, that's the two things
that we know for the items.

36
00:01:32,230 --> 00:01:34,140
And then the only piece of information
that

37
00:01:34,140 --> 00:01:36,970
you need, is also the capacity of your
knapsack.

38
00:01:36,970 --> 00:01:38,670
This is the input of your problem.

39
00:01:38,670 --> 00:01:41,350
That's what you need to actually start
formalizing it.

40
00:01:41,350 --> 00:01:44,290
And now the problem is really finding a

41
00:01:44,290 --> 00:01:47,420
subset of these items, Okay, which has
maximum value.

42
00:01:47,420 --> 00:01:49,050
You want to maximize the value of the

43
00:01:49,050 --> 00:01:51,590
items that you are picking up, but you
don't

44
00:01:51,590 --> 00:01:53,280
want the weight of the items that you are

45
00:01:53,280 --> 00:01:55,490
picking up to exceed the capacity of the
knapsack.

46
00:01:55,490 --> 00:01:55,940
Okay?

47
00:01:55,940 --> 00:01:58,130
This is still informal and we're going to
start

48
00:01:58,130 --> 00:02:00,360
formalizing this in the next couple of
slide.

49
00:02:00,360 --> 00:02:02,920
But this is the start of formalizing the
problem.

50
00:02:02,920 --> 00:02:03,500
Okay?

51
00:02:03,500 --> 00:02:06,700
We know the input, okay?
So, how do we model this?

52
00:02:06,700 --> 00:02:10,040
The first thing you have to do every time
you are trying to

53
00:02:10,040 --> 00:02:14,722
model an optimization problem is to find
out what the decision variables are.

54
00:02:14,722 --> 00:02:16,150
And you're going to say, oh, but what is
this thing.

55
00:02:16,150 --> 00:02:19,360
Essentially this is something that's
going to capture

56
00:02:19,360 --> 00:02:21,840
the real decisions you are interested in,
okay?

57
00:02:21,840 --> 00:02:24,310
In practice for instance, in this
particular case

58
00:02:24,310 --> 00:02:26,290
for a particular item what do you want

59
00:02:26,290 --> 00:02:29,095
to know, you want to know if you select
that item or if you don't select it.

60
00:02:29,095 --> 00:02:32,230
lf you put it in the knapsack or if you
don't put it in the knapsack.

61
00:02:32,230 --> 00:02:35,840
That's what you want to, to decide, and

62
00:02:35,840 --> 00:02:38,790
that's the decision variables will
correspond to that.

63
00:02:38,790 --> 00:02:40,670
Okay, so once you have these decision

64
00:02:40,670 --> 00:02:43,080
variables, you can start doing things with
them.

65
00:02:43,080 --> 00:02:45,150
And one of the really important things
that you

66
00:02:45,150 --> 00:02:49,000
have to do is basically model the problem
constraints.

67
00:02:49,000 --> 00:02:50,990
And these problem constraints are going to
tell you

68
00:02:50,990 --> 00:02:52,730
what you can do and what you cannot do.

69
00:02:52,730 --> 00:02:54,440
What is a feasible solution?

70
00:02:54,440 --> 00:02:57,680
A solution that people will tell you, yes,
yes that's the solution,

71
00:02:57,680 --> 00:03:00,866
not something no, you forgot something,
It's basically capturing

72
00:03:00,866 --> 00:03:03,229
what you can do, what is the feasible
solution.

73
00:03:03,229 --> 00:03:03,473
Okay?

74
00:03:03,473 --> 00:03:06,950
It's basically define the, the set of
things that people will accept as

75
00:03:06,950 --> 00:03:10,028
a solution, and then the last thing of
[UNKNOWN] you have to define

76
00:03:10,028 --> 00:03:13,790
your objective function, what are you
trying to maximize or minimize, and in

77
00:03:13,790 --> 00:03:18,290
this particular case the knapsack is going
to maximizing the value of your items.

78
00:03:18,290 --> 00:03:22,388
Okay, the objective functions is defining
the quality of your solution.

79
00:03:22,388 --> 00:03:22,978
The constraints

80
00:03:22,978 --> 00:03:25,990
are defining what is a solution and the
decision variables are

81
00:03:25,990 --> 00:03:29,620
telling you what to decide, what you will
decide upon, okay?

82
00:03:29,620 --> 00:03:31,360
And so essentially, the result of these

83
00:03:31,360 --> 00:03:33,650
three things together is an optimization
model.

84
00:03:33,650 --> 00:03:37,655
It doesn't tell you what to solve or what,
how to solve the problems.

85
00:03:37,655 --> 00:03:40,780
It tells you, it tells you what the
problem is.

86
00:03:40,780 --> 00:03:43,680
Okay, now a very important point here, is
that there are many,

87
00:03:43,680 --> 00:03:46,150
many ways of actually modeling a

88
00:03:46,150 --> 00:03:48,050
particular optimization problems, and this
is

89
00:03:48,050 --> 00:03:49,740
part of the beauty, okay?

90
00:03:49,740 --> 00:03:53,330
So in a sense I'm basically telling you
its specify what we want to solve but

91
00:03:53,330 --> 00:03:55,770
implicitly you are already making some
choices, and

92
00:03:55,770 --> 00:03:58,110
it can restrict how you will solve the
problem.

93
00:03:58,110 --> 00:03:59,910
So you have to be very careful when you do
this.

94
00:03:59,910 --> 00:04:02,460
There may be many formulations, they may
be translated

95
00:04:02,460 --> 00:04:05,120
from one to the other, but essentially
they will

96
00:04:05,120 --> 00:04:07,160
capture the same problem in a different
fashion, and

97
00:04:07,160 --> 00:04:09,070
they may influence the technique that you
will use.

98
00:04:09,070 --> 00:04:11,340
So you have to keep an open mind when you
model the problem.

99
00:04:11,340 --> 00:04:13,310
Okay, so, we'll come back to that many
times,

100
00:04:13,310 --> 00:04:15,930
present different models of different
problems

101
00:04:15,930 --> 00:04:18,530
for, you know, for practical application.

102
00:04:18,530 --> 00:04:20,570
Now, the, in the knapsack problems, the

103
00:04:20,570 --> 00:04:22,820
decision variables, here are the decision
variables.

104
00:04:22,820 --> 00:04:25,580
For every one of the items, you will have
a variable xi.

105
00:04:25,580 --> 00:04:29,720
For item i, you know, variable xi will
denote whether you select the

106
00:04:29,720 --> 00:04:33,560
item or not, whether you put the item
inside the knapsack or not, okay?

107
00:04:33,560 --> 00:04:36,690
So xi will be equal to one if you select
the item.

108
00:04:36,690 --> 00:04:38,510
It will be equal to zero otherwise.

109
00:04:38,510 --> 00:04:39,110
Okay?

110
00:04:39,110 --> 00:04:43,190
So, so the goal of the optimization model
will be to find the values of all

111
00:04:43,190 --> 00:04:45,338
these decision variables, whether you
assign a one

112
00:04:45,338 --> 00:04:47,150
or a zero to every one of them.

113
00:04:47,150 --> 00:04:49,880
That's going to be the goal, but these
decision variables when you

114
00:04:49,880 --> 00:04:52,222
see the value of them you know what to do,
okay?

115
00:04:52,222 --> 00:04:54,965
Every one which is every item, decision
variable which is a

116
00:04:54,965 --> 00:04:57,970
one you know that you want to put them in
the knapsack.

117
00:04:57,970 --> 00:05:00,620
The ones which are zero, you don't.
Okay?

118
00:05:00,620 --> 00:05:03,660
So the problem constraints have to be
expressed now in terms of

119
00:05:03,660 --> 00:05:04,900
these decision variables.

120
00:05:04,900 --> 00:05:08,110
And this is one of, this is the only, you

121
00:05:08,110 --> 00:05:11,280
know, feasibility constraints that you
have in this particular problem.

122
00:05:11,280 --> 00:05:12,350
What does it say?

123
00:05:12,350 --> 00:05:15,120
It basically makes sure that the item that
you select, they will

124
00:05:15,120 --> 00:05:19,530
have an xi equal to one, don't exceed the
capacity of the knapsack.

125
00:05:19,530 --> 00:05:23,720
So basically what you do is you sum this
product, okay, which is a constant,

126
00:05:23,720 --> 00:05:25,460
which is the weight of the variables and

127
00:05:25,460 --> 00:05:27,710
then whether you select the variable or
not.

128
00:05:27,710 --> 00:05:29,600
And that summation

129
00:05:29,600 --> 00:05:32,300
here has to be smaller than the capacity
of the knapsack.

130
00:05:32,300 --> 00:05:34,120
And you know, when you don't select the
item, you

131
00:05:34,120 --> 00:05:36,860
know this, you know this product is not
contribute anything.

132
00:05:36,860 --> 00:05:41,530
When you select it, it will contribute the
weight So essentially this make sure

133
00:05:41,530 --> 00:05:46,170
that you never exceed the capacity of the
knapsack with the item that you select.

134
00:05:46,170 --> 00:05:46,775
Okay.

135
00:05:46,775 --> 00:05:50,140
Now essentially this constraint defined
all the feasibility constraints.

136
00:05:50,140 --> 00:05:52,050
It basically makes sure that the item that
you

137
00:05:52,050 --> 00:05:54,700
selected will not exceed the capacity of
the knapsack.

138
00:05:54,700 --> 00:05:56,110
And then the last thing that you have to
do

139
00:05:56,110 --> 00:05:59,190
is express your objective function and we
use a singular

140
00:05:59,190 --> 00:06:02,620
you know, expression, we multiply every
one of these decision

141
00:06:02,620 --> 00:06:05,880
variables by the value of the item, the
corresponding item.

142
00:06:05,880 --> 00:06:09,830
We've summed them, and we have the full
value of the knapsack, okay?

143
00:06:09,830 --> 00:06:11,110
At this point, we have the decision

144
00:06:11,110 --> 00:06:14,410
variables, the feasibility constraints,
the objective function.

145
00:06:14,410 --> 00:06:15,700
We have a complete model.

146
00:06:15,700 --> 00:06:18,140
This is the complete model of the
knapsack.

147
00:06:18,140 --> 00:06:19,880
You see the value

148
00:06:19,880 --> 00:06:21,900
here that you are trying to maximize.

149
00:06:21,900 --> 00:06:24,740
And you see the capacity constraints over
here and

150
00:06:24,740 --> 00:06:26,930
then you know that every one of the
decision variables.

151
00:06:26,930 --> 00:06:28,620
It took a value of zero or one.

152
00:06:28,620 --> 00:06:31,400
You take the item or you don't.
Okay?

153
00:06:31,400 --> 00:06:34,490
And so this constitutes an optimization
model.

154
00:06:34,490 --> 00:06:37,310
Everything here is formalizing what you
want to do.

155
00:06:37,310 --> 00:06:39,760
You know exactly what's going to be a
solution and

156
00:06:39,760 --> 00:06:42,220
you also know the value of every one of
these solutions.

157
00:06:42,220 --> 00:06:45,020
What remains to be done, is what?
Is finding these,

158
00:06:45,020 --> 00:06:46,990
this, the value for these decision
variables.

159
00:06:48,030 --> 00:06:49,840
Now, now you can look at these problems
and

160
00:06:49,840 --> 00:06:53,930
you can start, but wow, how many solutions
are there?

161
00:06:53,930 --> 00:06:56,480
And in this particular case what you can
do is enumerate

162
00:06:56,480 --> 00:07:00,470
all the possible configuration for the
values of the decision variables.

163
00:07:00,470 --> 00:07:01,080
Okay?

164
00:07:01,080 --> 00:07:03,600
So you can decide for instance, that you
select no item,

165
00:07:03,600 --> 00:07:06,560
you know, that's not, not going to give
you very much value.

166
00:07:06,560 --> 00:07:10,090
But this is one of the things that you can
consider, or some configuration where you

167
00:07:10,090 --> 00:07:11,830
see like one item or a com, or the

168
00:07:11,830 --> 00:07:14,790
combination with two item, three items and
so on, okay?

169
00:07:14,790 --> 00:07:16,780
This is essentially your search space.

170
00:07:16,780 --> 00:07:18,150
When you look at the decision variables

171
00:07:18,150 --> 00:07:20,040
the value that you can take, the
contingent

172
00:07:20,040 --> 00:07:22,110
product of these guys are going to give
you

173
00:07:22,110 --> 00:07:24,885
all the configurations that you have to
consider.

174
00:07:24,885 --> 00:07:27,100
Okay?
Not all of them are going to be feasible.

175
00:07:27,100 --> 00:07:29,840
Some of them are going to violate the
capacity constraints, and

176
00:07:29,840 --> 00:07:32,370
that's going to be the feasible part of
your search base.

177
00:07:32,370 --> 00:07:32,970
Okay?

178
00:07:32,970 --> 00:07:34,470
So this is going to give you the search
base.

179
00:07:34,470 --> 00:07:35,750
This is the feasibility

180
00:07:35,750 --> 00:07:38,760
region in a sense, okay.
And how many are there?

181
00:07:38,760 --> 00:07:42,000
Well essentially in this particle or case
the number of configuration,

182
00:07:42,000 --> 00:07:45,030
if you ignore the ones that are violating
the capacity constraints.

183
00:07:45,030 --> 00:07:47,795
It's going to be two to the number of item
and that's a huge

184
00:07:47,795 --> 00:07:53,020
numbers if the items are actually, if
there is a large number of items, okay?

185
00:07:53,020 --> 00:07:55,470
So, so let me give you an idea of

186
00:07:55,470 --> 00:07:59,570
how many and how fast this, this value is
increasing.

187
00:07:59,570 --> 00:08:01,200
Assume that it takes one millisecond

188
00:08:01,200 --> 00:08:04,990
to test a configuration, to test if a
configuration is feasible.

189
00:08:04,990 --> 00:08:08,930
And we try to enumerate all of them, test,
and then we want to select the best one.

190
00:08:08,930 --> 00:08:12,260
We just, you know apply a brute force
algorithm to do this.

191
00:08:12,260 --> 00:08:14,400
If it takes one millisecond to test any

192
00:08:14,400 --> 00:08:17,880
configuration, and you have 50 item, okay,
it

193
00:08:17,880 --> 00:08:20,420
will take that number of centuries like,
you

194
00:08:20,420 --> 00:08:22,860
know, more than a wow, that's a huge
number.

195
00:08:22,860 --> 00:08:26,720
It's more like a billion centuries to
actually solve this right?

196
00:08:26,720 --> 00:08:30,040
So, this is huge okay, so you can't solve
the problem this way,

197
00:08:30,040 --> 00:08:34,800
and what this class is about is exploring
these configuration in a smaller way.

198
00:08:34,800 --> 00:08:35,420
Okay?

199
00:08:35,420 --> 00:08:38,450
And still finding optimal solution.
Okay?

200
00:08:38,450 --> 00:08:40,920
Or in a sense finding a very high quality
solution that

201
00:08:40,920 --> 00:08:44,200
you can say is very, very close to the
optimal solution.

202
00:08:44,200 --> 00:08:44,690
Okay?

203
00:08:44,690 --> 00:08:48,485
So next time we're going to start looking
at how you can actually do that.

204
00:08:48,485 --> 00:08:52,050
How you can find optimal solution to the
knapsack problems

205
00:08:52,050 --> 00:08:55,098
in reasonable time.
Okay, see you next time, thank you.

206
00:08:55,098 --> 00:08:56,340
[BLANK_AUDIO]