0:00

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.

Â 6:48

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]

Â