LP 6 - duality interpretation and uses

Loading...

From the course by The University of Melbourne

Discrete Optimization

207 ratings

The University of Melbourne

Discrete Optimization

207 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

Linear Programming

Linear programming has been, and remains, a workhorse of optimization. It consists in optimizing a linear objective subject to linear constraints, admits efficient algorithmic solutions, and is often an important building block for other optimization techniques. These lectures review fundamental concepts in linear programming, including the infamous simplex algorithm, simplex tableau, and duality. .

LP 1 - intuition, convexity, geometric view23:44

LP 2 - algebraic view, naive algorithm13:41

LP 3 - the simplex algorithm32:21

LP 4 - matrix notation, the tableau20:51

LP 5 - duality derivation22:00

LP 6 - duality interpretation and uses17:00

Meet the Instructors

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

Okay, so discrete optimization, part six, last part, okay?

And, so what I am going to talk about today is where these, this dual coming

from and why it is useful, okay? So, we saw that it was beautiful, okay?

We have no idea, you know, where magically it came from, okay?

And so, that's what I want to talk about, you know, in this, in this lecture.

And then, I want to also tell you a little bit what it means.

How you can understand these things, okay?

What is the meaning of these dual variables, and then I want to talk about,

you know, what it's useful for. Okay, so this is, you know, the mod, you

know, understanding where it came from, okay?

So this is an example that I took from [UNKNOWN] book.

If you have to read two books on linear programming, this, this has to be one of

them, okay? So, what you see there is basically

linear programming. I'm maximizing my profit here, I'm

maximizing this objective function, you know, subject to these constraints.

Okay? And the, the question is that, you know,

I'm asking, you know, the question, you know, can I bound this maximum?

Is there an optimistic evaluation of that maximum?

Okay? And so what I'm showing you here is one

of them. I'm basically telling you here, okay?

That the maximum value that is objective function in everything is 110, okay?

Why? Okay?

So, look at this constraints and look at this one.

Look at these two constraints, okay? So, this is 55, this is 110, okay?

Double. Why?

Because I basically took that constraints and I doubling every one of the

coefficient, okay? So instead of adding 5, I get 10, okay?

Instead of there being 1, I get 2. Why did I do that?

Okay? Because as soon as I do that, okay?

So, what you can see, okay? Is that this 10 here, okay?

Is actually greater than the coefficient in the objective function.

This value is also greater. All the values here are greater than the

objective function. And therefore, I'm maximizing something,

which has to, so, so if this, is this is a value, this will have a larger value of

inter-objective functions. As a value, this has to be greater than

the value of the objective function by definition, okay?

And therefore, in this particular case, I know that 110, okay?

Has to be an upper bound, okay? I will never be able to get to, to, you

know, to get higher than 110, okay? So that's an upper bound.

Now this is a terrible upper bound, of course.

But I'm going to show you better ones, okay?

So, look at these two things here. I have two, I basically take these two

constraints. I add them together, okay?

If I add them together, I get this constraint that you see here, right?

So, you basically see here 4x1, you know, plus 3x2, and so on smaller equal to 58,

okay? So now, once again, you know, you can do

the same reasoning. You can look at all the coefficients that

you see there. And once again, they are always greater

than the coefficients inside the objective function, okay?

So, greater or equal, right? So this 4 is the 4 of the objective

function. The next one is 3 instead of 1.

So, I know that if I sum these two terms there, they will be smaller than the sum

of these two terms. I continue to doing the same way, right?

So the five in the objective function becomes six, okay?

And the three remains three, okay? So, I know that this value is always

going to be greater than the value of the, the objective function.

Whatever the value that I find for the variables.

But now, this time, the value here is 58. So, it's a much smaller value.

So, I know that 58 in this particular case is a bound to this objective value

already, okay? So, wow.

Okay. So, so what I'm showing you here is that

by combining these, these constraints. And by actually making, you know, making

sure that this combination satisfies the basic constraints.

They have to be greater than the coefficients of the objective function,

okay? I can actually bound the value of this

objective function, okay? And that's very nice, okay?

So in a sense, yeah, yeah, yeah, but what is the relationship of the dual, okay?

So, look. What I'm going to do is take an arbitrary

combination, positive combination. It's called conic combination, of these

constraints, okay? And so if I do that, I'm basically going

to use y1, y2, and y3 to find the coefficients of the way I want to combine

these equations, right? [laughs] Think of it, you know, why y1,

y2, y3, does that remind you of something?

Okay. So, I'm basically taking these y1, y2,

y3, okay? And then, I'm basically combining,

multiplying the, the various constraints that you have there, okay?

And I know, okay? I know that, you know, when, when I do

this combination, okay? So, I have to be smaller or equal to this

particular value here, okay? Because, you know, this other right hand

side of this constraint, okay? So, if I multiply these left hand side by

y, I have to be smaller or equal to that, okay?

So, I know that is I multiply this constraint by y1, y2, y3, okay?

I have to be smaller than this expression, okay?

Once again, you know, right inside, hey, objective function.

So, if I minimize this, okay? I know that the value of this because of

this combination has to be greater than the value of it's to be, it's to be

greater. I knew that these values have, would have

to be greater than this thing, right? But what I want to do is find the

tightest, the tightest upper bound. So, I minimize this, okay?

So, so I minimize, I want to find the y's that are basically minimizing the value

of this expression. That I want to be bonding this thing by

both, okay? Now I told you before, we have to satisfy

some constraints, right? So, when I look at these coefficients

there and multiply them by the y's, I have to make sure that they are greater

than the value of the coefficient in this primal, right?

So in a sense, what are these? Well, these are the dual constraints,

okay? So, this is the dual objective function.

These are the dual constraints, okay? So, the whole thing here, it's just the

trick to actually bound the value of this primal, okay?

So, the dual is basically bounding these values.

And that's what I told you before, right? So the other day, you know, what we were

doing is the primal might be minimizing, the dual was, you know, maximizing.

And basically, the dual was always the lower bound to the value of the primal.

Here, I'm basically maximizing. Of course, the dual is minimizing, and

I'm always telling you hey, hey. The primal, the dual here has always to

be an upper bound to the value of the primal, okay?

And this is a systematic derivation of why this is true.

Of course, once you relax, ooh, this is an interesting linear program, you can

start whether the properties of these thing.

And that is essentially what I have shown you last time, okay?

That the value of the objective function of the primal at optimality is equal to

the objective value of the dual of the optimality.

So, this value here that you are minimizing is going to be exactly the

optimal value of the primal, okay? That's how you actually find the

derivation. You know what?

Where this dual is coming from essentially, okay?

Now, so this is, so I'm going to talk about complimentary slackness.

And this is essentially starting to convey what these dual variables mean.

And so in a sense, this is a topic which is, you know, a very interesting topic in

mathematical programming. In general, this is applied to linear

programming only, right? So what you see here, what basically

these equations are saying, is that if you have x star and y star.

Solutions to the primal and the dual, you have to have these conditions which are

satisfied. And I'm going to go over, you know, over

that. But essentially, what it means is that if

you look at the constraints of the primal, this is the constraint of the

primal. It's an equality, right?

And if this, this inequality of the optimal solution is tight.

So, so it has to be the case that either this inequality at opt, of the optimality

has to be tight. Or the dual variable has to be zero,

okay? So this is linking the primal val, the

primal solutions, the primal optimal solution.

And the dual of, you know, optimal solution.

And basically saying oh, either that constraints in the primary state or the

dual variable is zero. And this essentially expressing the same

thing for the dual, right? So, all the constraints in the dual is

tight, all the primary variable is zero. Okay, very interesting, okay?

Very interesting ratio between these things, okay?

So, you can guess which values are zero in the other side depending upon the way

that the constraints are tight, okay? Now, let me give you an economic

interpretation of this, okay? So once again, you know, I'm looking at

this program, okay? This linear program, and we are

maximizing so think maximizing profit. Now you have constraints, okay?

For instance, the constraint could be production, you know, capacity

constraints on your production, okay? So basically, this bi over there, okay?

Is telling you oh, this is as much as you can produce, okay?

So basically, you want to maximize your pro, profit.

This is what you can produce, okay? But, we are limited in what you can

produce, okay? So, look at this ti there.

So, what I'm looking at here is ooh, assume that I can increase my capacity

production a tiny bit, okay? What's going to happen?

And this is essentially what this dual variables are telling you, okay?

So, if you increase your capacity a little bit, okay?

The value of the, the objective function is going to change tiny, you know, in a

tiny fashion, okay? Is going to still be the, you know, still

be at least be as good as the primal objective function that you see there is

z star. But then, you're going to increase it

with what, with, you know, ti times yi star, okay?

For everyone of these dual variables. So, which basically means that, if you

increase the capacity of these various, various constraints on the capacity,

okay? I can, I can increase the value of the

objective function by multiplying this increase by the value of the dual

variables, okay? So, the dual variable is, in a sense,

telling you a much Increasing that particular capacity.

You know, relaxing that particular constraint, is bringing to the objective

function, okay? Now, this is only valid when ti is

sufficiently small, right? Because at some point, if you make this

ti sufficiently big, you may change basis, and so on and so forth, okay?

But this is essentially, this is essentially telling you, you may change

fundamentally the nature of the solution. But here, when you're very close, this is

what this is basically telling you, okay? So one last thing that I have to tell

you, duality in the tableau, okay? So remember you know, when, when we

presented the tableau, you always start with a basis, okay?

So, when you start with a basis, okay? So, you know that at the end of the day,

when you are at optimal solution. This other value of the objective

function, okay? Now, when you look at, when you have the

first basis, it's either the artificial variables.

Or a basis that you found after the first phase or something like that.

You have this basis and assume that these are, let's say artificial variables,

okay? The cost of this things is zero in the

objective function, okay? So, what do you know?

You know that when you look at this formula, the cj has to be zero, okay?

You also know that this matrix here, Aj, you know, this is the unit matrix, this

is a unit thing, okay? So essentially, what you have here is

that what remains of this is basically the value of these guys.

So, cBAB minus 1 which you recognize as the simplex multiplier, right?

So in a sense, the cost here, so what you will find in those locations are the

simplex multipliers. Which are the dual variables, okay?

So essentially, what you see there is that the, if you solve the primal, you

can always look inside your tableau. And you will find the value of the dual

variables. You will find the solution to the dual

variables. So, not only you know that the dual is a

particular cost, but you can actually retrieve the value of the dual variable

to its optimality, okay? Now, why is this thing useful?

Okay, so, so we have this beautiful theory.

We know where it comes from. We know what it means from economic

standpoint, for instance. But what does it correspond to?

Okay? So, so let's look at this example, okay?

So, we have a primary which is visible, okay?

So, the dual is not visible until you get a optimality.

So, you start your primary. You start minizining.

So, because essential, so, so you have to think the primary always visible I get

down to a point. In all these things, the dual is

infeasible. And at some point, you get to the optimal

solution. The dual become optimal and at the same

time feasible, okay? So the dual, so when you do the dual

simplex, okay? So, the dual is always feasible and the

primal is not until you reach optimality, okay?

So in a sense, what I'm telling you, that we can solve the primal.

And then when, add optimality of a solution to both the primal and the dual.

Or you can solve the dual, and then add optimality of a solution of a primal into

the dual. So, which do you do, okay?

Well, there is one case where it's actually very useful to use the dual,

okay? So, assume that you optimize the primal.

Okay, you optimize ta-ta-ta-boom, you have the objective, you have the optimal

solution. And then somebody comes and says ooh, I

forgot to tell you, I have this one constraint, okay?

And obviously, the constraint is satisfied, it's not interesting.

But assume the constraint is not satisfied, what's going to happen?

Okay? Well, the dual, okay?

Is going to be feasible. Why?

Because if you look at these constraints in the dual, what is it?

Oh, you flip, you know, and then it's the variable, okay?

So, if you are the variable to the dual, you know, of course, you know, this, the

dual is still feasible. You can give a zero to all these

variables and you have the same solution, right?

The primal is not feasible, it's constraint is violated.

So what you can do is to say ooh, but my dual is feasible, so I can optimize the

dual. [SOUND] I get to optimality and at that

point, I know that the primal is going to be feasible, okay?

So in a sense, if I'm adding a constraints to a primal algorithm, okay?

And, and obvious this, obviously, if these constraints is, is feasible, I

don't have a basic feasible solution to start from in the primal.

But I have one in dual. And I can optimize the dual, get back to

optimality, and there I know that the, the primal is, is, is going to be

feasible and optimal, okay? So in a sense, if I have an optimal

solution to the primal, [SOUND] I add the constraints, and that constraints is

violated. I can optimize the dual to get back to

optimality and feasibility by using the dual algorithm.

Very nice, okay? You will see why this is very nice in the

next couple of lecture when you do, when we do mixed integer programming, okay?

Now, the other things that we can do is that actually, you know, you can do

primal and dual on exactly the same tableau, right?

So remember, you know, we have this primal, we have this, basically, this

primal over there. And basically the dual is what?

The dual is taking the objective functions of the primal, okay?

And putting it as a right end side, okay? Where is my right end side?

Here, right? So, we can do the same thing for the

objective function, right? So, this is the right end side of the

primal, it becomes the objective function of the primal, okay?

And then, you have this big matrix, okay? The only thing that you do, [SOUND] you

transpose it, right? And so, that's what you have here.

These two things are the same, okay? And so, when you have the primal, assume

that I don't have this representation of the dual, right?

I see only the primal, right? But if I want to see the dual on the

primal, I do this, right? And know I see the primal, right?

So, in a, I, I see the dual, right? So, in a sense, I don't need this guy

because it's already there, right? It's, you know, it just, you know, a

different way of looking at it. So, now look at this.

If I do, if I do the primal algorithm, the primal simplex, what do I do?

I select an entering variable and then I select a leaving variable, okay?

So, that's the primal algorithm. If I look on the other side, what does it

mean? Ooh, it could mean in the dual, I would

select then living variable, and then an entering variable.

It's another way of doing it. It's fine, right?

Because it's going to do a pivoting operation in exactly the same fashion,

okay? And when I do the dual, right?

If I select an entering variable in the dual and the leaving variable, and then

the leaving variable to the dual, what does it correspond to?

Well, the leaving variable on this guy is the entering variable on the primal and

then vise versa. So, these things are the same, okay?

If I pivot here, I have the same pivot here.

If I pivot there, whoops, I have the pivot here, right?

So when I add a new constraint and it's violated, and I'm looking at the dual,

what do I do in the dual? I'm adding a, I'm selecting a constraint

to enter the basis, and another constraint for leaving the basis.

Which basically means that here, you know, I'm also selecting a variable.

But this time, a primary variable to lead, to enter the basis, and another

variable to leave the basis. So when I, when my constraints is

violated in the primal and I look at the dual, the dual is basically fine.

You know, I am basically, you know, doing a pivot operation here.

The same thing happens here. But of course, I never have to use this.

I can always use one of the tableau and do all of the things.

I just have to, you know, turn my head and then it's fine, okay?

So in a sense, that tells you, and of course, you could do some steps in the

primal, some step in the dual. And you can do all kinds of beautiful

things, right? So, using the same tableau, okay?

So, this is the relationship with this primal and dual.

And these things, you can exploit, and we will exploit them.

And I'll, you know, you'll understand, you know, more of this when we do mixed

integer programming. But the fact that we have these two

things is really very useful, okay? So next time, we're going to move to

mixed integer programming, okay? Which is going to be the, you know, the

third big approach to combinatory optimization.

And it will obviously rely on linear programming.

Thank you very much.

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.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play