Knapsack 3 - modeling

Loading...

En provenance du cours de The University of Melbourne

Discrete Optimization

252 notes

The University of Melbourne

Discrete Optimization

252 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 guys, welcome back, discrete optimization.

But still the knapsack problem, but today we're going to talk about modeling.

Okay, so whatever I'm going to say today is going to

seem very, very simple, but there are some deep

truths and deep knowledge in what I'm going to talk

about, but they will seem to be completely natural.

But we'll come back to them later on, and you'll see why

some of the things that I'm going to say today are actually important, okay?

So the first thing we're going to do is talk

about how to formalize an optimization task as a mathematical model.

This is the key, okay, so this is the key for actually solving these problems.

You have to be able to model them mathematically

why, you know, let me give me an example.

You talk with industry, you talk to people, they start

describing your problem, and you think you understand it, okay?

And then you come back with a beautiful solution and

tell you you know you can't do this, that's the constraints.

But they didn't express it the right way or they forgot

to tell you.

And essentially you come up with this

beautiful algorithm that really doesn't apply in practice.

So what you have to do first is always find

a description of the problems that everybody can agree upon.

Okay? This is the first step.

What is it that we are trying to solve?

And that's what I'm going to talk about today.

Okay, so lets do that for the knapsack which is very simple, but that's

going to give you an idea on how we do that for a very complex problem.

So, we start with a set of item, capital I, that's all the items

that we can actually put in the knapsack and

then for every one of these item, I, okay.

We will have two piece of information, okay?

That's what we've seen in the greedy algorithm so far, right.

The weight of the item, okay, and the weight of the item, and the

volume of the item, that's the two things that we know for the items.

And then the only piece of information that

you need, is also the capacity of your knapsack.

This is the input of your problem.

That's what you need to actually start formalizing it.

And now the problem is really finding a

subset of these items, Okay, which has maximum value.

You want to maximize the value of the

items that you are picking up, but you don't

want the weight of the items that you are

picking up to exceed the capacity of the knapsack.

Okay?

This is still informal and we're going to start

formalizing this in the next couple of slide.

But this is the start of formalizing the problem.

Okay?

We know the input, okay? So, how do we model this?

The first thing you have to do every time you are trying to

model an optimization problem is to find out what the decision variables are.

And you're going to say, oh, but what is this thing.

Essentially this is something that's going to capture

the real decisions you are interested in, okay?

In practice for instance, in this particular case

for a particular item what do you want

to know, you want to know if you select that item or if you don't select it.

lf you put it in the knapsack or if you don't put it in the knapsack.

That's what you want to, to decide, and

that's the decision variables will correspond to that.

Okay, so once you have these decision

variables, you can start doing things with them.

And one of the really important things that you

have to do is basically model the problem constraints.

And these problem constraints are going to tell you

what you can do and what you cannot do.

What is a feasible solution?

A solution that people will tell you, yes, yes that's the solution,

not something no, you forgot something, It's basically capturing

what you can do, what is the feasible solution.

Okay?

It's basically define the, the set of things that people will accept as

a solution, and then the last thing of [UNKNOWN] you have to define

your objective function, what are you trying to maximize or minimize, and in

this particular case the knapsack is going to maximizing the value of your items.

Okay, the objective functions is defining the quality of your solution.

The constraints

are defining what is a solution and the decision variables are

telling you what to decide, what you will decide upon, okay?

And so essentially, the result of these

three things together is an optimization model.

It doesn't tell you what to solve or what, how to solve the problems.

It tells you, it tells you what the problem is.

Okay, now a very important point here, is that there are many,

many ways of actually modeling a

particular optimization problems, and this is

part of the beauty, okay?

So in a sense I'm basically telling you its specify what we want to solve but

implicitly you are already making some choices, and

it can restrict how you will solve the problem.

So you have to be very careful when you do this.

There may be many formulations, they may be translated

from one to the other, but essentially they will

capture the same problem in a different fashion, and

they may influence the technique that you will use.

So you have to keep an open mind when you model the problem.

Okay, so, we'll come back to that many times,

present different models of different problems

for, you know, for practical application.

Now, the, in the knapsack problems, the

decision variables, here are the decision variables.

For every one of the items, you will have a variable xi.

For item i, you know, variable xi will denote whether you select the

item or not, whether you put the item inside the knapsack or not, okay?

So xi will be equal to one if you select the item.

It will be equal to zero otherwise.

Okay?

So, so the goal of the optimization model will be to find the values of all

these decision variables, whether you assign a one

or a zero to every one of them.

That's going to be the goal, but these decision variables when you

see the value of them you know what to do, okay?

Every one which is every item, decision variable which is a

one you know that you want to put them in the knapsack.

The ones which are zero, you don't. Okay?

So the problem constraints have to be expressed now in terms of

these decision variables.

And this is one of, this is the only, you

know, feasibility constraints that you have in this particular problem.

What does it say?

It basically makes sure that the item that you select, they will

have an xi equal to one, don't exceed the capacity of the knapsack.

So basically what you do is you sum this product, okay, which is a constant,

which is the weight of the variables and

then whether you select the variable or not.

And that summation

here has to be smaller than the capacity of the knapsack.

And you know, when you don't select the item, you

know this, you know this product is not contribute anything.

When you select it, it will contribute the weight So essentially this make sure

that you never exceed the capacity of the knapsack with the item that you select.

Okay.

Now essentially this constraint defined all the feasibility constraints.

It basically makes sure that the item that you

selected will not exceed the capacity of the knapsack.

And then the last thing that you have to do

is express your objective function and we use a singular

you know, expression, we multiply every one of these decision

variables by the value of the item, the corresponding item.

We've summed them, and we have the full value of the knapsack, okay?

At this point, we have the decision

variables, the feasibility constraints, the objective function.

We have a complete model.

This is the complete model of the knapsack.

You see the value

here that you are trying to maximize.

And you see the capacity constraints over here and

then you know that every one of the decision variables.

It took a value of zero or one.

You take the item or you don't. Okay?

And so this constitutes an optimization model.

Everything here is formalizing what you want to do.

You know exactly what's going to be a solution and

you also know the value of every one of these solutions.

What remains to be done, is what? Is finding these,

this, the value for these decision variables.

Now, now you can look at these problems and

you can start, but wow, how many solutions are there?

And in this particular case what you can do is enumerate

all the possible configuration for the values of the decision variables.

Okay?

So you can decide for instance, that you select no item,

you know, that's not, not going to give you very much value.

But this is one of the things that you can consider, or some configuration where you

see like one item or a com, or the

combination with two item, three items and so on, okay?

This is essentially your search space.

When you look at the decision variables

the value that you can take, the contingent

product of these guys are going to give you

all the configurations that you have to consider.

Okay? Not all of them are going to be feasible.

Some of them are going to violate the capacity constraints, and

that's going to be the feasible part of your search base.

Okay?

So this is going to give you the search base.

This is the feasibility

region in a sense, okay. And how many are there?

Well essentially in this particle or case the number of configuration,

if you ignore the ones that are violating the capacity constraints.

It's going to be two to the number of item and that's a huge

numbers if the items are actually, if there is a large number of items, okay?

So, so let me give you an idea of

how many and how fast this, this value is increasing.

Assume that it takes one millisecond

to test a configuration, to test if a configuration is feasible.

And we try to enumerate all of them, test, and then we want to select the best one.

We just, you know apply a brute force algorithm to do this.

If it takes one millisecond to test any

configuration, and you have 50 item, okay, it

will take that number of centuries like, you

know, more than a wow, that's a huge number.

It's more like a billion centuries to actually solve this right?

So, this is huge okay, so you can't solve the problem this way,

and what this class is about is exploring these configuration in a smaller way.

Okay?

And still finding optimal solution. Okay?

Or in a sense finding a very high quality solution that

you can say is very, very close to the optimal solution.

Okay?

So next time we're going to start looking at how you can actually do that.

How you can find optimal solution to the knapsack problems

in reasonable time. Okay, see you next time, thank you.

[BLANK_AUDIO]

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.

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

Télécharger dans l'App Store

Disponible sur Google Play