Okay? 
Welcome back. 
This is Discrete Optimization, second 
part of the Knapsack Problem. 
Okay. 
So what I'm going to do here on this 
lecture is switch hats. 
I'm going to take my made in the USA hat, 
okay, and change it and take another hat, 
you know, made in China, okay? 
And the reason that I'm doing this is 
because we are looking at the completely 
different way of solving exactly the same 
problem. 
And that's what is beautiful in 
optimization, right? 
So you have many hats, okay? 
And every one of them is a bag of tools 
that you can use for tackling a problem, 
okay? 
So today, I just changed my bag of tool, 
okay? 
I'm picking up another tool, okay? 
And that, and I'm going to show you how 
to use that tool for actually solving the 
Knapsack, okay? 
One of the thing I won't tell you is 
which of the two hats is better, okay? 
So you will have to figure out, you know, 
from yourself. 
But we're going to introduce a technique 
which is widely useful. 
Okay? 
Which is called branch and bound. 
Okay? 
Once again, we take the one-dimensional 
knapsack, okay? 
That we solved with dynamic programming. 
My other hat the other, the other day, 
okay? 
And so, what we see is we have the, the 
value of all the items. 
You have the weight of old d items which 
is to be smaller than k, and then we have 
to decide whether we have taken item or 
not. 
0 and 1 over it right? 
Okay, so that's the one-dimensional 
knapsack okay? 
Now, if I want to introduce. 
Branch and bones. 
What I have to do is start with 
exhaustive search, right? 
And that's the first thing I told you 
last time, right? 
So you can always decide, you know, I 
take, I take the item or I don't. 
OK? 
So, so in a sense, you know, once I have, 
once I make this, once I do that, I have 
two nodes. 
And I can do the same thing for the next 
level. 
I can decide where I take item to or I 
don't take the item to. 
And then I can continue and this part, 
this particular case. 
If I have three item, I get eight 
configuration. 
If I, if I get four, I'm going to get 16, 
32, 64 and so on. 
And it's going to grow exponentially. 
And of course what you don't want to do 
is explore all of these configuration, 
okay? 
So what we did with dynamic programming 
is trying to compute this thing bottom 
up. 
Avoiding to compute several times the 
same thing. 
What we're going to see here is branch 
and bound where you iterate two steps. 
A branching step, which is really trying 
to explore this, this tree, all right. 
So, like basically, we are going to 
explore the entire tree. 
But, we are going to use this technique, 
which is bounding. 
And bounding is going to tell you, wow, I 
look at this node. 
And I know for sure that I'm not going to 
ever be able to find and optimal solution 
below that node. 
So, I don't have to expand it. 
So you prune large part of this tree. 
And that's what branch and bound is all 
about. 
Okay? 
So looking at a tree, and starting, 
removing large pieces of it. 
Okay? 
Using what is called bounding. 
Okay? 
So, branching, I told you what it was, 
very easy, it's like an exhaustive 
search, sort of want to enumerate 
everything. 
Okay? 
And bounding is about finding an 
optimistic evaluation of a particular 
node. 
Okay? 
So optimization is for optimistic people. 
If you are not optimistic you can already 
give up, okay? 
So because we are trying to solve really 
hard problem, if you don't think you can 
do it, just no hope. 
So you have to be optimistic. 
And bounding is just that, okay? 
So you are looking at the node and how 
best can you do that node. 
Okay? 
So, if you maximize, you will have an 
upper bound. 
That's the top, you know, best that I 
could do for this knapsack. 
You know, if I, you know, if, the best 
that I can hope for. 
And if it's a minimization, it's going to 
be a lower bound. 
And how low can I go. 
Okay? 
So in a sense, what you want to do is 
find an optimistic evaluation, you know 
the best you can do, but of course you 
want the optimistic evaluation to be as 
middle of the optimistic as possible, 
right? 
So you want to make it as tight, as close 
to the optimal value as possible, okay, 
so we want to try to evaluate how good 
this node can be. 
As precisely as possible. 
Okay? 
That's bounding. 
Okay? 
So, how do we find this bounding 
technique? 
How, how do we bound? 
Okay? 
And so the basic idea here is that, what 
we're going to do is take the problem and 
relax it. 
Okay? 
So they also are going to think that you 
have always to remember is that. 
In a sense, optimization is the art of 
relaxation. 
OK? 
So, you know, optimization people, are 
both optimistic, and they know how to 
relax. 
OK? 
So we are very nice people, right? 
So, that's what we have to do. 
So, so now what we have to discuss is how 
we do relaxation in practice. 
OK? 
So you look at this model again, okay? 
That's a knapsack problem. 
And you are wondering you know, how can I 
relax this problem in such a way that the 
optimal solution is going to be better, 
well, the optimal solution of the 
relaxation is going to be better than the 
true optimal solution. 
How do I do that? 
Okay? 
Now you can look at everyting here and 
decide what to relax, one of the easy 
things to relax is [UNKNOWN]. 
While you can say, oh I'm going to relax 
the capacity constraint. 
So if I'm going to remove that 
constraints. 
I make the problems, you know, I make, 
it's a relaxation. 
Why is it a relaxation, because 
essentially I'm increasing the set of 
solutions to the problem. 
Now all these invisible solutions that I 
have to, that I eliminated before. 
Know they are solution. 
So these invisible configuration can 
somehow Are becoming feasible, so I have 
more of them. 
So the value of the objective value, the 
optimal solution of the optimal value is 
going to be higher. 
Okay. 
So that's an optimistic relaxation of 
this problem. 
Okay? 
So what happens when you do that? 
Okay. 
So, this is a simple example that I've 
shown you. 
You see on the table here You know, you 
see all the values of the items, and then 
you see the weight of every one of them, 
okay? 
So the first item, for instance, has a 
value of 45 and a weight of 5, okay? 
48 for the next one, and 8 as the weight, 
okay? 
So what we want to do is essentially 
solve th-, this, this problem with these 
three items and a capacity of 10, okay? 
So, you basically start at the beginning. 
What is the best, best, best you could 
ever do, okay? 
Well, we have relaxed the capacity 
constraint, so we can take all the items, 
okay? 
So, in this particular case, if you sum 
all the items. 
What you get, the va-, the sum of the 
values of all the items, you get 128. 
And that's what you see are these root 
node here, okay? 
So what you see are the root node, okay? 
Is basically the value 128. 
You see that the capacity of the knapsack 
is 10. 
And we are at the root node; we haven't 
actually accumulated anything. 
So the value is still 0, okay? 
So what are we going to do? 
Is we're going to take that node and 
branch, okay? 
So when we branch, and that's what you 
see there, okay, so I basically branch on 
the first item, okay, and that branch 
gives me a value of 45. 
Okay. 
Now, it also take a weight of 5, so now 
the capacity of the knapsack is 5, okay. 
And my, you know, optimistic evaluation 
is still 128 because now, if I can still 
take all the items, okay 
 >> So single variation, okay. 
I keep going. 
I decide to take item two, okay. 
If I take item two [NOISE] boom okay. 
I'm exceeding, I'm exceeding the capacity 
of the nap sac, five plus eight, 13. 
Okay, so this is an infeasible 
configureation. 
OK? 
Not a solution, and so I can reject it. 
OK? 
So I know that I cannot take item two if 
I have taken item one, OK? 
So the new evaluation is the sum of all 
the items that I can take, and in this 
particular case there is only one left, 
which is three And so the best thing that 
I could ever do, if I don't take item 
two, is 80. 
OK? 
And then I decide to take item three. 
That's what you see here. 
OK? 
And I get that value of 80. 
Yes! 
I have a solution now. 
OK? 
And its value is 80. 
If I don't take the item, I also get a 
solution. 
Its value is 45, so I can prune it away, 
okay? 
These nice little symbols here means, and 
we'll see that again and again, is 
basically mean I can prune that node, I 
don't need to look at that node. 
Is, is dominated by the best solutions I 
have found so far. 
Okay. 
Now you go back and there's the thing 
that you could do there is essentially 
not selecting item 1. 
What you get tehre is an optimastic 
evaluation which is 83. 
Okay. 
So if select the 2 other items I can get 
83. 
Now 83 is still better than 80 the 
solution that I have. 
Okay so i have to continue. 
Okay. 
So I'm continuing. 
Okay. 
So, I take item 2 okay, so I get still an 
evaluation of 83. 
And then, if I take item 3, [SOUND] I 
exceed the capacity of the knapsack. 
So, that's not a feasible, that's not a 
solution. 
That's not a feasible configuration. 
And if I don't take it, I get a value of 
48. 
that's not good. 
It's dominated by the best solution I 
found. 
I go back here, okay, I decide not to 
take item 2. 
And so, now all best value is 1 is 35. 
Okay, 35 is worse, is way worse. 
That what we have found there, I don't 
need to explore below, below that node. 
That's bounding, right. 
I know that, even if I take all the 
possible items that I have left, this 
will, this, this note will never be 
expanded to something which is better 
than 35 and before I can prune it away. 
I don't need to explore the choices. 
For the third item, below that node, 
okay? 
So that, you know, that explains to you, 
the bonding process in a very very naieve 
and simple relaxation, okay? 
So, now we look at this thing and we say, 
okay, so can I actually do something 
which is not completely stupid, can I 
actually get a relaxation here? 
Which is giving me some interesting, some 
interesting optimistic evaluation. 
How can I relax this in an interesting 
fashion? 
Okay? 
Now, think, you know, if instead of 
having these beautiful artifacts that, 
you know, Indiana Jones has to collect, 
what we are trying to do is to collect 
something which is almost as valuable, 
Belgian chocolate, right? 
So we are basically at all these bars of 
Belgian chocolate we will take as many as 
we can. 
But then, essentially, what can happen is 
that, okay, you fill your knapsack and 
then there is this nice bar that doesn't 
fit into the knapsack. 
What you can always do at that point is 
take the bar and break it, right. 
And you take a piece of it, okay. 
So, in a sense, one of the things that 
you can do in this particular case. 
If, if you are dealing with this 
beautiful and tasty Belgian chocolate. 
Is cut one item in parts, okay? 
You can do that, so that you can actually 
fit it inside the knapsack. 
So, if you do that essentially what 
you're doing is relaxing. 
The decision, the values of the decision 
variable can take. 
Remember before, the value that xi could 
take is 0 and 1, I take it or I don't, 
well I don't take it or I take it, okay? 
And so what I'm doing here is saying, oh 
but no, I can take an item or I cannot 
take an item or I can take any part of 
that item, any fraction of the item. 
And that's really what I do here, okay? 
So this is an interesting relaxation. 
We'll come back to it many, many times in 
this, in this class. 
And it's called the linear relaxation. 
Okay? 
So what we are basically doing is taking 
the, you know, the, the variable, the 
decision variable, which takes. 
We just have to take an integral value. 
And relaxing that so that they can take 
this continuous values inside the, their, 
their branches, okay? 
So we are basically saying that, no, we 
can take fractional parts of these, you 
know, items are in the values that these 
variables can take. 
Okay, so when you do that, okay, so you 
look at this knapsack and how do you, can 
you actually compute this in your 
relaxation? 
How do you actually find the solution, 
okay? 
Because now, we have to take, you know, 
we have to take all these fractional 
numbers, there are many, many, many more 
positive entities, right? 
So how are we going to do that? 
Well, there is a very simple way very, 
very simple way to do that in this 
particular case. 
And the key idea is that you look at all 
the items, and you rank them by this 
ratio, W-, Vi over Wi. 
So, remember, Vi is the value of the 
item, Wi is the weight. 
So in a sense, when you rank, so this 
ratio is giving you the most value per, 
you know, kilo or pot, okay? 
It's giving you the value, the most value 
of the, the items, that are, is ranking 
by the items that are the most valuable 
In, per unit, in a sense, okay? 
And so, you rank them in that particular 
way, and the key idea is that once you 
have ranked them in that particular way, 
you take them, you know. 
You take the most valuable item, and then 
the next valuable item, and then the 
subsequent valuable item. 
And at some point, you're going to get to 
the capacity of the knapsack. 
You can't fill the knapsack with the next 
item. 
And at that point, what you do is, you 
take a fractional part of that last item 
that you can't really fit into it, okay? 
And that's going to give you the optimal 
solution to this thing, okay? 
So if you look at this problem here, 
okay? 
So, these are the various ratios that you 
see there. 
Right? 
So, the first one is ni-, a value of 9. 
The second one 6. 
The, the third one is roughly 11.7. 
So, this is the, the third item is the 
most valuable. 
Okay? 
And that's obvious, right? 
So you see 35 divided by 3. 
That's obviously greater than, you know 
6, which is 48 divided by 8. 
Okay? 
So, in a sense, so now we have rang/ 
these guys, so we're going to select the 
third item first. 
Okay? 
And the total items take only a weight of 
3, so you still have room in the 
knapsack. 
Okay? 
And you got already a value of 35. 
Then you take the value 1, you take the 
item 1, its value, 45; so that gives you 
already 80, okay? 
And, you know that, that fits in the 
knapsack. 
Your knapsack at that point is, is you 
have already taken 8, 8 of the capaci-, 
you know, 8, you know, 8 units of the, of 
the capacity of the knapsack. 
Now, you look at the last item. 
The last i-, item would take 8, you know, 
of capacity in the knapsack. 
You can't fit it in, okay? 
You have only 2, you know, left. 
And so what you're going to do is take 
only a quarter of that item and of 
course, you get a quarter of that value. 
Okay, which is in this particular case, 
12, and you get an optimistic evaluation 
node, which is 92. 
Now, look at what we have done. 
Before if you take all the items, we have 
something like what, you know 128. 
Right? 
Now, we have an optimistic evaluation 
here, which is 92. 
That, we will never reach that. 
This, well, maybe we can. 
But, but this is the best we could ever 
do, if we actually select an, you know, 
items in their entirety. 
But this is an optimistic evaluation of 
the best you can do. 
Okay? 
So, so, so, but, it's much tighter than 
the one that we did before and that's 
good. 
So, you want this bond to be optimistic 
but as tight as possible. 
Right? 
And that's what we just did in this 
particular case. 
Okay? 
Now, you know, this is, this is the 
intuition why it is correct. 
You can play this valuable 
transformation. 
Where, you know, Yy is essentially Vi 
times Xi. 
When you do that, essentially, the 
objective function becomes beautiful. 
It's just a sum of all the decision 
variables. 
Inside, all the items have the same 
values. 
Okay. 
What has changed is the weight of these 
item now, okay. 
So the one which was, which was the most 
valuable now essentially is the s-, is 
the one that takes the fewest space 
inside the item. 
So what you're going to do is basically 
fill the item one by one, the one that 
take the least space inside the knapsack, 
until you get to the last one because 
they have all the same value. 
And until you get the last one which has 
a, you know, which maybe takes more space 
and you can, you will take only a 
fractional part of it. 
This is why, this is how you can justify 
correctness. 
Of the linear relaxation that I have 
shown you before. 
Okay? 
So, now, of course, in practice, you 
know, you probably don't want to take 
this, you know, stone, or Afghan emblem 
mask and break it into part, right? 
So we have to take entire pieces. 
We can't break them into parts. 
So all we're going to use that 
relaxation, well, we are going to use it 
as a bonding technique, right? 
So now we are at the top of the node. 
We know that the best we could ever do is 
92, okay? 
We haven't selected anything, we still 
have the full capacity of the knapsack 
available, okay? 
Now, if you select item 1, obviously 
every time you select something, okay, so 
in this particular case, you know, since 
it was taken into relaxation, you will 
have the same relaxation over, optimistic 
value here. 
So you still get 92. 
Now, you have already accumulated the 
value of 45 and the capacity of the 
knapsack is 5, okay? 
You keep going, you know if you take item 
2, boom, okay, you exceed the capacity of 
the knapsack, this is unfeasible so you 
don't consider that guy. 
You go on the right. 
You don't take item 2. 
What is interesting here is that now, the 
evaluation is different. 
It's 80, okay? 
It's taking basically item 1 and item 3. 
And you get a feasible solution when you 
take it. 
You also get a feasible solution if you 
don't take it, but that solution is 
dominated so you can create a way. 
Okay? 
So what is interesting, though, is what 
happens if you don't take item 1. 
Okay? 
If you don't take item 1, look. 
What we have is the value 77, right? 
That value is already lower than the best 
solution you found, which is 80. 
Which basically means what? 
Whatever you will do here below that 
tree, right, below that node, okay, 
whatever you will do Is not going to get 
you better, better solution than 77. 
You know that 77 is already lower than 
this one so you can throw the entire tree 
there, completely away. 
You can prune that, you know, away. 
Okay? 
So which is great. 
Right? 
So know the 3 is much smaller than 
before, you are cutting this exponential 
growth. 
Okay. 
Now how did we get, you know, 77. 
Well, what you know is that you can take 
item 1. 
Right? 
So you know that the most valuable item 
is item 3 so you take also 3 units of 
capacity for knapsack, okay, and you 
accumulate 35. 
So which means what, that you have 7 
units left in the knapsack, okay? 
So this guy is taking eight and you can't 
take all of them okay, so you are 
going to do what, you going to take seven 
of these 8 units. 
So if you do 7 8ths of 48, what you get 
is, is what? 
Okay. 
Is 42, 42 plus 35 is 77. 
That's the value that you see there. 
Okay, so but the key point here is that 
this is an optimistic evaluation using 
the linear relaxation. 
That's what I just told you about and 
because this value is really tight in 
this particular case, we can prune it, we 
can prune the entire subtree which is 
below that node in one step, at that 
level. 
Okay? 
And therefore the tree is much smaller. 
Okay? 
We prune that guy; we are done, okay? 
So, essentially, this is an introduction 
to depth-first branch and bound. 
That's the strategy that we have done, 
okay? 
So we start exploring the node, and then 
the node, you know? 
Th-, we start exploring from left to, you 
know, from left to right. 
And every time we branch, we have two 
nodes, we take the left one and we do 
that. 
When you go back we explore the right 
one. 
That's the depth-first search. 
There is another strategy which is 
best-first. 
And that strategy is essentially always 
taking the node which has the best 
evaluation. 
Okay? 
So we always say, oh, that node is a good 
evaluation. 
I want to take it because that's probably 
where the best solutions are. 
Okay? 
I'm going to discuss that in a moment. 
Okay? 
But there are many others and we'll come 
back to that later in the class. 
Okay, so that first, the key ID in that 
first is that you prune a node every time 
the evaluation is worse than the one you, 
that, that you have found so far, okay. 
It's very memory efficient. 
The only thing that you have to remember 
is essentially a path, okay. 
best-first search is always selecting the 
node with the best estimation, okay? 
And the key ID, what, the reason why you 
want to use a technique like that is 
because you want to dive in very quickly. 
To the best possible solution. 
Okay? 
So let me illustrate this by using the 
stupid illustration that we have seen 
before. 
Because it's easier to actually do the 
illustration here, okay? 
So I restart from the root. 
Okay? 
And I have the value of 28 nothing in the 
knapsack. 
No value accumulated. 
Okay? 
So essentially what I do is that in the 
particular case, you know, I branch, I 
generate these two nodes and I take the 
one that has the largest value. 
Right? 
so I take the one which has the value 
128, okay? 
So that's when I take the item, right? 
And now, what I do is, I expand that 
node, and I get 2 nodes, okay? 
So, I get one which is infeasible, so I 
throw it away, and I get another one, 
which has value 80. 
At that point, I look at all the nodes 
that I have, okay? 
I have 2 left. 
Which are feasible, which are potentially 
feasible, they are still feasible at this 
point. 
And I think the one which is the best 
evaluation of function which is this guy, 
right. 
So I expand that guy and I get two nodes, 
I get another node with 83 and I get a 
node with 35. 
So I take the node which has the highest 
value which is once again 83. 
I expand 83 and i get a value of 48. 
Okay, and any, and any feasible solution, 
okay? 
So I get 48 over there. 
That's the best, so that's the solution 
now, okay, and I can throw all the nodes 
which are in the tree which are worse 
than that. 
So I will throw away this particular node 
here, okay. 
Now that node here as evaluated, it's 
still greater than the best solution that 
I found, so I keep expanding it, okay. 
Whoops, sorry, so I forgot one of the 
things that I wanted to do. 
Okay, so I get these two, I get these two 
nodes, I get these two nodes there. 
Okay? 
And one of them is the value 80. 
The other one is the value 45, okay? 
So the value 45, I can throw away again. 
Okay? 
And the value 80 now becomes the best 
form solution. 
Okay? 
So, essentially, best-first is always 
going to look at the nodes and take the 
one which has the best evaluation 
function. 
When does it prune? 
It prunes when you have a physical 
solution, okay? 
When you find a physical solution, then 
all the nodes which are, you know, that 
are worse evaluations are going to be 
thrown away. 
And, the question that I have for you is 
that, is it memory efficient? 
Okay? 
And, I'm give you, I'm giving you a trick 
here. 
In most of these optimization problems, 
and most of the questions I'm going to 
ask you. 
The answers can always be found by 
exaggerating. 
Okay? 
So exaggerate the situation. 
If you exaggerate the situation, you will 
find out whether this thing, you know, 
whether the answer is, you know, whether 
the, well, what the answer is to the 
question. 
Okay so how do we exaggerate in this 
particular context. 
The way to exaggerate there is to assume 
that you have a terrible optimistic 
evaluation, you always return minus, plus 
infinity, you always believe that you can 
win the lottery, okay, so if you do that 
how many nodes are you going to expire, 
okay, so you are basically going to 
explore the entire tree because it's only 
when you find a solution at the end that 
it's going to tell you oh, this is the 
value... 
But all the other nodes are still, I can 
do better, I can do better. 
So you gotta explore the entire thing. 
So, what this is basically telling you is 
that if, you know, there are many nodes 
which are very close to the optimal 
solution, okay? 
So you may explore a very large portion 
of the tree. 
Okay? 
So it's, so the memory is an issue when 
you do a best, you know, best-first 
branch and bound. 
You have to make sure that you are not 
going to explore too many nodes. 
Okay? 
So so we have seen two techniques now 
dynamic programming and branch and bound. 
So one of the things you have to think 
about is which one is better than the 
other one, okay? 
One of the things that you may think 
about is that is this a good question, 
okay, is this even a valid question so 
think about it, okay? 
And then the other thing, and this is a 
valid question for sure. 
Can you actually combine these two 
techniques together? 
Can you actually have an algorithm which 
is the same, which is at the same time 
exploring some features of dynamic 
programming? 
And some features of Branch and Bound, 
okay? 
So you need to think about, what is 
really the essence of dynamic 
programming, okay? 
What is really the essence of Branch and 
Bound? 
Can you actually combine the two of them? 
Okay? 
Good. 
So this is essentially, you know, the end 
of the ramping up phase of the class. 
OK? 
So we have seen a very, very simple 
problem. 
Knapsack. 
Okay? 
Two basic techniques, you know, dynamic 
programming and branch and bound. 
We're going to look, now, in the next, 
the rest of the class, at various 
techniques like constrained programming, 
local search, mathematical programming. 
And, and try to look at more complex 
problems of course, okay? 
See you next time.