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.