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.

Â