1
00:00:00,490 --> 00:00:02,090
Welcome back.

2
00:00:02,090 --> 00:00:05,780
This is discrete optimization again, the
knapsack problem.

3
00:00:05,780 --> 00:00:09,430
And as you can see, I have a new hat.
This is the branch and bound hat.

4
00:00:09,430 --> 00:00:11,870
Something which is really useful, and
going to be used

5
00:00:11,870 --> 00:00:14,990
over and over again in this particular
class, okay.

6
00:00:14,990 --> 00:00:18,750
We're going to introduce branch and bond,
and also the value of relaxation, okay?

7
00:00:18,750 --> 00:00:21,410
Two very important concept in one lecture,
but

8
00:00:21,410 --> 00:00:23,350
still the lecture will be short, you'll
see.

9
00:00:23,350 --> 00:00:25,800
Okay so, this is the one dimensional
knapsack,

10
00:00:25,800 --> 00:00:28,390
we have seen it many times, you're
probably start getting fed

11
00:00:28,390 --> 00:00:32,180
up with this particular knapsack, but you
going to see something beautiful today.

12
00:00:32,180 --> 00:00:35,850
Okay, so, you know, remember when we talk
about binary programming,

13
00:00:35,850 --> 00:00:38,850
we talk about exhaustive search, okay, and
in a sense we

14
00:00:38,850 --> 00:00:41,210
have this, you know, decision variables on
top and what we're

15
00:00:41,210 --> 00:00:44,280
trying to find out is the values that are
possible for this.

16
00:00:44,280 --> 00:00:48,020
This, decision vibrance and what I've
shown you during the

17
00:00:48,020 --> 00:00:51,520
dynamic programming lecture is that they
exponentially many of these guys

18
00:00:51,520 --> 00:00:53,740
in terms of the number of items.
Okay?

19
00:00:53,740 --> 00:00:57,860
But how do we, this is a way to actually
build this configuration okay.

20
00:00:57,860 --> 00:01:00,510
You take the first item, and you have two
decisions.

21
00:01:00,510 --> 00:01:01,010
Okay.

22
00:01:01,010 --> 00:01:03,810
Whether you take the item or whether you
don't take the item, okay?

23
00:01:03,810 --> 00:01:07,430
And now you have these two possibilities,
and for these two possibilities.

24
00:01:07,430 --> 00:01:08,970
You're going to look at the second item
and you can

25
00:01:08,970 --> 00:01:11,320
decide to take the second item or not to
take it.

26
00:01:11,320 --> 00:01:14,600
And once again, what you get now are four
different configurations.

27
00:01:14,600 --> 00:01:16,550
And now, you can do the same with the
third

28
00:01:16,550 --> 00:01:20,260
item, okay, and you get the final eight
configuration, okay.

29
00:01:20,260 --> 00:01:21,920
And every one of the configuration will

30
00:01:21,920 --> 00:01:24,140
tell you whether you choose, you know,
item

31
00:01:24,140 --> 00:01:27,160
one or not, whether you choose item two or
not, or item three or not.

32
00:01:27,160 --> 00:01:30,180
And obviously I had four item we would
have, you know, 16

33
00:01:30,180 --> 00:01:33,910
of them, 5 item, 32, and this would grow,
grow, grow very large.

34
00:01:33,910 --> 00:01:37,500
What branch and body is about is looking
at this tree and trying

35
00:01:37,500 --> 00:01:41,680
to explore only a tiny part of it And
finding the optimum solution

36
00:01:41,680 --> 00:01:43,170
nevertheless, okay?

37
00:01:43,170 --> 00:01:46,310
So that's what we're going to do, and
we're going to show you how to do that.

38
00:01:46,310 --> 00:01:49,440
And the key idea is that the iterative two
steps, okay.

39
00:01:49,440 --> 00:01:52,060
Branching and bounding.
And branching is boring, right?

40
00:01:52,060 --> 00:01:54,370
It's like the exhaustive search, except
later on I will

41
00:01:54,370 --> 00:01:56,760
tell you that there are smart ways to do
this.

42
00:01:56,760 --> 00:01:58,730
But at this point it's completely boring.

43
00:01:58,730 --> 00:02:00,980
You know, it's like, okay, so I take an
item and whether I

44
00:02:00,980 --> 00:02:03,890
take the item or not, that's what
branching is going to be about, okay.

45
00:02:03,890 --> 00:02:06,810
It's like in the exhaustive search.
But then bounding.

46
00:02:06,810 --> 00:02:08,040
Bounding is very different.

47
00:02:08,040 --> 00:02:12,380
It's like finding an optimistic evaluation
Of what you can do, okay.

48
00:02:12,380 --> 00:02:15,370
So in optimization you have to be
optimistic, in life

49
00:02:15,370 --> 00:02:17,780
as well right, so we want you to be
optimistic.

50
00:02:17,780 --> 00:02:21,740
In fact, what is the best that I could
ever do, okay, if you are maximizing.

51
00:02:21,740 --> 00:02:25,300
Or if you are minimizing, how low can be
my cost, okay.

52
00:02:25,300 --> 00:02:28,030
So that's the kind of optimistic
evaluation

53
00:02:28,030 --> 00:02:30,820
that we need for actually for bounding,
okay.

54
00:02:30,820 --> 00:02:31,990
And I'm going to show

55
00:02:31,990 --> 00:02:33,530
you how we can get this.
Okay.

56
00:02:33,530 --> 00:02:35,210
So how do we find these things?

57
00:02:35,210 --> 00:02:38,270
So we are going to basically take the
problem and relax it.

58
00:02:38,270 --> 00:02:41,450
And so optimization Is the art of
relaxation.

59
00:02:41,450 --> 00:02:46,360
Okay, so image yourself in this [UNKNOWN],
and you are completely zen, and you find

60
00:02:46,360 --> 00:02:50,930
out the best way you can actually relax
these problems and make it easy to solve.

61
00:02:50,930 --> 00:02:51,530
Okay?

62
00:02:51,530 --> 00:02:55,420
And get and object, and get an optimistic
evaluation of this thing.

63
00:02:55,420 --> 00:02:57,020
Okay, so once again This is the

64
00:02:57,020 --> 00:02:59,640
knapsack, and you ask yourself,
[INAUDIBLE],

65
00:02:59,640 --> 00:03:01,670
okay, now, relax this [UNKNOWN], okay?

66
00:03:01,670 --> 00:03:03,960
And there are not that many things in this
notation, right?

67
00:03:03,960 --> 00:03:06,890
So, in this formulation.
And so, you may say, oh.

68
00:03:06,890 --> 00:03:09,110
with what I could relax is this
constraint, okay?

69
00:03:09,110 --> 00:03:12,370
We're going to relax the capacity
constraint, okay?

70
00:03:12,370 --> 00:03:15,110
And then, as soon as we do that, usually,

71
00:03:15,110 --> 00:03:17,509
we can get an optimistic evaluation of
this problem.

72
00:03:39,890 --> 00:03:41,210
evaluation, okay?

73
00:03:41,210 --> 00:03:42,720
So, what you going to see is that you're
going to see

74
00:03:42,720 --> 00:03:44,990
these node in the tree that I'm going to
build, okay?

75
00:03:44,990 --> 00:03:47,290
They have three entries, okay?

76
00:03:47,290 --> 00:03:50,490
They have the value of that I have
accumulated inside the knapsack.

77
00:03:50,490 --> 00:03:52,510
They have the space left in the knapsack.

78
00:03:52,510 --> 00:03:55,220
And then they have this optimistic
evaluation, okay?

79
00:03:55,220 --> 00:03:57,490
So initially I have accumulated no value.

80
00:03:57,490 --> 00:03:59,600
I have, you know, the full space in my
knapsack.

81
00:03:59,600 --> 00:04:01,140
10 in this particular case.

82
00:04:01,140 --> 00:04:05,490
And then I have this optimistic evaluation
which is oh, I can select everything okay,

83
00:04:05,490 --> 00:04:08,750
so in this particular case is 128.
And now I start doing things.

84
00:04:08,750 --> 00:04:08,960
Right?

85
00:04:08,960 --> 00:04:11,220
I'm selecting the first item, okay.

86
00:04:11,220 --> 00:04:14,090
As soon as I do that I computed the value
of the first item, 45.

87
00:04:14,090 --> 00:04:17,410
I take 5 units of space in the, in the
knapsack.

88
00:04:17,410 --> 00:04:20,100
And my, you know, optimistic evaluation is
still 128.

89
00:04:20,100 --> 00:04:23,820
You know, then I try to select item 2 but
as you can see

90
00:04:23,820 --> 00:04:27,600
item 2 is a size of 8 so I'm exceeding the
capacity of the knapsack.

91
00:04:27,600 --> 00:04:31,180
That's not a feasible solution, okay, so I
can't take item 2.

92
00:04:31,180 --> 00:04:35,410
And at that point my optimistic evaluation
is reduced to 80, okay?

93
00:04:35,410 --> 00:04:38,220
And I can decide to take item three or
not, okay?

94
00:04:38,220 --> 00:04:42,920
If I take item three, I get the value of
80, okay, this is one and three.

95
00:04:42,920 --> 00:04:45,640
And if I don't take it, I get a value of

96
00:04:45,640 --> 00:04:47,820
45, which is essentially completely
dominated

97
00:04:47,820 --> 00:04:49,360
by the previous solution I found.

98
00:04:49,360 --> 00:04:51,850
Okay, so I know that this is not an
optimal solution.

99
00:04:51,850 --> 00:04:52,320
Okay.

100
00:04:52,320 --> 00:04:54,230
Now I go back to the next part of the
tree.

101
00:04:54,230 --> 00:04:56,350
I decide not to select item 1 so

102
00:04:56,350 --> 00:04:58,770
my optimistic evaluation at this point is
83.

103
00:04:58,770 --> 00:05:02,710
It's still better than this guy, okay, 18,
the best solution that I've found.

104
00:05:02,710 --> 00:05:03,750
So I keep going.

105
00:05:03,750 --> 00:05:05,540
Okay.
I select item 2.

106
00:05:05,540 --> 00:05:07,820
If I select item 2 I'm still 83.

107
00:05:07,820 --> 00:05:10,030
Okay, then I decide if I select item 3 or

108
00:05:10,030 --> 00:05:13,180
not Okay, in the first case I get an
unfeasible solution.

109
00:05:13,180 --> 00:05:15,890
Otherwise I get the value 48, which is
also

110
00:05:15,890 --> 00:05:17,990
dominated by the best solutions that I
have found.

111
00:05:17,990 --> 00:05:20,960
So, you know, this is why I put this cross
over there.

112
00:05:20,960 --> 00:05:24,870
Otherwise if I decided not to take item
two, okay?

113
00:05:24,870 --> 00:05:27,770
So, what I get is a configuration there,
okay?

114
00:05:27,770 --> 00:05:31,730
Which is optimistic, whose optimistic
evaluation is 35, okay?

115
00:05:31,730 --> 00:05:34,030
Now that's terrible right?
So it's worse!

116
00:05:34,030 --> 00:05:36,280
That the best solutions that I have found
so far.

117
00:05:36,280 --> 00:05:40,960
So, I can decide without continuing
anything, now this is not valuable, okay?

118
00:05:40,960 --> 00:05:42,840
I don't have to actually branch on item 3.

119
00:05:42,840 --> 00:05:46,020
I already know that the best I could do is
worst than the

120
00:05:46,020 --> 00:05:49,472
best solution that I had.
And this is the key idea behind bounding.

121
00:05:49,472 --> 00:05:53,849
Once you have this optimistic evaluation,
if it's worse than the best solution you

122
00:05:53,849 --> 00:05:58,044
have found, you know that you don't have
to explore whatever is below the tree.

123
00:05:58,044 --> 00:06:00,954
Now this is an example which is terribly
bad, alright?

124
00:06:00,954 --> 00:06:04,278
Because my optimistic evaluation is so
optimistic that most of

125
00:06:04,278 --> 00:06:07,478
the time I'm going to basically explore
the entire tree, okay?

126
00:06:07,478 --> 00:06:10,952
But so you can see sometimes we get a
little bit of pruning, okay?

127
00:06:10,952 --> 00:06:13,688
But what we have to do is to find a better
relaxation

128
00:06:13,688 --> 00:06:18,000
so that We can prune a bigger part of this
tree, okay?

129
00:06:18,000 --> 00:06:21,740
So, look again at this knapsack example
and think, okay?

130
00:06:21,740 --> 00:06:24,130
What else can I relax?

131
00:06:24,130 --> 00:06:27,860
Okay, I let you think for about, ten
minutes I guess, okay?

132
00:06:27,860 --> 00:06:31,260
And then I'll tell you, okay?
Can we relax something else?

133
00:06:31,260 --> 00:06:33,600
And you're going to see a beautiful slide,
okay.

134
00:06:33,600 --> 00:06:36,030
So we are going to assume that

135
00:06:36,030 --> 00:06:41,660
instead of packing artifacts, we are
packing bars of Belgian chocolate, okay.

136
00:06:41,660 --> 00:06:43,770
Now this is completely different, right.

137
00:06:43,770 --> 00:06:46,550
So because now, you know, when you have
Belgian chocolate.

138
00:06:46,550 --> 00:06:47,770
Let me give you a picture, okay.

139
00:06:47,770 --> 00:06:51,040
So, because this is so beautiful I'm
already hungry here.

140
00:06:51,040 --> 00:06:53,060
Okay, so and, and here I can tell you that
Indian

141
00:06:53,060 --> 00:06:56,252
Jones loved Belgian chocolate, that's the
best chocolate in the world.

142
00:06:56,252 --> 00:06:57,125
By far, okay.

143
00:06:57,125 --> 00:07:01,240
So this is this bar of chocolates, okay.
Now what Indiana Jones can

144
00:07:01,240 --> 00:07:04,904
say, mm, oh i can't pile the whole thing
in my knapsack, but

145
00:07:04,904 --> 00:07:08,475
I can break it into piece and put it in my
knapsack, right.

146
00:07:08,475 --> 00:07:10,987
So this is completely different, right.

147
00:07:10,987 --> 00:07:13,005
It's not I take, or I don't take.

148
00:07:13,005 --> 00:07:17,860
I can take a piece of it, right.
And so now, assume that my old knapsack.

149
00:07:17,860 --> 00:07:22,380
Is built of artifacts that I can break.
Like you know, Belgian chocolate, okay?

150
00:07:22,380 --> 00:07:25,550
So then I get this beautiful [UNKNOWN],
right?

151
00:07:25,550 --> 00:07:26,270
So, the only thing

152
00:07:26,270 --> 00:07:29,880
that I did was for the decision variables.
They don't have to be zero one.

153
00:07:29,880 --> 00:07:33,132
I take it, or I don't take it, black and
white, ying and yang, right?

154
00:07:33,132 --> 00:07:35,775
Only, what I'm doing here is saying, ooh,
but I

155
00:07:35,775 --> 00:07:39,588
can take a fractional value of these
particular decision variables.

156
00:07:39,588 --> 00:07:44,189
I can take a quarter of it, or I can take
half of it, or something like this, right?

157
00:07:44,189 --> 00:07:48,640
And so I get this optimization problem
here, which is almost the same as before.

158
00:07:48,640 --> 00:07:51,721
Except that the value of the, of the
decision variables

159
00:07:51,721 --> 00:07:54,940
now can take any fraction between zero and
one.

160
00:07:54,940 --> 00:07:59,990
Okay, and now you can ask, oh, but, you
know, is that problem easy to solve?

161
00:07:59,990 --> 00:08:03,320
Okay, well actually this problem is called
a linear relaxation.

162
00:08:03,320 --> 00:08:06,400
You're going to see that in this class all
the time, okay.

163
00:08:06,400 --> 00:08:08,450
Especially when we start looking at, you

164
00:08:08,450 --> 00:08:11,592
know, mathematical programming, linear
programming, mixed integer programming.

165
00:08:11,592 --> 00:08:13,881
And so this is a very, very important
concept.

166
00:08:13,881 --> 00:08:17,065
So this says, a linear art, a linear
relaxation of the knapsack.

167
00:08:17,065 --> 00:08:20,938
And this has a very important properties
that in practice it's easy to compute.

168
00:08:20,938 --> 00:08:23,464
And I'm going to show a very easy way for
the knapsack.

169
00:08:23,464 --> 00:08:25,809
In practice it's a little bit more
complicated.

170
00:08:25,809 --> 00:08:27,755
We'll, we'll cover that as well, okay?

171
00:08:27,755 --> 00:08:30,047
So the only thing that the linear
relaxation is

172
00:08:30,047 --> 00:08:32,246
doing is take every value that To be a.

173
00:08:32,246 --> 00:08:34,375
A natural number, so an integer numbers.

174
00:08:34,375 --> 00:08:36,062
And relaxing them to a fraction.

175
00:08:36,062 --> 00:08:39,000
That's what the linear relaxation is
doing, is basically

176
00:08:39,000 --> 00:08:42,162
relaxing the integrality constraints that
you have in most of

177
00:08:42,162 --> 00:08:44,808
these models, okay?
So, now how can we solve this?

178
00:08:44,808 --> 00:08:47,236
I'm going to show you a very simple way to
do this.

179
00:08:47,236 --> 00:08:49,863
And this is going to you know, basically
be very close

180
00:08:49,863 --> 00:08:52,764
to some, some of the greediogories in that
we have seen.

181
00:08:52,764 --> 00:08:55,841
So we going to order the item By value per
kilos.

182
00:08:55,841 --> 00:08:56,336
Okay.

183
00:08:56,336 --> 00:09:02,112
So this is this WI you know, over you know
VI over WI ratio that I, that

184
00:09:02,112 --> 00:09:07,649
I've shown you before, okay.
So basically the item that is the largest

185
00:09:07,649 --> 00:09:10,227
value Okay, it is essentially the va, item

186
00:09:10,227 --> 00:09:12,647
that is the most valuable by kilo, and
when

187
00:09:12,647 --> 00:09:15,501
you look at chocolate that's, that's what
you want

188
00:09:15,501 --> 00:09:18,281
right, 'cos you can start breaking them up
okay?

189
00:09:18,281 --> 00:09:21,284
So essentially you alter the item by this
and what you

190
00:09:21,284 --> 00:09:24,585
have to do is basically select all the
item okay, until the

191
00:09:24,585 --> 00:09:28,841
capacity is, select all the items until
the capacity is exhausted, putting

192
00:09:28,841 --> 00:09:32,669
another item with, go over the capacity
and for this And once

193
00:09:32,669 --> 00:09:35,450
you have that you select the item and
select

194
00:09:35,450 --> 00:09:38,114
a fraction of it so you fill the knapsack.

195
00:09:38,114 --> 00:09:41,158
So in a sense you order these items in the
greedy

196
00:09:41,158 --> 00:09:44,770
algorithm you accumulate them if the next
one is going to

197
00:09:44,770 --> 00:09:47,885
go over capacity what you do is take a
fraction of

198
00:09:47,885 --> 00:09:52,353
it such that, that particular fraction is
going to fill the knapsack.

199
00:09:52,353 --> 00:09:57,387
And this is essentially an optimal
solution of this linear relaxation Okay.

200
00:09:57,387 --> 00:09:57,827
So look

201
00:09:57,827 --> 00:10:00,327
at this in this particular example, okay.

202
00:10:00,327 --> 00:10:05,127
So, you see the various, you know, you see
item one, item two, item three, okay.

203
00:10:05,127 --> 00:10:07,507
So the first item is 45 over 5, okay, and

204
00:10:07,507 --> 00:10:10,602
that gives you a value of 9 for that
particular item.

205
00:10:10,602 --> 00:10:14,457
The second one is 48 over 8, okay, and
that gives you a value of 6.

206
00:10:14,457 --> 00:10:15,932
And the third on is that?

207
00:10:15,932 --> 00:10:19,736
It's 35 over 3 and that gives you a value
of around You know 11.7.

208
00:10:19,736 --> 00:10:22,892
So the item number three is actually per,
y'know per

209
00:10:22,892 --> 00:10:26,525
kilo the most valuable item.
And then next one and next two.

210
00:10:26,525 --> 00:10:30,384
So what you would do here is you would
select item one, you would

211
00:10:30,384 --> 00:10:35,262
select item two okay, that gives you two
units for the capacity of the knapsack.

212
00:10:35,262 --> 00:10:38,462
and then you essentially take a quarter
because

213
00:10:38,462 --> 00:10:40,937
the weight of item two is eight okay.

214
00:10:40,937 --> 00:10:44,312
So you take a quarter of the value of this
guy going to

215
00:10:44,312 --> 00:10:47,937
give you umm which is going to give you a
quarter of that a

216
00:10:47,937 --> 00:10:50,312
value of 12 and the overall value of

217
00:10:50,312 --> 00:10:53,562
the linear estimation is going to be
ninety two.

218
00:10:53,562 --> 00:10:59,350
So ninety two in this particular case is
an optimistic evaluation Of the knapsack.

219
00:10:59,350 --> 00:11:03,250
You know for sure that you will never do
better than 92.

220
00:11:03,250 --> 00:11:04,200
Okay?

221
00:11:04,200 --> 00:11:07,000
So, but this is much better than the
relaxation that we had before,

222
00:11:07,000 --> 00:11:08,770
right, where we would basically sum

223
00:11:08,770 --> 00:11:11,130
everything, okay, and get 130 or
something.

224
00:11:11,130 --> 00:11:13,300
Right, so here, we have actually a value

225
00:11:13,300 --> 00:11:16,990
which is actually pretty good, okay, in
this particular case, okay.

226
00:11:16,990 --> 00:11:19,470
So, essentially the linear relaxation here
is giving

227
00:11:19,470 --> 00:11:24,160
you a very good value for the, for
bonding.

228
00:11:24,160 --> 00:11:26,480
particular knapsack problem.
Okay?

229
00:11:26,480 --> 00:11:27,810
Now why is this correct?

230
00:11:27,810 --> 00:11:32,850
This is a simple reformulation of, of the,
of this linear relaxation, okay?

231
00:11:32,850 --> 00:11:35,430
So you basically express, you introduce a

232
00:11:35,430 --> 00:11:38,310
new variable YI, which is basically the
product

233
00:11:38,310 --> 00:11:40,050
of VI and XI okay?

234
00:11:40,050 --> 00:11:44,090
And then you reformulate the knapsack and
what you see when you reformulate

235
00:11:44,090 --> 00:11:48,850
this knapsack is that all the item Have
the same, you know, value.

236
00:11:48,850 --> 00:11:50,590
Okay, they have a value 1, okay.

237
00:11:50,590 --> 00:11:54,110
But what is interesting when you
reformulate this problem is

238
00:11:54,110 --> 00:11:56,000
one, is not only the values are all the
same,

239
00:11:56,000 --> 00:12:00,190
but then this, this, this weight is
basically the density,

240
00:12:00,190 --> 00:12:02,690
the inverse of the density that I was
talking about, okay.

241
00:12:02,690 --> 00:12:03,450
The most

242
00:12:03,450 --> 00:12:06,780
valuable item have the least weight in
this reformulation.

243
00:12:06,780 --> 00:12:07,250
Okay.

244
00:12:07,250 --> 00:12:08,420
So how do you solve it?

245
00:12:08,420 --> 00:12:10,830
Well, it's like the greedy algorithm that
we have seen before.

246
00:12:10,830 --> 00:12:12,920
You take the smallest item first And when
you get

247
00:12:12,920 --> 00:12:15,530
stuck you take the fractional value of the
last one.

248
00:12:15,530 --> 00:12:19,200
That's why, in this particular case, the
linear relaxation is actually,

249
00:12:19,200 --> 00:12:22,600
is actually well, the algorithm that I've
given, that I've shown you.

250
00:12:22,600 --> 00:12:24,470
Select all the items until you get stuck
and

251
00:12:24,470 --> 00:12:27,280
then a fraction is actually computing the
linear relaxation.

252
00:12:27,280 --> 00:12:28,930
But of course,

253
00:12:28,930 --> 00:12:33,670
in practice, okay, the linear relaxation
is not a solution to a problem.

254
00:12:33,670 --> 00:12:34,260
Right?

255
00:12:34,260 --> 00:12:36,840
Because we have this mask and there is no
way we can break it,

256
00:12:36,840 --> 00:12:40,210
and anyway, even if you could break it you
would not want to break it.

257
00:12:40,210 --> 00:12:43,420
So essentially we can't take a fraction
part of this

258
00:12:43,420 --> 00:12:45,760
mask right, we can't decide to just take
the nose or

259
00:12:45,760 --> 00:12:48,800
whatever right, so we have to do, we have
to

260
00:12:48,800 --> 00:12:53,200
use this linear relaxation, ok inside the
branch and bound algorithm.

261
00:12:53,200 --> 00:12:54,430
And that's what we going to do, okay?

262
00:12:54,430 --> 00:12:57,830
So we start again at the root, okay?
There is nowhere else to start.

263
00:12:57,830 --> 00:13:01,790
But we know that the evaluation, the
optimistic evaluation here is 92, okay?

264
00:13:01,790 --> 00:13:03,440
Now we start, we go on the left, okay?

265
00:13:03,440 --> 00:13:06,560
So we take the items one.
Same evaluation, you know?

266
00:13:06,560 --> 00:13:09,240
Fewer space in the line.
Less space in the knapsack.

267
00:13:09,240 --> 00:13:11,502
We take item two, this is [INAUDIBLE]
feasible.

268
00:13:11,502 --> 00:13:11,777
You know?

269
00:13:11,777 --> 00:13:14,310
This is essentially the same as before.
We get this solution with [UNKNOWN].

270
00:13:14,310 --> 00:13:18,680
The other one with 45 is dominated.
But no.

271
00:13:18,680 --> 00:13:19,770
Now you're going to see something

272
00:13:19,770 --> 00:13:22,080
really, really cute, okay.

273
00:13:22,080 --> 00:13:26,990
So you go under, you, you go on the right,
okay, you don't select item 1.

274
00:13:26,990 --> 00:13:32,501
And what you see there now is that the
optimistic evaluation is 77.

275
00:13:34,530 --> 00:13:38,630
Oh, the 77 is worse than the best solution
that I have found so far, 80.

276
00:13:38,630 --> 00:13:42,480
So you know that the entire tree here, can
be thrown away.

277
00:13:42,480 --> 00:13:44,620
You don't have to look at it at all,
right.

278
00:13:44,620 --> 00:13:46,540
So you are at 77 here.

279
00:13:46,540 --> 00:13:48,590
And you know that anything which is below
you.

280
00:13:48,590 --> 00:13:52,390
Any solution, configuration which is below
that is guaranteed to be

281
00:13:52,390 --> 00:13:55,210
worse than the best solutions that you
have found so far.

282
00:13:55,210 --> 00:13:58,290
So you can stop there, and you know that
you have an optimal solution.

283
00:13:58,290 --> 00:13:59,790
And does the value

284
00:13:59,790 --> 00:14:01,580
of a good relaxation.
Okay.

285
00:14:01,580 --> 00:14:04,860
So if you relax and you do a good job of

286
00:14:04,860 --> 00:14:08,480
relaxing, okay, the, the computing job
that you will have to do.

287
00:14:08,480 --> 00:14:12,200
The job, the search space that you will
explore, is going to be much smaller.

288
00:14:12,200 --> 00:14:12,730
Okay.

289
00:14:12,730 --> 00:14:14,239
And that's the value of relaxation