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.