1 00:00:00,170 --> 00:00:02,920 Okay, guys. Discrete optimization, this is the, these 2 00:00:02,920 --> 00:00:05,220 are the advanced topics now. They are beautiful. 3 00:00:05,220 --> 00:00:08,060 You should really look at them. But, you know, they are really the 4 00:00:08,060 --> 00:00:11,980 advanced topic of this class. Not strictly mandatory in a sense. 5 00:00:11,980 --> 00:00:15,190 But, you know, they are really nice, so please look at them. 6 00:00:15,190 --> 00:00:17,540 So, so I'm going to talk about column generation, okay? 7 00:00:17,540 --> 00:00:20,860 So, and I'm going to give you a big intro it's kind of one-slide introduction to 8 00:00:20,860 --> 00:00:23,830 tell you what the spirit of it is. And then I'm going to show you the 9 00:00:23,830 --> 00:00:26,810 original example where this was introduced, which is cutting stock. 10 00:00:26,810 --> 00:00:29,740 Okay? So, in a sense you can think about branch 11 00:00:29,740 --> 00:00:34,300 and cut, as we are going to solve this MIP which has an exponential numbers of 12 00:00:34,300 --> 00:00:36,250 constraints. But of course, we don't explore them or 13 00:00:36,250 --> 00:00:38,780 we generate them, you know, one at a time. 14 00:00:38,780 --> 00:00:42,920 Okay, on on demand based on the value of the linear relaxation okay. 15 00:00:42,920 --> 00:00:47,130 So in the particle TSP we were generating the subtour constraints or is com 16 00:00:47,130 --> 00:00:51,440 constraint on demand. Column generation is just another, is, 17 00:00:51,440 --> 00:00:54,979 it's the same idea but reverse. Right so in solving exponentially many 18 00:00:54,979 --> 00:00:57,325 constraints we going to have exponentially many variables. 19 00:00:57,325 --> 00:01:01,710 Okay, and so we want to sort this LP with exponentially many variables. 20 00:01:01,710 --> 00:01:03,620 Okay. Wow that looks crazy right. 21 00:01:03,620 --> 00:01:06,420 But of course we want, we want to list all these variables we're going to 22 00:01:06,420 --> 00:01:10,220 generate them on demand again. Right and so the key point here is that 23 00:01:10,220 --> 00:01:13,910 the variables are not are going to represent complex object nor the simple 24 00:01:13,910 --> 00:01:17,300 decisions that we had before. And I'll talk a little bit about branch 25 00:01:17,300 --> 00:01:21,170 and price which is kind of the use of column generation in branching scheme at 26 00:01:21,170 --> 00:01:23,390 the end. But a key idea would be essentially to do 27 00:01:23,390 --> 00:01:26,900 a branch and bond but using column generation at every one of the nodes. 28 00:01:26,900 --> 00:01:30,220 Okay? So, so this is, this is the cutting stock 29 00:01:30,220 --> 00:01:32,700 example, once again. It came from Gilmore and Gomory. 30 00:01:32,700 --> 00:01:34,520 The same Gomory as the Gomory course of course. 31 00:01:34,520 --> 00:01:38,750 You know, a lot of contribution to coming out of optimization. 32 00:01:38,750 --> 00:01:40,800 And this is, this is what the problem consists of. 33 00:01:40,800 --> 00:01:43,480 So, you have large, you know, wood boards, okay? 34 00:01:43,480 --> 00:01:46,705 Really large, okay? of a particular length. 35 00:01:46,705 --> 00:01:48,530 Okay? And you have you know a large number of 36 00:01:48,530 --> 00:01:52,555 them and you want to cut them into small shelves of different sizes. 37 00:01:52,555 --> 00:01:55,430 Okay and these small shelves are what your customer require. 38 00:01:55,430 --> 00:01:58,330 They don't want very long thing that they are to cut at home. 39 00:01:58,330 --> 00:02:01,230 They, there are ones that are right you know more or less the right side. 40 00:02:01,230 --> 00:02:04,420 the right size, okay? And so for every one of those different 41 00:02:04,420 --> 00:02:07,700 types of shelves, okay. So you have a demand of the popular 42 00:02:07,700 --> 00:02:09,590 customers. You have the length of these shelves and 43 00:02:09,590 --> 00:02:13,790 then the demand of the customer, okay? And so what you need to do is to find how 44 00:02:13,790 --> 00:02:18,210 many boards, you know, big boards you need to actually meet the demand of your 45 00:02:18,210 --> 00:02:20,610 customers. And you, how, and also you want to know 46 00:02:20,610 --> 00:02:23,515 how you have to cut the big boards to actually get to that solution. 47 00:02:23,515 --> 00:02:26,830 Okay, so that's the problem. Okay I'm going to you know show it 48 00:02:26,830 --> 00:02:29,750 visually because it's much more clearer visually. 49 00:02:29,750 --> 00:02:32,310 So these are the big board, that are not that big in the example. 50 00:02:32,310 --> 00:02:35,740 But these are the long boards okay. And these are the types of shelves that 51 00:02:35,740 --> 00:02:40,250 you want to cut okay. So this board here is a length of 110 52 00:02:40,250 --> 00:02:42,590 okay. And so the smallest shelf here is you 53 00:02:42,590 --> 00:02:47,010 know is size 20 the largest is 75 and there are a variety of other sizes in 54 00:02:47,010 --> 00:02:47,910 between. Okay? 55 00:02:47,910 --> 00:02:50,660 And so for every one of these yes, you will have a demand. 56 00:02:50,660 --> 00:02:53,450 Okay? Your customers want 48 of the small 57 00:02:53,450 --> 00:02:55,008 shelf. They want eight of the longer, the 58 00:02:55,008 --> 00:02:57,760 longest shelf. Okay? 59 00:02:57,760 --> 00:03:02,510 And so, so, so, you want essentially to meet the demand of your customers and you 60 00:03:02,510 --> 00:03:06,420 want us to know how you have to, how many of these big boards you want and how you 61 00:03:06,420 --> 00:03:07,530 cut them. Okay? 62 00:03:07,530 --> 00:03:10,380 So this is a particular way to cut them with two of the no, shelf size. 63 00:03:10,380 --> 00:03:15,730 You know, shell size, size 20 and 75. And obviously, you know, the sum of this 64 00:03:15,730 --> 00:03:19,090 is 95, so it fits in the big board. It's one of the valid, you know, 65 00:03:19,090 --> 00:03:21,450 cuttings. This is another cutting which is, you 66 00:03:21,450 --> 00:03:24,000 know, one of five. You know, 50 and 55. 67 00:03:24,000 --> 00:03:27,858 And this is another cutting, you know, 20, 20, 20, 20, 20. 68 00:03:27,858 --> 00:03:30,810 Okay? And so basically what you want to do is 69 00:03:30,810 --> 00:03:34,480 look at these, look at these, look at the various ways you want to cut these 70 00:03:34,480 --> 00:03:37,145 boards, so that you minimize the number of big boards that you are using. 71 00:03:37,145 --> 00:03:39,700 Okay? So this is the first MIP model that I'm 72 00:03:39,700 --> 00:03:41,720 going to show you. It's going to be a terrible model, okay? 73 00:03:41,720 --> 00:03:44,660 But it's the first model that comes to mind, right? 74 00:03:44,660 --> 00:03:48,550 So what you want to do is you want to decide if a particular board, you know 75 00:03:48,550 --> 00:03:50,700 its selected in the optimal solution or not. 76 00:03:50,700 --> 00:03:55,080 So board b is going to be selected. Okay and then you will have a particular 77 00:03:55,080 --> 00:04:01,890 variable x as b which is, going to tells you tell you how many shelf of size s are 78 00:04:01,890 --> 00:04:06,530 basically cut inside are basically available from the cutting of board b. 79 00:04:06,530 --> 00:04:11,250 Okay so if you have for instance 20, 20, 20, 20 you know that's four times, lets 80 00:04:11,250 --> 00:04:16,980 say 5 times 20, you know that's going to tell you that size 20 is cut 5 times in 81 00:04:16,980 --> 00:04:19,210 this particular, in this particular board okay. 82 00:04:19,210 --> 00:04:23,320 So you have five you know shelves of size 20 in that board okay. 83 00:04:23,320 --> 00:04:26,920 Now the constraints that you will have to express inside the may bag are going to 84 00:04:26,920 --> 00:04:31,040 be you know the typical constraint that your having you have these two types of 85 00:04:31,040 --> 00:04:33,360 variables. One of them is going to say oh, I can you 86 00:04:33,360 --> 00:04:37,960 know the board is going to be cut if I. If I actually, board b has is to be cut, 87 00:04:37,960 --> 00:04:40,990 if I'm actually, you know, delivering some shelf from it. 88 00:04:40,990 --> 00:04:42,940 Okay? The second thing that you want is to make 89 00:04:42,940 --> 00:04:45,910 sure that the sum of the things that are basically cut from a bottle of board 90 00:04:45,910 --> 00:04:49,080 don't exceed the size of the board, and then you have to meet the demand of the 91 00:04:49,080 --> 00:04:51,980 customer, okay? So, and the objective of course is to 92 00:04:51,980 --> 00:04:54,760 minimize the number of boards. So, this is a MIP okay, which is 93 00:04:54,760 --> 00:04:57,340 describing that, okay, so you look at the boards, okay? 94 00:04:57,340 --> 00:05:00,150 The set of boards, okay, and you basically minimize the number of them 95 00:05:00,150 --> 00:05:04,250 that you select, okay, simple objective function, [UNKNOWN] zero one variables. 96 00:05:04,250 --> 00:05:08,565 Whether I use a, board b or not, okay. Now, if I'm, so the first set of 97 00:05:08,565 --> 00:05:12,786 constraints is basically telling you that if you are not using board B, you can't 98 00:05:12,786 --> 00:05:17,771 get anything from it. That's what this constraint is using, we 99 00:05:17,771 --> 00:05:21,801 use a big M notation then you basically have you know, x, yb, yb you know, 100 00:05:21,801 --> 00:05:25,583 multiply by M and that basically constraint the value yb multiply by M and 101 00:05:25,583 --> 00:05:29,427 that constraint the value of x as b so if yb is equal to 0, x sb has to be equal to 102 00:05:29,427 --> 00:05:35,661 0, okay? The second type of constraint, second set 103 00:05:35,661 --> 00:05:39,466 of constraint that you have there is basically a capacity constraint. 104 00:05:39,466 --> 00:05:44,384 For every bin, if you sum. The set of the, if you sum the set of 105 00:05:44,384 --> 00:05:49,376 the, of the, of the, if you sum the set of the shelf that you're cutting from 106 00:05:49,376 --> 00:05:53,900 this board, you know, it has to be smaller than the length of the board, 107 00:05:53,900 --> 00:06:00,760 okay? And then you have essentially here the 108 00:06:00,760 --> 00:06:04,280 constraint that is saying you have to meet the demands and then you have the 109 00:06:04,280 --> 00:06:06,140 basically the 0, 1 variables that you have there. 110 00:06:06,140 --> 00:06:08,670 Okay. So, this is the first model that comes, 111 00:06:08,670 --> 00:06:15,670 you know, to mind and one of the things that you see here, is, yeah, so you see 112 00:06:15,670 --> 00:06:19,850 all the, all the types of constraints. And you wonder, you can wonder, is this a 113 00:06:19,850 --> 00:06:21,460 good model or not? Okay? 114 00:06:21,460 --> 00:06:25,280 And the answer is no, this is a terrible model, it has a very bad linear 115 00:06:25,280 --> 00:06:26,360 relaxation. Okay? 116 00:06:26,360 --> 00:06:30,080 And one of the things that you can notice immediately, is that it will have a lot 117 00:06:30,080 --> 00:06:31,140 of symmetries. Okay? 118 00:06:31,140 --> 00:06:33,210 So, essentially, all the boards here. Okay? 119 00:06:33,210 --> 00:06:36,360 All these boards are basically interchangeable. 120 00:06:36,360 --> 00:06:39,360 Which basically means, that if I ever can't figure a cutting with some of these 121 00:06:39,360 --> 00:06:43,150 boards I can just permute this and I have you know a another set of boards. 122 00:06:43,150 --> 00:06:45,625 And as soon as you have something like that in the MIP it's terrible because the 123 00:06:45,625 --> 00:06:49,820 MIP can, you know, even if you have a good bonding you still have to explore 124 00:06:49,820 --> 00:06:52,475 this, you know, rhythm and solution. So you will have to try to break the 125 00:06:52,475 --> 00:06:55,175 symmetries as well. So this is a very bad model actually. 126 00:06:55,175 --> 00:06:59,009 Okay, now one of the question you may ask yourself is that, oh, you know, how many 127 00:06:59,009 --> 00:07:02,420 board do I need, okay. Now there is a very simple upper bounce 128 00:07:02,420 --> 00:07:06,390 of the number of board that you need and you just sum, you know, the demands and 129 00:07:06,390 --> 00:07:09,510 in the worst case you would have board for every one of the demand okay. 130 00:07:09,510 --> 00:07:13,500 So in a sense there is easy upper bound for every one of these things but even 131 00:07:13,500 --> 00:07:15,960 that upper bound this is a very bad model okay. 132 00:07:15,960 --> 00:07:19,200 So what we going to do is move to hyper space okay. 133 00:07:19,200 --> 00:07:22,210 So like in star wars. Okay so we are going to change completely 134 00:07:22,210 --> 00:07:26,160 the way we view this problem okay. And instead of adding these binary 135 00:07:26,160 --> 00:07:30,540 variable you know zero, one whether I use that board or how many items you know how 136 00:07:30,540 --> 00:07:33,040 many shelf of that type I'm cutting with in that board. 137 00:07:33,040 --> 00:07:35,850 I'm going to reason about cutting configuration okay. 138 00:07:35,850 --> 00:07:39,680 So I'm going to say okay this is one way of cutting this board okay. 139 00:07:39,680 --> 00:07:43,520 Do how many of these guys do I select. So I'm not looking, it's very simple 140 00:07:43,520 --> 00:07:45,610 object here. I'm going to look at really complex 141 00:07:45,610 --> 00:07:49,530 object that tells me how I can cut the big board okay. 142 00:07:49,530 --> 00:07:54,680 And so once you have that okay, so will decide which of these cuttings you will 143 00:07:54,680 --> 00:07:57,260 select. To meet the demand, okay? 144 00:07:57,260 --> 00:08:00,730 Now, how is one of these configurations selected, or represented, or 145 00:08:00,730 --> 00:08:03,320 characterized? Essentially, what you have to say is, oh, 146 00:08:03,320 --> 00:08:07,410 this is a configuration that cuts this amount of shelf one, this amount of shelf 147 00:08:07,410 --> 00:08:09,660 two, this amount of shelf n, and so on. Okay? 148 00:08:09,660 --> 00:08:13,650 So, what you need to do is basically specify only, oh, I have a cutting. 149 00:08:13,650 --> 00:08:16,710 This cutting is providing me that many shelves of this type, that many shelves 150 00:08:16,710 --> 00:08:18,350 of that type, and so on. Okay. 151 00:08:18,350 --> 00:08:20,240 That's what I'm going to reason about. Okay. 152 00:08:20,240 --> 00:08:23,680 So, every one of these configurations is basically telling me the various shelves 153 00:08:23,680 --> 00:08:24,980 that I get from it. Okay. 154 00:08:24,980 --> 00:08:27,140 And so, we can find all these configurations. 155 00:08:27,140 --> 00:08:29,000 Okay. We going to discuss how to do that. 156 00:08:29,000 --> 00:08:31,280 But we can find all these configurations. Okay. 157 00:08:31,280 --> 00:08:34,940 And so now, instead of reasoning about, you know, whether I can, how many, he's 158 00:08:34,940 --> 00:08:38,420 just bored, use, and how is, you know, how many of these types of shelves are 159 00:08:38,420 --> 00:08:41,100 cut in the board I'm really using this configuration. 160 00:08:41,100 --> 00:08:43,850 I don't want to reason about these cuttings anymore. 161 00:08:43,850 --> 00:08:48,190 I'm just reasoning I have them, I'm just reasoning about the, the which 162 00:08:48,190 --> 00:08:52,850 configuration I'm going to select. Okay the decision variables are going to 163 00:08:52,850 --> 00:08:57,150 be for a particular configuration c, Xc that's going to be the decision variable 164 00:08:57,150 --> 00:09:01,130 and Xc is going to denote how many times in the optimal solution or in a high 165 00:09:01,130 --> 00:09:03,810 quality solution. I'm selecting that particular type of 166 00:09:03,810 --> 00:09:06,950 configuration okay? So, this is the model, very simple now, 167 00:09:06,950 --> 00:09:09,200 oh, you know, we got rid of all these variables. 168 00:09:09,200 --> 00:09:11,145 Okay. So, what we are saying here is that we 169 00:09:11,145 --> 00:09:15,310 want to minimize the number of boards that we cut, that Xc for every one of the 170 00:09:15,310 --> 00:09:17,500 configuration, how many of these do I select? 171 00:09:17,500 --> 00:09:19,160 You take the sum of this, you want to minimize that. 172 00:09:19,160 --> 00:09:21,820 Okay. Minimize how many of these, of these you 173 00:09:21,820 --> 00:09:25,510 know configuration I'm selecting. So, that's what, you need to think about 174 00:09:25,510 --> 00:09:27,640 them, okay? So this is the number of configuration of 175 00:09:27,640 --> 00:09:28,400 type C. Okay? 176 00:09:28,400 --> 00:09:31,420 The sum is the old, the total number of configurations that I'm cutting. 177 00:09:31,420 --> 00:09:32,900 I want to minimize that. Okay? 178 00:09:32,900 --> 00:09:35,240 And then your only really one constraint. Okay? 179 00:09:35,240 --> 00:09:39,470 Which is how many, you know I need to meet the demands. 180 00:09:39,470 --> 00:09:40,890 Okay. Well how do you do that? 181 00:09:40,890 --> 00:09:45,170 Well you know you have the number of configuration of type you know of type Xc 182 00:09:45,170 --> 00:09:48,627 that you that you are cutting. Okay everyone for every one of the types 183 00:09:48,627 --> 00:09:53,407 of shots that you are requesting is going to give you a number which is NCS. 184 00:09:53,407 --> 00:09:58,975 Okay, NCS is telling you the number of shelf of type S, that configuration c is 185 00:09:58,975 --> 00:10:03,203 providing. Okay, so if you multiply these two, you 186 00:10:03,203 --> 00:10:07,038 have the number of type shelf, of shelves of type S, that are produced by all the 187 00:10:07,038 --> 00:10:11,843 configurations C that I'm producing, that I'm carrying. 188 00:10:11,843 --> 00:10:14,898 And then that has to be greater than the demand for, you know, shelves of type S, 189 00:10:14,898 --> 00:10:17,230 okay? And that's what these constraints is 190 00:10:17,230 --> 00:10:19,420 doing. So once I have this configuration, you 191 00:10:19,420 --> 00:10:22,235 know, I want to minimize the number of them, okay, that I'm selecting, and I 192 00:10:22,235 --> 00:10:24,760 want to meet the demand, okay? And obviously, you know, these values 193 00:10:24,760 --> 00:10:26,050 have to be integers. Okay? 194 00:10:26,050 --> 00:10:28,100 The number of shelves that I'm cutting. Okay? 195 00:10:28,100 --> 00:10:32,080 So this is a much simpler, this is a much simpler model, MIP model okay? 196 00:10:32,080 --> 00:10:37,840 It has also a very strong relaxation. Okay? 197 00:10:37,840 --> 00:10:42,380 And so one of the things that you have to see here is that we got rid entirely on 198 00:10:42,380 --> 00:10:44,220 the capacity constraints on the big board. 199 00:10:44,220 --> 00:10:46,400 Why? Because they are built inside the 200 00:10:46,400 --> 00:10:49,690 configuration. My configuration are valued cuttings. 201 00:10:49,690 --> 00:10:52,560 Okay? So I know that these are rep, that these 202 00:10:52,560 --> 00:10:53,810 are good cuttings. Okay? 203 00:10:53,810 --> 00:10:55,880 They are valid cuttings, they are cutting the big board. 204 00:10:55,880 --> 00:10:57,080 Okay? In pieces. 205 00:10:57,080 --> 00:10:58,880 Okay? And the only thing that I am doing is 206 00:10:58,880 --> 00:11:03,350 really selecting which one I want. Okay and then there are no symmetries 207 00:11:03,350 --> 00:11:04,820 here. All these configuration are different. 208 00:11:04,820 --> 00:11:07,400 I'm just picking the right sub set of configuration. 209 00:11:07,400 --> 00:11:11,030 So I got rid of all the symmetries. I got rid of all the capacity constraints 210 00:11:11,030 --> 00:11:13,920 and I have a beautiful strong relaxation. Okay? 211 00:11:13,920 --> 00:11:17,740 Now I told you that we moved to hyper space right? 212 00:11:17,740 --> 00:11:23,090 So we are basically looking to this the, to the cutting configurations, okay? 213 00:11:23,090 --> 00:11:27,170 Now it's simple zero one variables, okay? How do we find this configuration? 214 00:11:27,170 --> 00:11:30,600 The only thing that we need to do is basically satisfy these capacity 215 00:11:30,600 --> 00:11:32,830 constraints. Every one of these configuration when it 216 00:11:32,830 --> 00:11:36,750 provides a number of shelves of different types that it's providing has to satisfy 217 00:11:36,750 --> 00:11:39,830 this configuration. And this is a very simple constraint, 218 00:11:39,830 --> 00:11:41,630 right. So if we are trying to characterize some 219 00:11:41,630 --> 00:11:42,870 configuration. Okay. 220 00:11:42,870 --> 00:11:48,170 We are going to look at this number and ask, so how many of shelves, of type S, 221 00:11:48,170 --> 00:11:51,670 are we producing in that configuration. And we obviously want to make sure that 222 00:11:51,670 --> 00:11:56,040 when you take the, this type S multiply by size ls, you want to be sure that your 223 00:11:56,040 --> 00:11:59,160 smaller than the length of the big board okay. 224 00:11:59,160 --> 00:12:02,680 So you want so every one of these configuration is going to satisfy that 225 00:12:02,680 --> 00:12:05,080 okay. So we can enumerate the order. 226 00:12:05,080 --> 00:12:08,740 So it's very easy to find this as kind of a simple nap sack constaint with no 227 00:12:08,740 --> 00:12:11,630 objective right. So we can enumerate all these constraints 228 00:12:11,630 --> 00:12:15,700 but in a practical problem, okay. So you will have billions and billions 229 00:12:15,700 --> 00:12:18,460 and billions of them. And so we can't generate them all at the 230 00:12:18,460 --> 00:12:21,423 beginning. And just solve you know the MIP problems 231 00:12:21,423 --> 00:12:24,482 that I've shown you before. So we going to do is you know the same 232 00:12:24,482 --> 00:12:28,311 trick as we did for branch and cut. We are gene-, we are going to generate 233 00:12:28,311 --> 00:12:32,762 these configurations you know one at a time on the mat okay. 234 00:12:32,762 --> 00:12:35,678 So we're going to solve a linear relaxation and then we're going to say 235 00:12:35,678 --> 00:12:40,768 ooh, can I improve this linear relaxation by generating a new configuration okay. 236 00:12:40,768 --> 00:12:43,315 And what happened so, this is the essence of column generation, okay. 237 00:12:43,315 --> 00:12:46,578 It's basically saying, ooh, are these the next configuration? 238 00:12:46,578 --> 00:12:49,224 Or in terms of the linear programming relaxation, it's going to be, what is the 239 00:12:49,224 --> 00:12:52,250 next column that I have to generate? Okay? 240 00:12:52,250 --> 00:12:55,980 So, so this the tableau at a higher level, right? 241 00:12:55,980 --> 00:12:59,430 So you see in this particular case all the variables, which represent the 242 00:12:59,430 --> 00:13:02,148 configurations. So, every one of these column, in a sense 243 00:13:02,148 --> 00:13:06,340 is a configuration, and that configuration is telling you, you know, 244 00:13:06,340 --> 00:13:11,340 how many of this types of shelf, you know, we are producing. 245 00:13:11,340 --> 00:13:15,070 Okay in that particular configuration. So in a sense this big matrix here is 246 00:13:15,070 --> 00:13:17,990 telling you, you know, for a particular configuration how many of these various 247 00:13:17,990 --> 00:13:21,070 types of shelves I'm producing. Okay, and of course, the decision 248 00:13:21,070 --> 00:13:23,980 variables are these Xi, how many of these things we do. 249 00:13:23,980 --> 00:13:26,990 And obviously when you try to have a, you know, the constraint that you are 250 00:13:26,990 --> 00:13:30,130 representing is that the sum of these guys on a particular row has to be 251 00:13:30,130 --> 00:13:32,350 greater than or equal to the demand, okay? 252 00:13:32,350 --> 00:13:35,410 So let's say that we have a bunch of configurations, we solve the LP, we get a 253 00:13:35,410 --> 00:13:39,223 good value, okay, okay? And then we say, ooh, can we improve this 254 00:13:39,223 --> 00:13:42,010 linear relaxation? And what you do is basically say, ooh, 255 00:13:42,010 --> 00:13:46,520 can I find a new column, which when I add that column, okay, I'm going to get a 256 00:13:46,520 --> 00:13:49,530 better linear relaxation? Okay, so you don't want to generate 257 00:13:49,530 --> 00:13:53,658 arbitrary, you know, configuration, you want to generate some of them that will 258 00:13:53,658 --> 00:13:55,790 improve the value of the objective function. 259 00:13:55,790 --> 00:13:58,400 Some of them maybe completely terrible, they are cutting face that you don't 260 00:13:58,400 --> 00:14:01,240 need. You want to just to look at the 261 00:14:01,240 --> 00:14:05,190 particular configuration that because they have a good mix of different types 262 00:14:05,190 --> 00:14:07,090 of self, will improve the linear relaxation. 263 00:14:07,090 --> 00:14:11,370 Okay, that's the goal. Okay, so how do we do that? 264 00:14:11,370 --> 00:14:15,080 Okay, so essentially, you know, a configuration is a column inside the 265 00:14:15,080 --> 00:14:17,280 linear relaxation. Okay, so what is an interesting 266 00:14:17,280 --> 00:14:20,555 configuration? Well, it has to be a co-, a conf-, a 267 00:14:20,555 --> 00:14:25,370 column that whose variable, when I'm adding it inside the linear relaxation, 268 00:14:25,370 --> 00:14:26,530 is going to enter the basis. Okay? 269 00:14:26,530 --> 00:14:28,570 It's going to improve the linear relaxation. 270 00:14:28,570 --> 00:14:31,440 If it's not entering the basis, you know, why would we put it in there. 271 00:14:31,440 --> 00:14:35,390 If it's already optimal, we are adding a column, you know that's basically, not 272 00:14:35,390 --> 00:14:38,330 entering the basis, going to stay the same place, that's terrible right. 273 00:14:38,330 --> 00:14:42,030 So what you want, is to add this column so that they enter the basis and improve 274 00:14:42,030 --> 00:14:45,770 the value of the linear relaxation. Okay, so essentially the way you know 275 00:14:45,770 --> 00:14:50,590 because we cover linear programming before we know that to do that you need 276 00:14:50,590 --> 00:14:53,784 essentially a configuration with a negative reduce cost okay. 277 00:14:53,784 --> 00:14:57,390 So if it's positive it's not going to to enter the basis, if you want a negative 278 00:14:57,390 --> 00:15:00,310 you know reduce cost. What is this cost, this is the ugly ugly 279 00:15:00,310 --> 00:15:03,530 formula that we saw in linear programming, actually it's beautiful but 280 00:15:03,530 --> 00:15:05,700 it's kind of messy. Okay. 281 00:15:05,700 --> 00:15:09,000 So, we going to ignore the constant term, we goonna look only at this term. 282 00:15:09,000 --> 00:15:10,390 Okay. So, let's zoom on it. 283 00:15:10,390 --> 00:15:12,000 Okay? So, this is the part of it which is 284 00:15:12,000 --> 00:15:13,860 really interesting. Okay? 285 00:15:13,860 --> 00:15:16,525 The constant, you know, part, we are not interesting to for, interested in for 286 00:15:16,525 --> 00:15:20,560 generating the new column. You look at this thing, okay, you 287 00:15:20,560 --> 00:15:23,680 specialize it to the problem, which basically means that the constant here, 288 00:15:23,680 --> 00:15:26,700 the C, is going to be one, that's, you know, the cost of one particular 289 00:15:26,700 --> 00:15:27,760 configuration. Okay. 290 00:15:27,760 --> 00:15:31,820 They are all the same, these boards okay and then this the configuration right. 291 00:15:31,820 --> 00:15:35,790 So the configuration is going to specify okay how many of the various types of 292 00:15:35,790 --> 00:15:40,020 shots we will be producing okay. And then you multiply that by CB and you 293 00:15:40,020 --> 00:15:43,460 know the inverse of the basis at this point in the linear relaxation okay. 294 00:15:43,460 --> 00:15:47,174 So we are looking at this thing okay. But what is this guy okay. 295 00:15:47,174 --> 00:15:50,840 We know this guy right? So we know this is essentially you know 296 00:15:50,840 --> 00:15:54,165 the simplex multiper or the dual varibles of the linear relaxation. 297 00:15:54,165 --> 00:15:58,423 Okay, so when we are looking at this, this is essentially, this is essentially 298 00:15:58,423 --> 00:16:01,890 what we will want to become negative okay. 299 00:16:01,890 --> 00:16:05,420 We will want to find a configuration here, you know, which produce these 300 00:16:05,420 --> 00:16:08,538 different types of shelfs which when multiplying by the multiplier I'm 301 00:16:08,538 --> 00:16:11,880 going to make this whole expression negative such that it enter the basis. 302 00:16:11,880 --> 00:16:14,890 OK of course I don't know this and so this is what I want to compute. 303 00:16:14,890 --> 00:16:18,420 I want to compute this really nice configuration such that this expression 304 00:16:18,420 --> 00:16:21,670 using the dual variables are going to give me a number such that that 305 00:16:21,670 --> 00:16:23,095 configuration is going to enter the basis. 306 00:16:23,095 --> 00:16:29,640 Okay so in a sense these multipliers these simplex these dual variables, I 307 00:16:29,640 --> 00:16:32,936 have them. Okay they are already inside my tableau. 308 00:16:32,936 --> 00:16:36,300 Right so I told you how to get that when we talked about linear programming. 309 00:16:36,300 --> 00:16:39,436 So I have these guys, okay so I'm looking at defining these values here, I have 310 00:16:39,436 --> 00:16:43,402 these guys and I have one, okay. And I, I and I know I can try to find 311 00:16:43,402 --> 00:16:47,098 these ends you know using this, you know durable variables search that I will be 312 00:16:47,098 --> 00:16:51,890 able to have a configuration which end to the basis, okay. 313 00:16:51,890 --> 00:16:55,173 So what I'm really doing here is solving an optimization problem, right so I want 314 00:16:55,173 --> 00:16:59,715 these two conditions I want you know a valid, you know cutting of this board. 315 00:16:59,715 --> 00:17:04,195 And I want you know that particular cutting, that particular column to enter 316 00:17:04,195 --> 00:17:09,758 the basis as soon as well when I put it inside the simplex table. 317 00:17:09,758 --> 00:17:12,548 So the feasibility is what I told you before you know I told you that we could 318 00:17:12,548 --> 00:17:15,338 generate billion and billions they have to satisfy this constraint which 319 00:17:15,338 --> 00:17:19,233 basically means the cutting is valid this ns times Ls. 320 00:17:19,233 --> 00:17:22,335 You know, when you sum that, it has to be smaller than the big board, okay and then 321 00:17:22,335 --> 00:17:27,500 I have this quality criteria which say. Ooh, you know, this ns that I'm looking 322 00:17:27,500 --> 00:17:33,150 for, you know, when I, when I used to do variables, when I computed reduced costs, 323 00:17:33,150 --> 00:17:36,280 there, this reduced cost has to be negative, and therefore this part of the 324 00:17:36,280 --> 00:17:39,000 configuration is going to enter the basis, which means we're going to select 325 00:17:39,000 --> 00:17:40,440 that configuration. Right? 326 00:17:40,440 --> 00:17:43,950 And so what you end up doing is solving this beautiful, you know, optimization 327 00:17:43,950 --> 00:17:47,869 problem again, okay. And so this is a problem here where we 328 00:17:47,869 --> 00:17:52,765 are basically basically solving a pro, so we're basically minimizing the value of 329 00:17:52,765 --> 00:17:56,071 the reduced cost. Okay. 330 00:17:56,071 --> 00:17:59,719 So we are trying to meet you know, the capacity constraints of the way, you are 331 00:17:59,719 --> 00:18:04,518 making sure that we are cutting this board in the right fashion. 332 00:18:04,518 --> 00:18:07,716 And obviously this ns has to be integer value. 333 00:18:07,716 --> 00:18:11,150 So this is, this is a, this is a mid problem that we are solving, okay? 334 00:18:11,150 --> 00:18:15,118 Now, if we optimize this, okay, if we optimize this map again, okay, and the 335 00:18:15,118 --> 00:18:19,266 value is small, is negative, then we know, okay? 336 00:18:19,266 --> 00:18:22,300 We know we have a column that's going to enter the basis. 337 00:18:22,300 --> 00:18:25,452 So, great! So, we have a new variable, in a sense. 338 00:18:25,452 --> 00:18:28,396 Okay which will enter the basis and improve the linear relaxation. 339 00:18:28,396 --> 00:18:30,922 Okay? Otherwise, that means that none of them 340 00:18:30,922 --> 00:18:33,164 exist. You could have, you know, exponentially 341 00:18:33,164 --> 00:18:35,855 many of these things. It's billions of things that remain. 342 00:18:35,855 --> 00:18:38,330 You will never improve the linear relaxations. 343 00:18:38,330 --> 00:18:40,930 That means that you have the best linear relaxation at this point. 344 00:18:40,930 --> 00:18:43,820 Okay? So now look at this MIP problem, okay, 345 00:18:43,820 --> 00:18:47,180 can we solve it efficiently? What does it remind you of? 346 00:18:47,180 --> 00:18:50,732 You know once again this is going to be an outside problem. 347 00:18:50,732 --> 00:18:54,630 Okay and so we can solve this problem very very quickly and therefore you know 348 00:18:54,630 --> 00:18:58,050 essentially generating a new column here which can enter the basis is going to 349 00:18:58,050 --> 00:19:00,540 mean I have to solve this outside problem. 350 00:19:00,540 --> 00:19:04,420 Once again we are basically closing the loop with the first lecture, right? 351 00:19:04,420 --> 00:19:08,070 So this how we do column generation then. Okay you generate an initial set of 352 00:19:08,070 --> 00:19:11,020 configuration. For instance we can use one configuration 353 00:19:11,020 --> 00:19:14,730 for it's shelf type and try to pack as many shelf of that type. 354 00:19:14,730 --> 00:19:16,750 Okay. Then you solve the linear program, okay. 355 00:19:16,750 --> 00:19:20,122 So using the existing configuration, if you have an integer solution of [UNKNOWN] 356 00:19:20,122 --> 00:19:25,090 stop, okay. otherwise what you're trying to do is 357 00:19:25,090 --> 00:19:29,540 basically trying to see if you know find a new column find new variable that will 358 00:19:29,540 --> 00:19:32,495 improve the linear relaxation. To do that we have to solve this simple 359 00:19:32,495 --> 00:19:35,880 knapsack problem okay. And so if you solve, if you find these 360 00:19:35,880 --> 00:19:39,970 new column okay, you'll repeat at step two and then you'll continue improving 361 00:19:39,970 --> 00:19:43,216 the linear relaxation adding more and more and more variables. 362 00:19:43,216 --> 00:19:45,860 Okay? Now, once you can't do that, okay, so 363 00:19:45,860 --> 00:19:48,600 what you do, essentially, is that you, one of the things that you can do, and 364 00:19:48,600 --> 00:19:51,940 you do for cutting stock because the linear relaxation is very strong, is to 365 00:19:51,940 --> 00:19:57,122 simply round up all the value of the shelf, of the end variables okay. 366 00:19:57,122 --> 00:20:03,290 Because essentially, you know, that will increase a little bit the number of 367 00:20:03,290 --> 00:20:05,505 shelves that you can because these variables can be fractional. 368 00:20:05,505 --> 00:20:08,900 Okay. so this is an example, so we basically 369 00:20:08,900 --> 00:20:12,835 have this big board. You have the various types of various 370 00:20:12,835 --> 00:20:15,370 demands for various types of shelf. Okay. 371 00:20:15,370 --> 00:20:18,015 We start with a very simple set of configurations. 372 00:20:18,015 --> 00:20:20,960 Okay. We take shelf of size 20, you know we cut 373 00:20:20,960 --> 00:20:24,435 them, we cut as many of them as possible. We do the same thing for 45, for 50, 55, 374 00:20:24,435 --> 00:20:28,360 75 okay. So these are my set of inital 375 00:20:28,360 --> 00:20:30,574 configuration. I solve the linear relaxation. 376 00:20:30,574 --> 00:20:33,300 I was going to select you know a mix of these things okay. 377 00:20:33,300 --> 00:20:38,100 And then I start doing column generation. Can I add new configuration that going to 378 00:20:38,100 --> 00:20:40,910 help me improve the value of the linear relaxation. 379 00:20:40,910 --> 00:20:44,548 The first one that I'm going to find is something that counts 20 and 75 at the 380 00:20:44,548 --> 00:20:47,608 same time. Then something that count 20, 45, and 45 381 00:20:47,608 --> 00:20:50,328 and then another one which is 20, 20, 20, 50. 382 00:20:50,328 --> 00:20:54,816 Okay that's a nice one because it cuts the board you know perfectly and that's 383 00:20:54,816 --> 00:20:58,774 going to be enough to actually find the optimal solution to this linear you know 384 00:20:58,774 --> 00:21:01,440 linear problem with exponential variables. 385 00:21:01,440 --> 00:21:03,260 This is the value of the objective constraints. 386 00:21:03,260 --> 00:21:08,320 This is what you are cutting for everyone of these typical configuration you see 387 00:21:08,320 --> 00:21:12,090 that some of them are fractional right? So for finding a feasible solution you 388 00:21:12,090 --> 00:21:13,550 will have to run that up. Okay? 389 00:21:13,550 --> 00:21:16,735 Which means that in this particular case the value that we'll find the integer 390 00:21:16,735 --> 00:21:21,452 solution is going to be 48. Okay this of usually lower bound okay. 391 00:21:21,452 --> 00:21:26,057 Now if you try to solve this problem optimally okay so this is what you get. 392 00:21:26,057 --> 00:21:28,558 Okay, so this is the first you know so lets say you use the first, you use the 393 00:21:28,558 --> 00:21:32,550 first formulation that I've shown you to solve it optimally you will get 47. 394 00:21:32,550 --> 00:21:35,585 Okay, now what is interesting is the time okay. 395 00:21:35,585 --> 00:21:38,573 The column generation is very very tiny example right. 396 00:21:38,573 --> 00:21:43,020 Is going to take 0.03 in of the systems that we are using okay. 397 00:21:43,020 --> 00:21:47,970 The MIP system, the first MIP formulation is going to take about 4 seconds, that's 398 00:21:47,970 --> 00:21:52,220 about two orders of magnitude right? And so that's essentially the basic. 399 00:21:52,220 --> 00:21:57,360 The basic feature of column generation. It's a very nice technique for scaling up 400 00:21:57,360 --> 00:21:59,790 to very large, for, for large scale problems. 401 00:21:59,790 --> 00:22:02,760 Okay? And so that basically gives you the 402 00:22:02,760 --> 00:22:05,970 essence of column generation. If you want to do branch and price, is 403 00:22:05,970 --> 00:22:10,500 the same idea except that column generation is at one particular node of 404 00:22:10,500 --> 00:22:11,270 the tree. Okay? 405 00:22:11,270 --> 00:22:14,210 So in a sense you have to think about column generation. 406 00:22:14,210 --> 00:22:18,930 Is giving you a very, very good lower bound at every one of the nodes, by 407 00:22:18,930 --> 00:22:21,540 generating variables on the fly. Okay? 408 00:22:21,540 --> 00:22:24,590 And as soon as you do a branching decision, you can start regenerating new 409 00:22:24,590 --> 00:22:28,480 column, okay, for improving the value of the linear relaxation. 410 00:22:28,480 --> 00:22:30,819 Okay? So you basically iterate, you know, 411 00:22:30,819 --> 00:22:34,299 branching, and then doing column generation to find a really nice lower 412 00:22:34,299 --> 00:22:37,408 bound. To that to a very nice lower bound or 413 00:22:37,408 --> 00:22:41,184 upper bound I mean a relaxation a very good relaxation to the particular node 414 00:22:41,184 --> 00:22:44,505 okay. So this is you know a branch, your cum 415 00:22:44,505 --> 00:22:47,768 generation, branch and price very useful in practice. 416 00:22:47,768 --> 00:22:50,136 There are a lot of extension to these things in practice that work very well in 417 00:22:50,136 --> 00:22:53,110 different settings. It's a very interesting setting when you 418 00:22:53,110 --> 00:22:57,250 know you have different kinds of complex objects that you have to manipulate. 419 00:22:57,250 --> 00:23:01,618 Okay, thank you very much, next lecture is going to be on [UNKNOWN] and 420 00:23:01,618 --> 00:23:03,432 scheduling.