Knapsack 5 - relaxation, branch and bound

Loading...

From the course by The University of Melbourne

Discrete Optimization

298 ratings

The University of Melbourne

Discrete Optimization

298 ratings

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming. Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

From the lesson

Knapsack

These lectures introduce optimization problems and some optimization techniques through the knapsack problem, one of the most well-known problem in the field. It discusses how to formalize and model optimization problems using knapsack as an example. It then reviews how to apply dynamic programming and branch and bound to the knapsack problem, providing intuition behind these two fundamental optimization techniques. The concept of relaxation and search are also discussed.

Knapsack 1 - intuition2:33

Knapsack 2 - greedy algorithms7:13

Knapsack 3 - modeling8:56

Knapsack 4 - dynamic programming17:57

Knapsack 5 - relaxation, branch and bound14:53

Knapsack 6 - search strategies, depth first, best first, least discrepancy14:45

Meet the Instructors

Professor Pascal Van Hentenryck
Dr. Carleton Coffrin
Adjunct Lecturer
Computing and Information Systems

Welcome back.

This is discrete optimization again, the knapsack problem.

And as you can see, I have a new hat. This is the branch and bound hat.

Something which is really useful, and going to be used

over and over again in this particular class, okay.

We're going to introduce branch and bond, and also the value of relaxation, okay?

Two very important concept in one lecture, but

still the lecture will be short, you'll see.

Okay so, this is the one dimensional knapsack,

we have seen it many times, you're probably start getting fed

up with this particular knapsack, but you going to see something beautiful today.

Okay, so, you know, remember when we talk about binary programming,

we talk about exhaustive search, okay, and in a sense we

have this, you know, decision variables on top and what we're

trying to find out is the values that are possible for this.

This, decision vibrance and what I've shown you during the

dynamic programming lecture is that they exponentially many of these guys

in terms of the number of items. Okay?

But how do we, this is a way to actually build this configuration okay.

You take the first item, and you have two decisions.

Okay.

Whether you take the item or whether you don't take the item, okay?

And now you have these two possibilities, and for these two possibilities.

You're going to look at the second item and you can

decide to take the second item or not to take it.

And once again, what you get now are four different configurations.

And now, you can do the same with the third

item, okay, and you get the final eight configuration, okay.

And every one of the configuration will

tell you whether you choose, you know, item

one or not, whether you choose item two or not, or item three or not.

And obviously I had four item we would have, you know, 16

of them, 5 item, 32, and this would grow, grow, grow very large.

What branch and body is about is looking at this tree and trying

to explore only a tiny part of it And finding the optimum solution

nevertheless, okay?

So that's what we're going to do, and we're going to show you how to do that.

And the key idea is that the iterative two steps, okay.

Branching and bounding. And branching is boring, right?

It's like the exhaustive search, except later on I will

tell you that there are smart ways to do this.

But at this point it's completely boring.

You know, it's like, okay, so I take an item and whether I

take the item or not, that's what branching is going to be about, okay.

It's like in the exhaustive search. But then bounding.

Bounding is very different.

It's like finding an optimistic evaluation Of what you can do, okay.

So in optimization you have to be optimistic, in life

as well right, so we want you to be optimistic.

In fact, what is the best that I could ever do, okay, if you are maximizing.

Or if you are minimizing, how low can be my cost, okay.

So that's the kind of optimistic evaluation

that we need for actually for bounding, okay.

And I'm going to show

you how we can get this. Okay.

So how do we find these things?

So we are going to basically take the problem and relax it.

And so optimization Is the art of relaxation.

Okay, so image yourself in this [UNKNOWN], and you are completely zen, and you find

out the best way you can actually relax these problems and make it easy to solve.

Okay?

And get and object, and get an optimistic evaluation of this thing.

Okay, so once again This is the

knapsack, and you ask yourself, [INAUDIBLE],

okay, now, relax this [UNKNOWN], okay?

And there are not that many things in this notation, right?

So, in this formulation. And so, you may say, oh.

with what I could relax is this constraint, okay?

We're going to relax the capacity constraint, okay?

And then, as soon as we do that, usually,

we can get an optimistic evaluation of this problem.

evaluation, okay?

So, what you going to see is that you're going to see

these node in the tree that I'm going to build, okay?

They have three entries, okay?

They have the value of that I have accumulated inside the knapsack.

They have the space left in the knapsack.

And then they have this optimistic evaluation, okay?

So initially I have accumulated no value.

I have, you know, the full space in my knapsack.

10 in this particular case.

And then I have this optimistic evaluation which is oh, I can select everything okay,

so in this particular case is 128. And now I start doing things.

Right?

I'm selecting the first item, okay.

As soon as I do that I computed the value of the first item, 45.

I take 5 units of space in the, in the knapsack.

And my, you know, optimistic evaluation is still 128.

You know, then I try to select item 2 but as you can see

item 2 is a size of 8 so I'm exceeding the capacity of the knapsack.

That's not a feasible solution, okay, so I can't take item 2.

And at that point my optimistic evaluation is reduced to 80, okay?

And I can decide to take item three or not, okay?

If I take item three, I get the value of 80, okay, this is one and three.

And if I don't take it, I get a value of

45, which is essentially completely dominated

by the previous solution I found.

Okay, so I know that this is not an optimal solution.

Okay.

Now I go back to the next part of the tree.

I decide not to select item 1 so

my optimistic evaluation at this point is 83.

It's still better than this guy, okay, 18, the best solution that I've found.

So I keep going.

Okay. I select item 2.

If I select item 2 I'm still 83.

Okay, then I decide if I select item 3 or

not Okay, in the first case I get an unfeasible solution.

Otherwise I get the value 48, which is also

dominated by the best solutions that I have found.

So, you know, this is why I put this cross over there.

Otherwise if I decided not to take item two, okay?

So, what I get is a configuration there, okay?

Which is optimistic, whose optimistic evaluation is 35, okay?

Now that's terrible right? So it's worse!

That the best solutions that I have found so far.

So, I can decide without continuing anything, now this is not valuable, okay?

I don't have to actually branch on item 3.

I already know that the best I could do is worst than the

best solution that I had. And this is the key idea behind bounding.

Once you have this optimistic evaluation, if it's worse than the best solution you

have found, you know that you don't have to explore whatever is below the tree.

Now this is an example which is terribly bad, alright?

Because my optimistic evaluation is so optimistic that most of

the time I'm going to basically explore the entire tree, okay?

But so you can see sometimes we get a little bit of pruning, okay?

But what we have to do is to find a better relaxation

so that We can prune a bigger part of this tree, okay?

So, look again at this knapsack example and think, okay?

What else can I relax?

Okay, I let you think for about, ten minutes I guess, okay?

And then I'll tell you, okay? Can we relax something else?

And you're going to see a beautiful slide, okay.

So we are going to assume that

instead of packing artifacts, we are packing bars of Belgian chocolate, okay.

Now this is completely different, right.

So because now, you know, when you have Belgian chocolate.

Let me give you a picture, okay.

So, because this is so beautiful I'm already hungry here.

Okay, so and, and here I can tell you that Indian

Jones loved Belgian chocolate, that's the best chocolate in the world.

By far, okay.

So this is this bar of chocolates, okay. Now what Indiana Jones can

say, mm, oh i can't pile the whole thing in my knapsack, but

I can break it into piece and put it in my knapsack, right.

So this is completely different, right.

It's not I take, or I don't take.

I can take a piece of it, right. And so now, assume that my old knapsack.

Is built of artifacts that I can break. Like you know, Belgian chocolate, okay?

So then I get this beautiful [UNKNOWN], right?

So, the only thing

that I did was for the decision variables. They don't have to be zero one.

I take it, or I don't take it, black and white, ying and yang, right?

Only, what I'm doing here is saying, ooh, but I

can take a fractional value of these particular decision variables.

I can take a quarter of it, or I can take half of it, or something like this, right?

And so I get this optimization problem here, which is almost the same as before.

Except that the value of the, of the decision variables

now can take any fraction between zero and one.

Okay, and now you can ask, oh, but, you know, is that problem easy to solve?

Okay, well actually this problem is called a linear relaxation.

You're going to see that in this class all the time, okay.

Especially when we start looking at, you

know, mathematical programming, linear programming, mixed integer programming.

And so this is a very, very important concept.

So this says, a linear art, a linear relaxation of the knapsack.

And this has a very important properties that in practice it's easy to compute.

And I'm going to show a very easy way for the knapsack.

In practice it's a little bit more complicated.

We'll, we'll cover that as well, okay?

So the only thing that the linear relaxation is

doing is take every value that To be a.

A natural number, so an integer numbers.

And relaxing them to a fraction.

That's what the linear relaxation is doing, is basically

relaxing the integrality constraints that you have in most of

these models, okay? So, now how can we solve this?

I'm going to show you a very simple way to do this.

And this is going to you know, basically be very close

to some, some of the greediogories in that we have seen.

So we going to order the item By value per kilos.

Okay.

So this is this WI you know, over you know VI over WI ratio that I, that

I've shown you before, okay. So basically the item that is the largest

value Okay, it is essentially the va, item

that is the most valuable by kilo, and when

you look at chocolate that's, that's what you want

right, 'cos you can start breaking them up okay?

So essentially you alter the item by this and what you

have to do is basically select all the item okay, until the

capacity is, select all the items until the capacity is exhausted, putting

another item with, go over the capacity and for this And once

you have that you select the item and select

a fraction of it so you fill the knapsack.

So in a sense you order these items in the greedy

algorithm you accumulate them if the next one is going to

go over capacity what you do is take a fraction of

it such that, that particular fraction is going to fill the knapsack.

And this is essentially an optimal solution of this linear relaxation Okay.

So look

at this in this particular example, okay.

So, you see the various, you know, you see item one, item two, item three, okay.

So the first item is 45 over 5, okay, and

that gives you a value of 9 for that particular item.

The second one is 48 over 8, okay, and that gives you a value of 6.

And the third on is that?

It's 35 over 3 and that gives you a value of around You know 11.7.

So the item number three is actually per, y'know per

kilo the most valuable item. And then next one and next two.

So what you would do here is you would select item one, you would

select item two okay, that gives you two units for the capacity of the knapsack.

and then you essentially take a quarter because

the weight of item two is eight okay.

So you take a quarter of the value of this guy going to

give you umm which is going to give you a quarter of that a

value of 12 and the overall value of

the linear estimation is going to be ninety two.

So ninety two in this particular case is an optimistic evaluation Of the knapsack.

You know for sure that you will never do better than 92.

Okay?

So, but this is much better than the relaxation that we had before,

right, where we would basically sum

everything, okay, and get 130 or something.

Right, so here, we have actually a value

which is actually pretty good, okay, in this particular case, okay.

So, essentially the linear relaxation here is giving

you a very good value for the, for bonding.

particular knapsack problem. Okay?

Now why is this correct?

This is a simple reformulation of, of the, of this linear relaxation, okay?

So you basically express, you introduce a

new variable YI, which is basically the product

of VI and XI okay?

And then you reformulate the knapsack and what you see when you reformulate

this knapsack is that all the item Have the same, you know, value.

Okay, they have a value 1, okay.

But what is interesting when you reformulate this problem is

one, is not only the values are all the same,

but then this, this, this weight is basically the density,

the inverse of the density that I was talking about, okay.

The most

valuable item have the least weight in this reformulation.

Okay.

So how do you solve it?

Well, it's like the greedy algorithm that we have seen before.

You take the smallest item first And when you get

stuck you take the fractional value of the last one.

That's why, in this particular case, the linear relaxation is actually,

is actually well, the algorithm that I've given, that I've shown you.

Select all the items until you get stuck and

then a fraction is actually computing the linear relaxation.

But of course,

in practice, okay, the linear relaxation is not a solution to a problem.

Right?

Because we have this mask and there is no way we can break it,

and anyway, even if you could break it you would not want to break it.

So essentially we can't take a fraction part of this

mask right, we can't decide to just take the nose or

whatever right, so we have to do, we have to

use this linear relaxation, ok inside the branch and bound algorithm.

And that's what we going to do, okay?

So we start again at the root, okay? There is nowhere else to start.

But we know that the evaluation, the optimistic evaluation here is 92, okay?

Now we start, we go on the left, okay?

So we take the items one. Same evaluation, you know?

Fewer space in the line. Less space in the knapsack.

We take item two, this is [INAUDIBLE] feasible.

You know?

This is essentially the same as before. We get this solution with [UNKNOWN].

The other one with 45 is dominated. But no.

Now you're going to see something

really, really cute, okay.

So you go under, you, you go on the right, okay, you don't select item 1.

And what you see there now is that the optimistic evaluation is 77.

Oh, the 77 is worse than the best solution that I have found so far, 80.

So you know that the entire tree here, can be thrown away.

You don't have to look at it at all, right.

So you are at 77 here.

And you know that anything which is below you.

Any solution, configuration which is below that is guaranteed to be

worse than the best solutions that you have found so far.

So you can stop there, and you know that you have an optimal solution.

And does the value

of a good relaxation. Okay.

So if you relax and you do a good job of

relaxing, okay, the, the computing job that you will have to do.

The job, the search space that you will explore, is going to be much smaller.

Okay.

And that's the value of relaxation

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play