Knapsack 6 - search strategies, depth first, best first, least discrepancy

Loading...

En provenance du cours de The University of Melbourne

Discrete Optimization

220 notes

The University of Melbourne

Discrete Optimization

220 notes

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.

À partir de la leçon

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

Rencontrer les enseignants

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

Okay, welcome back, discrete optimization, knapsack.

So I want to go back to the branch and

bound, and talk a little bit about search strategies.

I put something under the rug, and I want to cover them during this lecture.

And you're going to see, some of these things

are going to be very interesting later on, okay?

But you need, you need to understand them.

It's going to build on branch and bound, but just refine the kinds of thing,

actually expand the kinds of things that you can do in branch and bound.

Okay? Remember, branch and one we are working

with real artifacts that we can break but

still we are using the linear relaxation in general,

or relaxation in general to actually compute good, you

know, optimistic episodes of the best you can do.

Okay?

So once again the key idea between branch and bound is that you look at

this exhaustive search, and you want to explore a very tiny piece of this tree.

Okay?

And you do that with basic, you know, relaxation ID.

Okay?

Now one

of the things I didn't talk about last time is

that you can search that tree in many different ways.

So, we saw that first branch and bound and I will talk about a little bit

about it again such that to refresh your

memory, but there are other things you can do.

And some of them are, you know, code best, you know, best, best search, best-first

search or, you know, limited discrepancy search,

and that's what I want to cover today.

Okay I want to give you an idea that, you know, there

is one thing that you need to consider when you solve a problem.

It's also

how you explore that, that particular, that particular trait.

There are many others, and you will see more in this class, okay?

But at this point, I just want to give you some of

the ideas on what you can do, and compare them, okay?

So that first search, you explore your, your,

your, no, that's what we saw last time.

You explore your tree in a tree in that first fashion,

and you prune the search tree as soon as you come

back to a node, and that node is an optimistic evaluation

which is worse than the best solutions you have found, okay?

That's depth-first search,

okay? Now we going to see best-first search.

And the key idea there is that you want to

select at any stage the node which has the best evaluation.

Okay.

So that's what best-first is.

And we'll see a limited discrepency search where

what you will do is trusting a greedy heuristic.

And you'll be, be following these heuristic and then allowing you

to move away from the heuristic in a very systematic fashion.

So I'll go into the details of these two things, okay?

So let, you know I just want to remind you of that first search first, okay?

And we are using the good eval-, the

linear relaxation here for the knapsack problem, okay?

And remember what we did was basically exploring these tree, we

would find a good solution there, with a cost of 80.

And then we would go back to the other part

of the tree here, where we're done selling the first item.

And you see that the optimistic evaluation here is worse than

the best solution that we have found, and therefore you can

prove this entire tree.

Okay so that's what I told you before, in that first

search, when you have an optimistic evaluation of a note, you compare

it to the best solutions that you have found so far,

and if it's worse then you just throw the entire sub-tree away.

Okay? So that's what that first search is about.

Okay?

So in a sense, you know, the key idea for that

search is like in the NFL, you want to go deep.

Okay?

And, and, and try to find good solutions quickly.

Okay, when does it prune?

It prunes as soon as you're reach a note

which who's evaluation is worth in the best found solution.

Okay?

And one of the questions I have for you

is, how efficient is it from a memory standpoint, okay?

And I'm going to always ask you questions like this during this class, okay?

And the key anyone you want to answer them is, you have to exaggerate, okay?

So, just assume, you know,

extreme cases and try to see all these things are working, okay?

So, how much space, you know, is a branch

and bound, is that first branch and bound going to take?

Okay, can you find, can you, can you find the answer to that?

Well it's very simple, right?

You always go left, left, left until you get stuck.

Okay?

So essentially the number of notes you can accumulate in memory

of one time is essentially the length of that particular branch,

which is this particular case is the number of items you can put in an upside.

So yes, it's actually pretty memory efficient because

you look at everyone of the item, you

have to do that because you have to find out whether you select them or not.

And that's what you select inside a particular branch.

Once you have, you know, explored that branch you

can remove some of these notes, and you would

select other ones by sticking the other branches, but

you always have essentially one branch at any one time.

Okay?

So, lets look at the next technique which is best-first branch and bound.

And to illustrate this, I'm going to use a

very, very simple relaxation, the one where we remove

the capacity constraint, because that allows me to express,

you know, illustrate a concepts in a better fashion.

Same, you know, same ratio of, you know, values weight that done before.

Same capacity for nap sack. Okay?

And once again all the notes, the values that I've accumulated, the space left in

the knapsack and the optimistic evaluation, okay.

So, initially best research, look at the

particular item, and then generate two sub-problems, okay.

Whether you select the item or you don't select the item, okay.

And now that first search, or best-first search, is

going to look at all the notes which are there, okay.

And select the one, okay, which is not close.

Which means we haven't explored, you know, its children yet.

Okay, which is the best evaluation?

And in this particular case, we take the one where we selected

the item, and which has a value of 128, right?

And we basically explore its, you know, generate its two children, okay?

One of them is infeasible, and the other one is a value 80, okay?

And now we basically have to consider

these three notes, one of which is infeasible.

So we have essentially to consider these two.

And we take the one which has the best evaluation, which is this one.

Okay, we expand the children again, okay, and what

we get now is these three notes, okay, which have

evaluated tree and, and then 35.

And once again we take the one which has

the best evaluation, 83, okay, and we expand it.

And we get a feasible solution there which has

a pretty bad value of 48, and an infeasible solution.

Okay, so at that point once again, you know, we will be basically evaluating,

taking the best note, the note which has the best evaluation for expansion, okay?

So it's going to, so this note we already know,

but I'll come back to that in a moment.

We already

know that we would never select it right?

Because it's worth in the best solution that we have,

but we expand this one and we find two solutions.

One with value 80 and one with value 45.

Okay, and this is the best solution that we have.

At this point we look at the best, you

know, note, which is not expanded inside a tree.

We see this guy, but you see this guy doesn't have to be expanded, which is

already worse than the best solution we have, we have found so far, so we can stop

the exploration at that point. Okay?

So that's best for search. Okay.

You always look at the note which has the

best optimistic evaluation that is the one that you select.

You expand, you know its children, and then you repeat the process

select the one which is the best evaluation and keep doing this, okay?

So, in a sense best-first search is always greedy, right,

always go for the best, okay, and expand that one, okay?

Most of the time when you expand that particular note,

you know, they will, their value may go up and therefore you

may go down and therefore you don't select that many more, okay?

When is best-first search pruning?

It's essentially pruning when, you know, you

tried all the nodes that you can expand

if a value which is worst than the best solutions that you have found so far.

At that point, you have all these nodes which are floating around.

They've not been expanded, okay, but it makes no

sense to actually explore any of them, so you stop.

And that's,

you know, when the computation stops. Now, is it memory efficient?

Think about it, okay, once again.

Exaggerate. Okay?

How would we be exaggerating in this particular problem?

Okay? Well we can be just city.

Right, suppose that, you know, the, the

optimistic evaluation is going to be amazingly optimistic.

It's going to give you plus infinity all the time.

So if you do that, how much space

are you going to use in best-first branch and bound?

Think about it, okay?

Essentially what you going to do is, take an oath.

They have all the same value, infinity.

You're going to expand one, okay?

And then you're going to expand the other one, and so on.

And you will have to expand all of them.

So, you're going to store the entire tree inside

memory, which is kind of a disaster, right?

Because normally you will take exponential time,

but you will also take exponential space.

And space is actually one of the main limits in computers these days.

Okay, so,

you know, you know this is, this is the

worst case for you know a best-first branch and bound.

Know you may ask, when is best-first branch and bound really good?

Okay? And once again, exaggerate, right?

And we can do the exact opposite exaggeration, right?

So you have the perfect evaluation, okay?

If you have the perfect evaluation, okay, then

you will select the minimal number of notes.

Okay, so you see a little

bit about what's best for branch and bound.

If the relaxation is really good, then, the, the, what,

the number that you explore would be little, will be,

you know, very small otherwise you, you will explore a

large number of notes, and these notes are inside memory.

Okay.

Now, let me talk about the last search technique that

I want to talk about today, which is limited discrepancy search.

It's actually a very interesting and amazing heur-, you know search strategy.

And it assume

that you have a good heuristic, okay.

Assume that you have a greedy algorithm which is really good, okay

and that it makes very few mistakes okay, that's what the issue.

The heuristic is making very few mistakes we assume that the search tree is

binary, okay, and following that heuristic mean,

its always going left, left, left, left.

Right, so you select item, you select the item, you select the item.

Okay, and branching right means the heuristic is making a mistake.

Okay.

So if you do this, okay, this is what,

you know, limited discrepancy search does, okay.

It wants to avoid mistake at all costs, okay.

So we basically explore a search space by increasing number of mistakes.

We first explore something which has, you

know, zero mistakes, one mistakes, two mistakes.

Okay, and what we're doing there is really trusting the heuristic lesson last.

Okay.

We start by trusting the heuristic, trying to avoid mistakes, and then

allow a certain number of mistakes and then more and more mistakes

until we don't trust the heuristic. Okay.

So in a sense the way to view this is that limited discrepancy search can be viewed

as a technique which is basically exploring the

search, this entire tree, through a bunch of waves.

The first waves assume that you make no mistake.

The next wave, you know, wave number one, assume that you can make one mistake.

And then wave number two, two mistakes, and then so on and so forth.

Okay? So let me show you that on

the exhaustive tree. Okay?

So you start at the root of use tree, and then you assume that you make no mistake.

You follow the heuristic all the time.

That means what?

Branching left, left, left, okay, and that's what you see there.

This is, you know, the first wave that you see there.

Okay.

Now the second wave is going to lower you form one mistake.

Okay.

So that basically means that you can only branch once, on the right.

Okay.

So for instance you can go here, okay, but then you would have to go left,

left, left, left.

Okay, and this is what you see in the first wave.

Okay, you go left, you go right and then left, left, left, or you go left and

then one right and then only left or left, left and then one right over here, right.

So this is what you explore in the second wave,

and there is something which is really interesting here, right?

So, this is half of the search space, this is the second half of the search space.

And what you can see here is already, in wave, in the second wave,

you are already exploring one particular configuration, which

is in the second half of the search space.

Which depth first search would never do, until, you know, it takes, it,

it, it has explored the entire first half of the search space, right?

And this is one of the interesting things about limited discrepancy search.

It actually probes the search space in many different places.

Okay?

Then the third wave is going to be makes

two mistakes that makes, that means that you can

take two rights and one left. Okay, and that's what you see there.

And that point we have almost explored everything.

Okay.

And then essentially the last web is going to explore this guys on the left.

Okay, so let me show you this example of the knapsack example as well.

Okay.

So we start from the configuration, okay, in wave one, we start from the root.

And we branch left only, boom, boom, boom.

And in this particular case, it's kind

of annoying, because you get into infeasibility

very quickly. Okay?

The first wave, okay, is basically, you can do one right.

And this is what you get, okay?

And, so you basically make one right there, with, you,

you make a mistake for, you know, refer back to the

heuristic, you let the heuristic make a mistake, and then you

go left, or you go right, there, and go left again.

And at that particular point, you find the optimal solution already.

Okay?

And then in wave three, you explore two mistakes for every one.

And most of these things are going to be

rejected, of course, because we have already the optimal solution there, okay?

So, limited discrepancy search.

In summary, trust the greedy heuristic.

When does it prune? Think about it.

When does it prune?

Why, it's exactly like in that first search.

When you see a note, okay, it does an evaluation

which is worse than the best found solution so far.

You know that you don't have to explore

it, so it prunes like in best-first search.

And no, here is an interesting question, okay?

Is it memory efficient? Okay.

So, compared to depth-first and best-first search, is it memory efficient?

Okay. Now this is a very interesting question.

You know why?

Because I even told you really how to implement this, okay.

And depending upon the way you would implement this search, okay.

There will be an interesting trade off between space and time, okay.

You can implement it very efficiently,

but it will take a lot of space.

Or you can implement it by doing redundant work and it will take minimal space.

So the implementation can be between

the best-first and the depth-first search approach.

Okay?

So think about it and think how you would do this.

This is a very interesting topic.

Now limited discrepancy searches on beautiful application is scheduling.

We'll come back to that and rounding as well.

So it's a very interesting technique when you have

a good heuristic, when you know what you're doing.

Okay? So,

let me conclude here.

So, we have seen search strategies here

and we have two class time about relaxation.

Okay?

The big idea last time was relaxation. The big idea today is search, okay.

Now how do you choose between them, okay.

This is a very interesting topic in optimization.

This is one of the most important topic.

You can find really strong relaxation, but they will be so slow that

you will explore a very small tree, but it take a long time.

Or you can have a relaxation, which is really strong.

The trees and a really fast computer.

And, the trees the size of your search base substantially.

So, you have to find, you know the right relaxation and

the right part of the search tree that you will explore.

This is a very interesting topic. Okay?

Most of this is going to be problem specific like everything in optimization.

Okay?

And finally, you know, there are many other strategies.

And, you know, I really encourage you to actually think outside the box, and

think, if you can find all the kind of strategies that are going to be good.

Okay? Think about it, okay?

So, at this point, this is very interesting.

We have covered, you know the knapsack problem entirely.

Okay.

It's time for you to start the assignments, okay, and we'll

go into more sophisticated techniques in the next couple of lectures.

Thank you very much guys.

Okay, so it's time to actually go to work and actually solve these assignments.

Bye.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play