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.
Column Generation - branch and price, cutting stock
Loading...
來自 The University of Melbourne 的課程
Discrete Optimization
251 個評分
從本節課中
Advanced Topics: Part II
These lectures continues to cover some more advanced concepts in optimization. They introduce large neighborhood search, which often combines constraint programming and local search, and column generation which decomposes an optimization model into a master and pricing problem, using more complex variables.
與講師見面
Professor Pascal Van Hentenryck
Dr. Carleton CoffrinAdjunct Lecturer
Computing and Information Systems
Okay, guys. Discrete optimization, this is the, these
are the advanced topics now. They are beautiful.
You should really look at them. But, you know, they are really the
advanced topic of this class. Not strictly mandatory in a sense.
But, you know, they are really nice, so please look at them.
So, so I'm going to talk about column generation, okay?
So, and I'm going to give you a big intro it's kind of one-slide introduction to
tell you what the spirit of it is. And then I'm going to show you the
original example where this was introduced, which is cutting stock.
Okay? So, in a sense you can think about branch
and cut, as we are going to solve this MIP which has an exponential numbers of
constraints. But of course, we don't explore them or
we generate them, you know, one at a time.
Okay, on on demand based on the value of the linear relaxation okay.
So in the particle TSP we were generating the subtour constraints or is com
constraint on demand. Column generation is just another, is,
it's the same idea but reverse. Right so in solving exponentially many
constraints we going to have exponentially many variables.
Okay, and so we want to sort this LP with exponentially many variables.
Okay. Wow that looks crazy right.
But of course we want, we want to list all these variables we're going to
generate them on demand again. Right and so the key point here is that
the variables are not are going to represent complex object nor the simple
decisions that we had before. And I'll talk a little bit about branch
and price which is kind of the use of column generation in branching scheme at
the end. But a key idea would be essentially to do
a branch and bond but using column generation at every one of the nodes.
Okay? So, so this is, this is the cutting stock
example, once again. It came from Gilmore and Gomory.
The same Gomory as the Gomory course of course.
You know, a lot of contribution to coming out of optimization.
And this is, this is what the problem consists of.
So, you have large, you know, wood boards, okay?
Really large, okay? of a particular length.
Okay? And you have you know a large number of
them and you want to cut them into small shelves of different sizes.
Okay and these small shelves are what your customer require.
They don't want very long thing that they are to cut at home.
They, there are ones that are right you know more or less the right side.
the right size, okay? And so for every one of those different
types of shelves, okay. So you have a demand of the popular
customers. You have the length of these shelves and
then the demand of the customer, okay? And so what you need to do is to find how
many boards, you know, big boards you need to actually meet the demand of your
customers. And you, how, and also you want to know
how you have to cut the big boards to actually get to that solution.
Okay, so that's the problem. Okay I'm going to you know show it
visually because it's much more clearer visually.
So these are the big board, that are not that big in the example.
But these are the long boards okay. And these are the types of shelves that
you want to cut okay. So this board here is a length of 110
okay. And so the smallest shelf here is you
know is size 20 the largest is 75 and there are a variety of other sizes in
between. Okay?
And so for every one of these yes, you will have a demand.
Okay? Your customers want 48 of the small
shelf. They want eight of the longer, the
longest shelf. Okay?
And so, so, so, you want essentially to meet the demand of your customers and you
want us to know how you have to, how many of these big boards you want and how you
cut them. Okay?
So this is a particular way to cut them with two of the no, shelf size.
You know, shell size, size 20 and 75. And obviously, you know, the sum of this
is 95, so it fits in the big board. It's one of the valid, you know,
cuttings. This is another cutting which is, you
know, one of five. You know, 50 and 55.
And this is another cutting, you know, 20, 20, 20, 20, 20.
Okay? And so basically what you want to do is
look at these, look at these, look at the various ways you want to cut these
boards, so that you minimize the number of big boards that you are using.
Okay? So this is the first MIP model that I'm
going to show you. It's going to be a terrible model, okay?
But it's the first model that comes to mind, right?
So what you want to do is you want to decide if a particular board, you know
its selected in the optimal solution or not.
So board b is going to be selected. Okay and then you will have a particular
variable x as b which is, going to tells you tell you how many shelf of size s are
basically cut inside are basically available from the cutting of board b.
Okay so if you have for instance 20, 20, 20, 20 you know that's four times, lets
say 5 times 20, you know that's going to tell you that size 20 is cut 5 times in
this particular, in this particular board okay.
So you have five you know shelves of size 20 in that board okay.
Now the constraints that you will have to express inside the may bag are going to
be you know the typical constraint that your having you have these two types of
variables. One of them is going to say oh, I can you
know the board is going to be cut if I. If I actually, board b has is to be cut,
if I'm actually, you know, delivering some shelf from it.
Okay? The second thing that you want is to make
sure that the sum of the things that are basically cut from a bottle of board
don't exceed the size of the board, and then you have to meet the demand of the
customer, okay? So, and the objective of course is to
minimize the number of boards. So, this is a MIP okay, which is
describing that, okay, so you look at the boards, okay?
The set of boards, okay, and you basically minimize the number of them
that you select, okay, simple objective function, [UNKNOWN] zero one variables.
Whether I use a, board b or not, okay. Now, if I'm, so the first set of
constraints is basically telling you that if you are not using board B, you can't
get anything from it. That's what this constraint is using, we
use a big M notation then you basically have you know, x, yb, yb you know,
multiply by M and that basically constraint the value yb multiply by M and
that constraint the value of x as b so if yb is equal to 0, x sb has to be equal to
0, okay? The second type of constraint, second set
of constraint that you have there is basically a capacity constraint.
For every bin, if you sum. The set of the, if you sum the set of
the, of the, of the, if you sum the set of the shelf that you're cutting from
this board, you know, it has to be smaller than the length of the board,
okay? And then you have essentially here the
constraint that is saying you have to meet the demands and then you have the
basically the 0, 1 variables that you have there.
Okay. So, this is the first model that comes,
you know, to mind and one of the things that you see here, is, yeah, so you see
all the, all the types of constraints. And you wonder, you can wonder, is this a
good model or not? Okay?
And the answer is no, this is a terrible model, it has a very bad linear
relaxation. Okay?
And one of the things that you can notice immediately, is that it will have a lot
of symmetries. Okay?
So, essentially, all the boards here. Okay?
All these boards are basically interchangeable.
Which basically means, that if I ever can't figure a cutting with some of these
boards I can just permute this and I have you know a another set of boards.
And as soon as you have something like that in the MIP it's terrible because the
MIP can, you know, even if you have a good bonding you still have to explore
this, you know, rhythm and solution. So you will have to try to break the
symmetries as well. So this is a very bad model actually.
Okay, now one of the question you may ask yourself is that, oh, you know, how many
board do I need, okay. Now there is a very simple upper bounce
of the number of board that you need and you just sum, you know, the demands and
in the worst case you would have board for every one of the demand okay.
So in a sense there is easy upper bound for every one of these things but even
that upper bound this is a very bad model okay.
So what we going to do is move to hyper space okay.
So like in star wars. Okay so we are going to change completely
the way we view this problem okay. And instead of adding these binary
variable you know zero, one whether I use that board or how many items you know how
many shelf of that type I'm cutting with in that board.
I'm going to reason about cutting configuration okay.
So I'm going to say okay this is one way of cutting this board okay.
Do how many of these guys do I select. So I'm not looking, it's very simple
object here. I'm going to look at really complex
object that tells me how I can cut the big board okay.
And so once you have that okay, so will decide which of these cuttings you will
select. To meet the demand, okay?
Now, how is one of these configurations selected, or represented, or
characterized? Essentially, what you have to say is, oh,
this is a configuration that cuts this amount of shelf one, this amount of shelf
two, this amount of shelf n, and so on. Okay?
So, what you need to do is basically specify only, oh, I have a cutting.
This cutting is providing me that many shelves of this type, that many shelves
of that type, and so on. Okay.
That's what I'm going to reason about. Okay.
So, every one of these configurations is basically telling me the various shelves
that I get from it. Okay.
And so, we can find all these configurations.
Okay. We going to discuss how to do that.
But we can find all these configurations. Okay.
And so now, instead of reasoning about, you know, whether I can, how many, he's
just bored, use, and how is, you know, how many of these types of shelves are
cut in the board I'm really using this configuration.
I don't want to reason about these cuttings anymore.
I'm just reasoning I have them, I'm just reasoning about the, the which
configuration I'm going to select. Okay the decision variables are going to
be for a particular configuration c, Xc that's going to be the decision variable
and Xc is going to denote how many times in the optimal solution or in a high
quality solution. I'm selecting that particular type of
configuration okay? So, this is the model, very simple now,
oh, you know, we got rid of all these variables.
Okay. So, what we are saying here is that we
want to minimize the number of boards that we cut, that Xc for every one of the
configuration, how many of these do I select?
You take the sum of this, you want to minimize that.
Okay. Minimize how many of these, of these you
know configuration I'm selecting. So, that's what, you need to think about
them, okay? So this is the number of configuration of
type C. Okay?
The sum is the old, the total number of configurations that I'm cutting.
I want to minimize that. Okay?
And then your only really one constraint. Okay?
Which is how many, you know I need to meet the demands.
Okay. Well how do you do that?
Well you know you have the number of configuration of type you know of type Xc
that you that you are cutting. Okay everyone for every one of the types
of shots that you are requesting is going to give you a number which is NCS.
Okay, NCS is telling you the number of shelf of type S, that configuration c is
providing. Okay, so if you multiply these two, you
have the number of type shelf, of shelves of type S, that are produced by all the
configurations C that I'm producing, that I'm carrying.
And then that has to be greater than the demand for, you know, shelves of type S,
okay? And that's what these constraints is
doing. So once I have this configuration, you
know, I want to minimize the number of them, okay, that I'm selecting, and I
want to meet the demand, okay? And obviously, you know, these values
have to be integers. Okay?
The number of shelves that I'm cutting. Okay?
So this is a much simpler, this is a much simpler model, MIP model okay?
It has also a very strong relaxation. Okay?
And so one of the things that you have to see here is that we got rid entirely on
the capacity constraints on the big board.
Why? Because they are built inside the
configuration. My configuration are valued cuttings.
Okay? So I know that these are rep, that these
are good cuttings. Okay?
They are valid cuttings, they are cutting the big board.
Okay? In pieces.
Okay? And the only thing that I am doing is
really selecting which one I want. Okay and then there are no symmetries
here. All these configuration are different.
I'm just picking the right sub set of configuration.
So I got rid of all the symmetries. I got rid of all the capacity constraints
and I have a beautiful strong relaxation. Okay?
Now I told you that we moved to hyper space right?
So we are basically looking to this the, to the cutting configurations, okay?
Now it's simple zero one variables, okay? How do we find this configuration?
The only thing that we need to do is basically satisfy these capacity
constraints. Every one of these configuration when it
provides a number of shelves of different types that it's providing has to satisfy
this configuration. And this is a very simple constraint,
right. So if we are trying to characterize some
configuration. Okay.
We are going to look at this number and ask, so how many of shelves, of type S,
are we producing in that configuration. And we obviously want to make sure that
when you take the, this type S multiply by size ls, you want to be sure that your
smaller than the length of the big board okay.
So you want so every one of these configuration is going to satisfy that
okay. So we can enumerate the order.
So it's very easy to find this as kind of a simple nap sack constaint with no
objective right. So we can enumerate all these constraints
but in a practical problem, okay. So you will have billions and billions
and billions of them. And so we can't generate them all at the
beginning. And just solve you know the MIP problems
that I've shown you before. So we going to do is you know the same
trick as we did for branch and cut. We are gene-, we are going to generate
these configurations you know one at a time on the mat okay.
So we're going to solve a linear relaxation and then we're going to say
ooh, can I improve this linear relaxation by generating a new configuration okay.
And what happened so, this is the essence of column generation, okay.
It's basically saying, ooh, are these the next configuration?
Or in terms of the linear programming relaxation, it's going to be, what is the
next column that I have to generate? Okay?
So, so this the tableau at a higher level, right?
So you see in this particular case all the variables, which represent the
configurations. So, every one of these column, in a sense
is a configuration, and that configuration is telling you, you know,
how many of this types of shelf, you know, we are producing.
Okay in that particular configuration. So in a sense this big matrix here is
telling you, you know, for a particular configuration how many of these various
types of shelves I'm producing. Okay, and of course, the decision
variables are these Xi, how many of these things we do.
And obviously when you try to have a, you know, the constraint that you are
representing is that the sum of these guys on a particular row has to be
greater than or equal to the demand, okay?
So let's say that we have a bunch of configurations, we solve the LP, we get a
good value, okay, okay? And then we say, ooh, can we improve this
linear relaxation? And what you do is basically say, ooh,
can I find a new column, which when I add that column, okay, I'm going to get a
better linear relaxation? Okay, so you don't want to generate
arbitrary, you know, configuration, you want to generate some of them that will
improve the value of the objective function.
Some of them maybe completely terrible, they are cutting face that you don't
need. You want to just to look at the
particular configuration that because they have a good mix of different types
of self, will improve the linear relaxation.
Okay, that's the goal. Okay, so how do we do that?
Okay, so essentially, you know, a configuration is a column inside the
linear relaxation. Okay, so what is an interesting
configuration? Well, it has to be a co-, a conf-, a
column that whose variable, when I'm adding it inside the linear relaxation,
is going to enter the basis. Okay?
It's going to improve the linear relaxation.
If it's not entering the basis, you know, why would we put it in there.
If it's already optimal, we are adding a column, you know that's basically, not
entering the basis, going to stay the same place, that's terrible right.
So what you want, is to add this column so that they enter the basis and improve
the value of the linear relaxation. Okay, so essentially the way you know
because we cover linear programming before we know that to do that you need
essentially a configuration with a negative reduce cost okay.
So if it's positive it's not going to to enter the basis, if you want a negative
you know reduce cost. What is this cost, this is the ugly ugly
formula that we saw in linear programming, actually it's beautiful but
it's kind of messy. Okay.
So, we going to ignore the constant term, we goonna look only at this term.
Okay. So, let's zoom on it.
Okay? So, this is the part of it which is
really interesting. Okay?
The constant, you know, part, we are not interesting to for, interested in for
generating the new column. You look at this thing, okay, you
specialize it to the problem, which basically means that the constant here,
the C, is going to be one, that's, you know, the cost of one particular
configuration. Okay.
They are all the same, these boards okay and then this the configuration right.
So the configuration is going to specify okay how many of the various types of
shots we will be producing okay. And then you multiply that by CB and you
know the inverse of the basis at this point in the linear relaxation okay.
So we are looking at this thing okay. But what is this guy okay.
We know this guy right? So we know this is essentially you know
the simplex multiper or the dual varibles of the linear relaxation.
Okay, so when we are looking at this, this is essentially, this is essentially
what we will want to become negative okay.
We will want to find a configuration here, you know, which produce these
different types of shelfs which when multiplying by the multiplier I'm
going to make this whole expression negative such that it enter the basis.
OK of course I don't know this and so this is what I want to compute.
I want to compute this really nice configuration such that this expression
using the dual variables are going to give me a number such that that
configuration is going to enter the basis.
Okay so in a sense these multipliers these simplex these dual variables, I
have them. Okay they are already inside my tableau.
Right so I told you how to get that when we talked about linear programming.
So I have these guys, okay so I'm looking at defining these values here, I have
these guys and I have one, okay. And I, I and I know I can try to find
these ends you know using this, you know durable variables search that I will be
able to have a configuration which end to the basis, okay.
So what I'm really doing here is solving an optimization problem, right so I want
these two conditions I want you know a valid, you know cutting of this board.
And I want you know that particular cutting, that particular column to enter
the basis as soon as well when I put it inside the simplex table.
So the feasibility is what I told you before you know I told you that we could
generate billion and billions they have to satisfy this constraint which
basically means the cutting is valid this ns times Ls.
You know, when you sum that, it has to be smaller than the big board, okay and then
I have this quality criteria which say. Ooh, you know, this ns that I'm looking
for, you know, when I, when I used to do variables, when I computed reduced costs,
there, this reduced cost has to be negative, and therefore this part of the
configuration is going to enter the basis, which means we're going to select
that configuration. Right?
And so what you end up doing is solving this beautiful, you know, optimization
problem again, okay. And so this is a problem here where we
are basically basically solving a pro, so we're basically minimizing the value of
the reduced cost. Okay.
So we are trying to meet you know, the capacity constraints of the way, you are
making sure that we are cutting this board in the right fashion.
And obviously this ns has to be integer value.
So this is, this is a, this is a mid problem that we are solving, okay?
Now, if we optimize this, okay, if we optimize this map again, okay, and the
value is small, is negative, then we know, okay?
We know we have a column that's going to enter the basis.
So, great! So, we have a new variable, in a sense.
Okay which will enter the basis and improve the linear relaxation.
Okay? Otherwise, that means that none of them
exist. You could have, you know, exponentially
many of these things. It's billions of things that remain.
You will never improve the linear relaxations.
That means that you have the best linear relaxation at this point.
Okay? So now look at this MIP problem, okay,
can we solve it efficiently? What does it remind you of?
You know once again this is going to be an outside problem.
Okay and so we can solve this problem very very quickly and therefore you know
essentially generating a new column here which can enter the basis is going to
mean I have to solve this outside problem.
Once again we are basically closing the loop with the first lecture, right?
So this how we do column generation then. Okay you generate an initial set of
configuration. For instance we can use one configuration
for it's shelf type and try to pack as many shelf of that type.
Okay. Then you solve the linear program, okay.
So using the existing configuration, if you have an integer solution of [UNKNOWN]
stop, okay. otherwise what you're trying to do is
basically trying to see if you know find a new column find new variable that will
improve the linear relaxation. To do that we have to solve this simple
knapsack problem okay. And so if you solve, if you find these
new column okay, you'll repeat at step two and then you'll continue improving
the linear relaxation adding more and more and more variables.
Okay? Now, once you can't do that, okay, so
what you do, essentially, is that you, one of the things that you can do, and
you do for cutting stock because the linear relaxation is very strong, is to
simply round up all the value of the shelf, of the end variables okay.
Because essentially, you know, that will increase a little bit the number of
shelves that you can because these variables can be fractional.
Okay. so this is an example, so we basically
have this big board. You have the various types of various
demands for various types of shelf. Okay.
We start with a very simple set of configurations.
Okay. We take shelf of size 20, you know we cut
them, we cut as many of them as possible. We do the same thing for 45, for 50, 55,
75 okay. So these are my set of inital
configuration. I solve the linear relaxation.
I was going to select you know a mix of these things okay.
And then I start doing column generation. Can I add new configuration that going to
help me improve the value of the linear relaxation.
The first one that I'm going to find is something that counts 20 and 75 at the
same time. Then something that count 20, 45, and 45
and then another one which is 20, 20, 20, 50.
Okay that's a nice one because it cuts the board you know perfectly and that's
going to be enough to actually find the optimal solution to this linear you know
linear problem with exponential variables.
This is the value of the objective constraints.
This is what you are cutting for everyone of these typical configuration you see
that some of them are fractional right? So for finding a feasible solution you
will have to run that up. Okay?
Which means that in this particular case the value that we'll find the integer
solution is going to be 48. Okay this of usually lower bound okay.
Now if you try to solve this problem optimally okay so this is what you get.
Okay, so this is the first you know so lets say you use the first, you use the
first formulation that I've shown you to solve it optimally you will get 47.
Okay, now what is interesting is the time okay.
The column generation is very very tiny example right.
Is going to take 0.03 in of the systems that we are using okay.
The MIP system, the first MIP formulation is going to take about 4 seconds, that's
about two orders of magnitude right? And so that's essentially the basic.
The basic feature of column generation. It's a very nice technique for scaling up
to very large, for, for large scale problems.
Okay? And so that basically gives you the
essence of column generation. If you want to do branch and price, is
the same idea except that column generation is at one particular node of
the tree. Okay?
So in a sense you have to think about column generation.
Is giving you a very, very good lower bound at every one of the nodes, by
generating variables on the fly. Okay?
And as soon as you do a branching decision, you can start regenerating new
column, okay, for improving the value of the linear relaxation.
Okay? So you basically iterate, you know,
branching, and then doing column generation to find a really nice lower
bound. To that to a very nice lower bound or
upper bound I mean a relaxation a very good relaxation to the particular node
okay. So this is you know a branch, your cum
generation, branch and price very useful in practice.
There are a lot of extension to these things in practice that work very well in
different settings. It's a very interesting setting when you
know you have different kinds of complex objects that you have to manipulate.
Okay, thank you very much, next lecture is going to be on [UNKNOWN] and
scheduling.
