0:00

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.