1 00:00:00,350 --> 00:00:04,645 Okay, so this is Discrete Optimization and Mixed Integer Program. 2 00:00:04,645 --> 00:00:08,530 We'll talk about MIP. So, this is one of these magical tools 3 00:00:08,530 --> 00:00:11,650 that we have in optimization, so it's going to be very different from what you 4 00:00:11,650 --> 00:00:14,530 have seen so far. And this is a tool, when it works, it's 5 00:00:14,530 --> 00:00:16,710 really amazing. And sometimes it works, sometimes it 6 00:00:16,710 --> 00:00:19,455 doesn't, but you will see it's really a magical tool. 7 00:00:19,455 --> 00:00:24,420 so what I'm going to do in this lecture is give you a basic introduction to Mixed 8 00:00:24,420 --> 00:00:27,680 Integer, Mix Integer Program, okay? We call them MIP, okay. 9 00:00:27,680 --> 00:00:31,380 I'll talk about MIP all the time today. And then we talk about branch and bound, 10 00:00:31,380 --> 00:00:33,970 which is the basic technique to actually solve them, okay. 11 00:00:33,970 --> 00:00:36,680 Basic introduction. This is a big field. 12 00:00:36,680 --> 00:00:40,630 What I want to give you is the feeling about what this is about okay? 13 00:00:40,630 --> 00:00:44,480 So, this is, this is an integer program. So, what you have to think is that it is 14 00:00:44,480 --> 00:00:46,640 like linear program. Okay? 15 00:00:46,640 --> 00:00:49,770 So, like linear programming. The only difference is that the variable 16 00:00:49,770 --> 00:00:51,980 here, have all to be integers. Okay? 17 00:00:51,980 --> 00:00:56,140 So, we still have, you know, an objective function that we are minimizing. 18 00:00:56,140 --> 00:00:58,300 And we have n variables and m constraints. 19 00:00:58,300 --> 00:01:01,120 Okay? So, you see the, you know you see the end 20 00:01:01,120 --> 00:01:04,670 variables, you see the end constraint. All these constraints are inequalities 21 00:01:04,670 --> 00:01:07,150 okay? So, the variables are constraints to be 22 00:01:07,150 --> 00:01:09,810 non negative okay? Again okay? 23 00:01:09,810 --> 00:01:14,630 And then we have these additional constraints that they have to be integer 24 00:01:14,630 --> 00:01:17,820 values okay? And this difference, this makes a huge 25 00:01:17,820 --> 00:01:20,090 difference in practice of course. Okay? 26 00:01:20,090 --> 00:01:23,890 So, we'll talk about the mixed integer program when not all the variables have 27 00:01:23,890 --> 00:01:26,610 to be integers. Some of them can and some, some are and 28 00:01:26,610 --> 00:01:30,020 some aren't, okay? And that's essentially a mixed integer 29 00:01:30,020 --> 00:01:32,160 program. So, we have some values that are like in 30 00:01:32,160 --> 00:01:34,880 linear programming. They can take you know, rational values, 31 00:01:34,880 --> 00:01:37,810 real numbers. Are and then some of them are going to be 32 00:01:37,810 --> 00:01:41,010 integers. Okay, so and that's why you call mixed, 33 00:01:41,010 --> 00:01:45,024 mixture of two variables. Okay, but once again, a big you know, a 34 00:01:45,024 --> 00:01:48,690 big, big thing to mention here is that the constraints are linear, they're 35 00:01:48,690 --> 00:01:52,360 qualities and of course we're minimizing. Of course all the techniques that I've 36 00:01:52,360 --> 00:01:54,920 shown you for linear programming are still working, right? 37 00:01:54,920 --> 00:01:58,300 Maximizing is easy to do. You minimize the negation. 38 00:01:58,300 --> 00:02:03,620 Writing equations or you know, inequalities or equations, and, and you 39 00:02:03,620 --> 00:02:07,120 know, equations are inequalities. Are going to be done exactly like we did 40 00:02:07,120 --> 00:02:09,530 for linear problems. And of course if you want a variable 41 00:02:09,530 --> 00:02:12,770 which can take negative value, you can always use a different set we have done 42 00:02:12,770 --> 00:02:13,600 before. Okay? 43 00:02:13,600 --> 00:02:16,910 So, most of the same technique, but what is key is that the constraints and the 44 00:02:16,910 --> 00:02:20,600 objective function are linear. But now, some of the variables can be 45 00:02:20,600 --> 00:02:22,140 integers. Okay? 46 00:02:22,140 --> 00:02:26,360 So, the difference between having integer variables or not having integer variable 47 00:02:26,360 --> 00:02:28,750 is big, right? So, that's the gap between being 48 00:02:28,750 --> 00:02:33,480 polynomial and NP complete, okay? So, this is a huge difference, as soon as 49 00:02:33,480 --> 00:02:37,676 you introduce this, this, this integer variables okay? 50 00:02:37,676 --> 00:02:43,250 So, so the, the, the entire complexity of the problem changes and for most people 51 00:02:43,250 --> 00:02:46,340 in industry sometimes, it's a big, it's a big difference right? 52 00:02:46,340 --> 00:02:49,480 They say, oh but it should be easier there are fewer integers than there are 53 00:02:49,480 --> 00:02:53,815 real numbers but no having integers is what makes this problem really complex. 54 00:02:53,815 --> 00:02:56,710 Okay? So, this is an example that we have seen 55 00:02:56,710 --> 00:02:57,250 before. Right? 56 00:02:57,250 --> 00:03:01,420 The knapsack example. This is, this is a mixed integer program. 57 00:03:01,420 --> 00:03:04,070 Okay? So, we have a linear objective function, 58 00:03:04,070 --> 00:03:06,740 the variable xi are constrained to be 0 and 1. 59 00:03:06,740 --> 00:03:10,010 And they have to be integer value. Want to take the item or not. 60 00:03:10,010 --> 00:03:12,210 Okay? You know it's not a fraction value. 61 00:03:12,210 --> 00:03:14,680 And of course we had this linear inequality. 62 00:03:14,680 --> 00:03:17,195 Okay? So, that's the most simple in a sense. 63 00:03:17,195 --> 00:03:21,030 Mixed integer program that we have okay? So, what we're going to do now is look at 64 00:03:21,030 --> 00:03:24,870 warehouse location we see this problem before when we do local search. 65 00:03:24,870 --> 00:03:27,470 And what we going to do is develop the mid program for it. 66 00:03:27,470 --> 00:03:32,080 So, I'm going to go over what the problem is again and then we see how we design. 67 00:03:32,080 --> 00:03:35,260 And mid program, actually we'll come back several time to this problem, okay? 68 00:03:35,260 --> 00:03:39,770 So, what we had there is that we have various locations where we can open a, a 69 00:03:39,770 --> 00:03:42,530 warehouse, okay? So, when we open a, a warehouse in a 70 00:03:42,530 --> 00:03:44,780 particular location, we say we open that warehouse. 71 00:03:44,780 --> 00:03:48,080 If we don't put it there it's basically, basically say that it's closed. 72 00:03:48,080 --> 00:03:50,350 Okay? And then we have a bunch of customers 73 00:03:50,350 --> 00:03:52,950 have, you know, around you know, all over the place. 74 00:03:52,950 --> 00:03:55,670 Okay? And the goal is actually to choose which 75 00:03:55,670 --> 00:03:58,540 warehouses to open so that you can serve all the customers. 76 00:03:58,540 --> 00:04:02,970 And every one of the customer. Is,will be allocated to exactly one 77 00:04:02,970 --> 00:04:05,920 warehouse okay? Now what you want to minimize is the cost 78 00:04:05,920 --> 00:04:08,650 of opening these warehouses and maintaining them, that's the fixed cost 79 00:04:08,650 --> 00:04:12,790 for every warehouse, warehouse. And then you have the transportation cost 80 00:04:12,790 --> 00:04:16,090 from the customers to the warehouse okay? So, you will want to minimize the sum of 81 00:04:16,090 --> 00:04:18,160 these two things okay? So that's the problem okay. 82 00:04:18,160 --> 00:04:21,950 So, this one solution where you open one warehouse and you serve all the customers 83 00:04:21,950 --> 00:04:24,758 with that warehouse okay? This is another solution where we open 84 00:04:24,758 --> 00:04:28,610 two warehouses okay? And the customer are served you know, in 85 00:04:28,610 --> 00:04:31,980 the way which is depicted here. But once again you know I want to focus, 86 00:04:31,980 --> 00:04:36,590 I, I want to mention the fact that every one customer is assigned to exactly one 87 00:04:36,590 --> 00:04:37,390 warehouse. Okay? 88 00:04:37,390 --> 00:04:39,520 And this is another solution with two warehouses. 89 00:04:39,520 --> 00:04:41,590 It's a different customer allocation. Okay? 90 00:04:41,590 --> 00:04:44,650 So, now the question is can we find a MIP model okay? 91 00:04:44,650 --> 00:04:47,960 For warehouse location. Okay? 92 00:04:47,960 --> 00:04:50,440 And so once again, it's [UNKNOWN] constraint programs. 93 00:04:50,440 --> 00:04:53,130 It's going to be easy, right? So, the only three things that we have to 94 00:04:53,130 --> 00:04:55,380 do is find what are the decision variables. 95 00:04:55,380 --> 00:04:58,510 And then we have to express linear constraints, because we are in a MIP 96 00:04:58,510 --> 00:05:00,770 context in terms of this decision variable. 97 00:05:00,770 --> 00:05:03,580 And then express the objective function, which is also to be linear. 98 00:05:03,580 --> 00:05:06,460 Okay? So, can we find that for warehouse 99 00:05:06,460 --> 00:05:08,660 location? Okay, and obviously the answer is yes. 100 00:05:08,660 --> 00:05:10,530 Otherwise I wouldn't be talking about this problem, right. 101 00:05:10,530 --> 00:05:13,777 So, what are the decision variables? Okay? 102 00:05:13,777 --> 00:05:16,780 So, in this particular case we are going to use two types of decision 103 00:05:16,780 --> 00:05:17,670 variables. Okay? 104 00:05:17,670 --> 00:05:22,220 So, the first type is going to basically be associated with every warehouse. 105 00:05:22,220 --> 00:05:24,030 Okay? So right, so this is what we want at the 106 00:05:24,030 --> 00:05:26,960 end, we want to know. You know, which warehouse is to be open 107 00:05:26,960 --> 00:05:28,640 okay? How many and where, okay? 108 00:05:28,640 --> 00:05:33,490 So, we'll have a decision variable xw for every warehouse w. 109 00:05:33,490 --> 00:05:37,800 And that variable is going to be one, if that warehouse is open, okay? 110 00:05:37,800 --> 00:05:40,620 So, that means that we're building the warehouse at that location, okay? 111 00:05:40,620 --> 00:05:44,040 It's zero if we just don't build the warehouse at that location, okay? 112 00:05:44,040 --> 00:05:47,040 So, that's the first type of variables that's going to tell us where to build 113 00:05:47,040 --> 00:05:48,954 these warehouses. And how many. 114 00:05:48,954 --> 00:05:50,800 Okay? Now, we need a second thing, right? 115 00:05:50,800 --> 00:05:54,660 So, we need for every customers to know which you know, warehouse it's going to 116 00:05:54,660 --> 00:05:57,530 be allocated to. So, we are going to use a second set of 117 00:05:57,530 --> 00:06:00,040 variable, which we call the Y variables here. 118 00:06:00,040 --> 00:06:03,640 Okay? And Ywc is going to be equal to 1. 119 00:06:03,640 --> 00:06:08,380 If customer c is basically served by warehouse w okay? 120 00:06:08,380 --> 00:06:12,440 And zero otherwise. Zero would mean, okay custo, warehouse w 121 00:06:12,440 --> 00:06:14,190 doesn't serve customer c. Okay? 122 00:06:14,190 --> 00:06:17,820 So, once again two types of variables. Whether we open a warehouse or not that's 123 00:06:17,820 --> 00:06:21,810 the x variables and the y variables is going to tell me for a pair of customer's 124 00:06:21,810 --> 00:06:25,330 warehouse are these two guys connected? You know, is this warehouse serving that 125 00:06:25,330 --> 00:06:26,720 customer? Okay?. 126 00:06:26,720 --> 00:06:29,560 So, now we the decision variables the only thing that we have to do now is 127 00:06:29,560 --> 00:06:33,150 express the constraints okay? So, what are the constraints okay? 128 00:06:33,150 --> 00:06:35,560 So think about it. What are the constraints in this 129 00:06:35,560 --> 00:06:39,640 particular setting, okay?. Now there is one constraint which is 130 00:06:39,640 --> 00:06:43,710 really important that we don't want to miss is that we can serve a customer with 131 00:06:43,710 --> 00:06:46,890 a warehouse. Only if that warehouse is open. 132 00:06:46,890 --> 00:06:48,361 Right? So, we don't to connect a customer to a 133 00:06:48,361 --> 00:06:50,478 warehouse that doesn't exist. Right? 134 00:06:50,478 --> 00:06:52,599 So, that's a very simple constraint. Okay? 135 00:06:52,599 --> 00:06:55,009 But it's very important. Otherwise you know, we don't, we wouldn't 136 00:06:55,009 --> 00:06:57,339 have a solution. And the second one is that we want to 137 00:06:57,339 --> 00:07:01,050 make sure that the customer is served by exactly one warehouse. 138 00:07:01,050 --> 00:07:03,026 Okay? So, so we have to make sure that the 139 00:07:03,026 --> 00:07:05,593 customer is served. But it can only be served by one 140 00:07:05,593 --> 00:07:07,214 warehouse. Okay? 141 00:07:07,214 --> 00:07:10,342 And so, essentially that's the second constraint, the second type of constraint 142 00:07:10,342 --> 00:07:12,580 that we have to express. Okay? 143 00:07:12,580 --> 00:07:16,505 Now, we have to express these constraints as linear constraints. 144 00:07:16,505 --> 00:07:18,140 Okay? And that's what this slide is showing 145 00:07:18,140 --> 00:07:18,850 you. Okay?. 146 00:07:18,850 --> 00:07:22,710 So, the first constraint telling you that you know, a warehouse is to be opened to 147 00:07:22,710 --> 00:07:26,553 serve a customer, is a simple inequality with two, the two, the two types of 148 00:07:26,553 --> 00:07:29,960 variables okay? So, we are basically saying that, why the 149 00:07:29,960 --> 00:07:33,970 value c has to be smaller or equal to xw, what does that mean okay? 150 00:07:33,970 --> 00:07:38,960 So, if we close the warehouse, so that means that xw, if we close warehouse w so 151 00:07:38,960 --> 00:07:42,127 that we don't build a warehouse, that means xw is 0 right? 152 00:07:42,127 --> 00:07:48,370 If xw is 0 then it's for, you know y you know, wc is going to be forced to be 0, 153 00:07:48,370 --> 00:07:51,950 we can't actually you know, serve that customer with that warehouse. 154 00:07:51,950 --> 00:07:56,600 That's part of what we want, right? And if, if xw is 1, that basically means 155 00:07:56,600 --> 00:07:58,540 that the warehouse is open, we can use it. 156 00:07:58,540 --> 00:08:01,400 But that doesn't mean that we have to allocate customer c to that warehouse, 157 00:08:01,400 --> 00:08:02,470 but we can. Okay? 158 00:08:02,470 --> 00:08:06,100 So, that value is going to be 1, which basically means that the variable you 159 00:08:06,100 --> 00:08:10,020 know, ywc it's free, it can take value 0 it can take value 1. 160 00:08:10,020 --> 00:08:11,810 That's the meaning of that constraint. Okay? 161 00:08:11,810 --> 00:08:16,300 So, in a sense we are encoding you know, the relationship between these decisions 162 00:08:16,300 --> 00:08:18,580 using an inequality in this particular case. 163 00:08:18,580 --> 00:08:22,030 And this works well because these two variables take 0, 1 values and we come 164 00:08:22,030 --> 00:08:25,829 back to the fact that in a MIP a lot of the decision variables are going to be 165 00:08:25,829 --> 00:08:26,570 0,1. Okay? 166 00:08:26,570 --> 00:08:30,335 The second constraint that you see there, is basically telling us that a customer 167 00:08:30,335 --> 00:08:33,030 should be served by exactly one warehouse. 168 00:08:33,030 --> 00:08:35,445 And what we're going to do is, we're going to look at one customer, we're 169 00:08:35,445 --> 00:08:37,550 going to look at all the possible warehouse. 170 00:08:37,550 --> 00:08:41,000 And we're going to make sure that the sum of the variables that are basically 171 00:08:41,000 --> 00:08:45,100 denoting whether that warehouse is serving that customer, is equal to 1. 172 00:08:45,100 --> 00:08:48,460 And that's what you see there, okay? So, you see a sum for all the warehouses. 173 00:08:48,460 --> 00:08:55,220 And then you see the variable ywc okay? So, that basically means is y actu, is w 174 00:08:55,220 --> 00:08:56,712 actually serving customer c? Okay? 175 00:08:56,712 --> 00:08:59,678 So, it's the sum of all these guys and they have to sum to 1. 176 00:08:59,678 --> 00:09:02,330 Okay? Once again, these guys are 0, 1 so that 177 00:09:02,330 --> 00:09:05,630 basically means that one of these warehouses is going to serve that 178 00:09:05,630 --> 00:09:07,380 customer. Okay? 179 00:09:07,380 --> 00:09:10,750 So, beautiful we have a model, if we can express the objective function. 180 00:09:10,750 --> 00:09:14,790 The objective function now is the sum of the fixed costs and the transportation 181 00:09:14,790 --> 00:09:15,430 cost. Okay? 182 00:09:15,430 --> 00:09:19,030 It's reasonably easy to state. What you do, this is essentially the 183 00:09:19,030 --> 00:09:22,030 fixed part, okay? So, what we are doing is the sum for all 184 00:09:22,030 --> 00:09:25,380 the warehouse of the fixed cost of the warehouse, okay, times whether the 185 00:09:25,380 --> 00:09:27,910 warehouse is open or not. So, if the warehouse is closed, there is 186 00:09:27,910 --> 00:09:31,400 no cost. If the warehouse is open will, you know, 187 00:09:31,400 --> 00:09:32,940 incur a cost of cw. Okay? 188 00:09:34,310 --> 00:09:38,100 And then the second, the second aspect here is basically the transportation 189 00:09:38,100 --> 00:09:42,800 cost. We look at the pair wc, and if, and if, 190 00:09:42,800 --> 00:09:46,460 you know, w is serving c, that variable y is going to be 1. 191 00:09:46,460 --> 00:09:49,157 So, we want to incur the transportation cost. 192 00:09:49,157 --> 00:09:52,670 twc okay? So, that's we have to do, of course with 193 00:09:52,670 --> 00:09:56,520 the variable y is 0 then essentially there is no cost incurred. 194 00:09:56,520 --> 00:09:58,570 You know, these things are not connected. Okay? 195 00:09:58,570 --> 00:10:01,450 So now, so this is the transportation costs okay? 196 00:10:01,450 --> 00:10:04,660 So fixed costs, transportation costs. We have the objective function and we 197 00:10:04,660 --> 00:10:08,473 have the entire model okay? So, this is the entire MIP model for 198 00:10:08,473 --> 00:10:10,183 warehouse location. Okay? 199 00:10:10,183 --> 00:10:12,855 Objective function, fixed cost, variable cost. 200 00:10:12,855 --> 00:10:15,700 Okay? Then we have the constraints here, that 201 00:10:15,700 --> 00:10:19,770 basically state that you know, you can serve a customer with a warehouse. 202 00:10:19,770 --> 00:10:22,950 If the warehouse is, if, you can serve a customer with a warehouse if the 203 00:10:22,950 --> 00:10:27,424 warehouse is open. Then you have to serve exactly 1 customer 204 00:10:27,424 --> 00:10:31,225 uh, [INAUDIBLE] a customer exactly once, so you look at all the warehouse exactly 205 00:10:31,225 --> 00:10:34,104 one should serve that customer. And then usually these two types of 206 00:10:34,104 --> 00:10:36,240 variables have to be 0 and 1. Okay? 207 00:10:36,240 --> 00:10:41,250 We open up a warehouse or we don't, we serve you know, the warehouse w serve 208 00:10:41,250 --> 00:10:43,050 customer c or not. Okay? 209 00:10:43,050 --> 00:10:45,170 And that's the entire model. Okay? 210 00:10:45,170 --> 00:10:49,204 So, so its interesting when you look at these models that the variables here are 211 00:10:49,204 --> 00:10:49,904 0, 1. Okay? 212 00:10:49,904 --> 00:10:54,240 And I'm going to come back to that, but we could have another essential model. 213 00:10:54,240 --> 00:10:58,464 We could think of you know, instead of having all these 0, 1 variables, ywc for 214 00:10:58,464 --> 00:11:03,440 all the warehouses, why don't I have simply a variable yc. 215 00:11:03,440 --> 00:11:08,479 Which denotes the, the, the warehouse that is serving customer c, okay? 216 00:11:08,479 --> 00:11:12,972 Now this is a question for you, okay? So think, you know, use, you know, try to 217 00:11:12,972 --> 00:11:18,675 build a MIP model using a decision variable which is yc, okay? 218 00:11:18,675 --> 00:11:22,489 And see what the challenges are. It's a very, it's a very interesting 219 00:11:22,489 --> 00:11:25,294 exercise try to see what is going to be tough if you use these decision 220 00:11:25,294 --> 00:11:29,826 variables, instead of those 0, 1 variables that I showed you, okay? 221 00:11:29,826 --> 00:11:34,677 So, so to think [UNKNOWN] is that in general, MIP models love 0, 1 variables, 222 00:11:34,677 --> 00:11:37,410 okay? So, you'll see a huge amount of 0, 1 223 00:11:37,410 --> 00:11:40,582 variables in MIP model. You'll see typically very few integer 224 00:11:40,582 --> 00:11:43,143 variables, okay? The integer variables are typically 225 00:11:43,143 --> 00:11:46,081 going to be 0 and 1. So, you know, it's like you know, MIP 226 00:11:46,081 --> 00:11:50,880 models like to have decision which are actually yes or no, okay? 227 00:11:50,880 --> 00:11:54,296 So, very different from constraint programming model in that sense, okay? 228 00:11:54,296 --> 00:11:57,383 But the good point is that once you have the 0, 1 variables expressing linear 229 00:11:57,383 --> 00:12:00,336 constraints, is typically very simple, okay? 230 00:12:00,336 --> 00:12:03,622 So, in a sense you know, you use these very simple 0, 1 variables and then all 231 00:12:03,622 --> 00:12:08,549 the constrains. Are you know, simple to state in general. 232 00:12:08,549 --> 00:12:10,778 Okay? So, so sometimes they have many indices, 233 00:12:10,778 --> 00:12:13,837 but they are easier to state, they are easy to state okay? 234 00:12:13,837 --> 00:12:17,899 So, it doesn't mean that you know modeling in MIP is easy. 235 00:12:17,899 --> 00:12:20,419 And we'll see some of these issues later on so, there're are still many, many 236 00:12:20,419 --> 00:12:23,503 possible models you can design. You know, what are the basic, what are 237 00:12:23,503 --> 00:12:25,868 the basic decision variables that you are going to use? 238 00:12:25,868 --> 00:12:27,571 What are the constraints? What are the objectives? 239 00:12:27,571 --> 00:12:30,188 Everything that we said for constraint programming is still valid. 240 00:12:30,188 --> 00:12:33,438 Finding a good model is not necessarily easy, okay? 241 00:12:33,438 --> 00:12:36,538 And so, we'll see some of these things in, in a moment, actually, or the next 242 00:12:36,538 --> 00:12:39,790 lecture. Okay, so now we have a beautiful MIP 243 00:12:39,790 --> 00:12:43,954 model, how do we solve them? Now this has been an active research area 244 00:12:43,954 --> 00:12:46,882 for many, many decades, and it's still a very active research area, it's a 245 00:12:46,882 --> 00:12:51,256 fascinating area, okay? And so, one of the basic techniques to 246 00:12:51,256 --> 00:12:54,316 solve MIP problems okay? Is to use branch and bound. 247 00:12:54,316 --> 00:12:56,703 Okay? Remember, branch and bound, we saw that 248 00:12:56,703 --> 00:12:59,643 you know, first lecture you have, or second lecture, with bounding, and 249 00:12:59,643 --> 00:13:02,700 branching. Okay, bounding is what, is finding an 250 00:13:02,700 --> 00:13:07,192 optimistic evaluation of the, of the objective function. 251 00:13:07,192 --> 00:13:10,490 Optimistic, optimistic relaxation, we love relaxing, right? 252 00:13:10,490 --> 00:13:13,814 And then branching is when, you know, is basically splitting the problem into sub 253 00:13:13,814 --> 00:13:17,011 problems, and then apply the same algorithm on the sub products. 254 00:13:17,011 --> 00:13:18,900 Okay? So this is the basic two steps. 255 00:13:18,900 --> 00:13:23,500 Now what is nice about MIP models is that they have a very, very natural 256 00:13:23,500 --> 00:13:25,960 relaxation, okay? Which is linear programming. 257 00:13:25,960 --> 00:13:29,000 And that's why we talked about linear programming so much. 258 00:13:29,000 --> 00:13:35,150 We have this linear relaxation that we can use as the bonding of as the bonding 259 00:13:35,150 --> 00:13:37,955 part of MIP models, of branch and bond for MIP. 260 00:13:37,955 --> 00:13:40,130 Okay? So, the key idea is that you going to 261 00:13:40,130 --> 00:13:43,830 remove the integrality constraints, and you have a relaxation, okay? 262 00:13:43,830 --> 00:13:45,410 So, this is the only thing that you do, right? 263 00:13:45,410 --> 00:13:47,970 You look at this big MIP model. If you remove the integrality 264 00:13:47,970 --> 00:13:50,220 constraints, what do you have? You have a linear program. 265 00:13:50,220 --> 00:13:53,090 You can solve that very fast, and that's what we going to do, okay? 266 00:13:53,090 --> 00:13:57,350 So, the bounding path, the optimistic relaxation, is going to be basically 267 00:13:57,350 --> 00:14:00,730 relaxing the integer constraints. You wrap your largest set of values that 268 00:14:00,730 --> 00:14:02,401 the variable can take, so it's a relaxation. 269 00:14:02,401 --> 00:14:06,355 Okay? So, so basically the branch and bound for 270 00:14:06,355 --> 00:14:08,860 MIP models is going to be solving the linear relaxation. 271 00:14:08,860 --> 00:14:10,910 Okay? At a particular node, you're going to do 272 00:14:10,910 --> 00:14:13,771 that, you're going to look at that node. You're going to say, oh, I want to solve 273 00:14:13,771 --> 00:14:16,560 the linear relaxation. And if the linear relaxation is worse 274 00:14:16,560 --> 00:14:20,120 than the best solutions you have found so far, you can prune that node, that, that 275 00:14:20,120 --> 00:14:23,172 node away, okay? It basically means that the associated 276 00:14:23,172 --> 00:14:26,270 sub problems to that node is provably sub-optimal. 277 00:14:26,270 --> 00:14:28,370 You can get rid of it. Okay? 278 00:14:28,370 --> 00:14:32,900 So, if not, okay, so if the, you, you are basically looking at this linear 279 00:14:32,900 --> 00:14:37,900 relaxation more closely, and you are looking to see if it has all integer 280 00:14:37,900 --> 00:14:41,010 values, which can happen, right? And if that happens, that means that in 281 00:14:41,010 --> 00:14:44,610 this large space of solutions, you know, the linear programming relaxation, it 282 00:14:44,610 --> 00:14:47,330 throws in an integer value for all of these variables. 283 00:14:47,330 --> 00:14:50,830 And that means that you know, obviously it's a solution to the overall MIP 284 00:14:50,830 --> 00:14:54,360 problem, well to, for that node, right? And so, essentially you have found a 285 00:14:54,360 --> 00:14:58,210 feasible solution and you can obtain the best solution you have found so far, 286 00:14:58,210 --> 00:15:01,520 okay? Now if none of these two things apply 287 00:15:01,520 --> 00:15:05,260 then you need to branch, okay? And the interesting thing about MIP 288 00:15:05,260 --> 00:15:10,240 models, is that they are going to use the linear relaxation to drive or to branch 289 00:15:10,240 --> 00:15:11,780 in general. Okay? 290 00:15:11,780 --> 00:15:14,610 And so there are many ways to do this, okay so I'm just going to mention one 291 00:15:14,610 --> 00:15:16,710 here. But this is also a very active area. 292 00:15:16,710 --> 00:15:19,670 How you branch, what do you use, how do you use, do you use the objective 293 00:15:19,670 --> 00:15:21,330 function? Do you use the constraints, and so on. 294 00:15:21,330 --> 00:15:24,700 But this is the simplest scheme that is using the linear relaxation. 295 00:15:24,700 --> 00:15:27,660 So, what you're going to do is you're going to look at this relaxation, and you 296 00:15:27,660 --> 00:15:30,640 know that, you know, some of the integer variables have a fractional value, and 297 00:15:30,640 --> 00:15:31,700 they should not. Okay? 298 00:15:31,700 --> 00:15:35,910 So, what you're going to do is take one of those, okay, which has, let's say, x 299 00:15:35,910 --> 00:15:39,240 which has a fractional value f. And what you're going to do is create two 300 00:15:39,240 --> 00:15:40,320 set problems. Okay? 301 00:15:40,320 --> 00:15:45,830 One of them is going to be saying that x has to be small or equal to the integer 302 00:15:45,830 --> 00:15:49,000 which is the smallest, the largest integer which is smaller than f. 303 00:15:49,000 --> 00:15:51,430 Okay? So, that's the floor of, of f and okay 304 00:15:51,430 --> 00:15:54,890 and that's one of the sub problems, okay? And the other sub problem is going to see 305 00:15:54,890 --> 00:15:59,050 that x is greater than the seal of f, that's the smallest integer which is 306 00:15:59,050 --> 00:16:00,360 larger than f. Okay? 307 00:16:00,360 --> 00:16:05,030 So, these are two sub problems you can add to the, to the set of constraints 308 00:16:05,030 --> 00:16:07,164 that you have and then you repeat the branch and bound. 309 00:16:07,164 --> 00:16:09,790 Okay? So, the key point here, if you remember 310 00:16:09,790 --> 00:16:12,000 constraint programming. Constraint programming was obsessed with 311 00:16:12,000 --> 00:16:15,040 constraints, okay? And was basically branching on the, you 312 00:16:15,040 --> 00:16:18,710 know, using feasibility information. Here we are obsessed with the objective. 313 00:16:18,710 --> 00:16:22,010 We are getting these, good, you know, well, hopefully good. 314 00:16:22,010 --> 00:16:25,010 Relaxation of the objective optimistic evaluation of the objective. 315 00:16:25,010 --> 00:16:29,590 And then what we use is we use this linear relaxation which is like ooh, you 316 00:16:29,590 --> 00:16:32,020 know, this is like a very good solution, okay? 317 00:16:32,020 --> 00:16:36,050 But it's not feasible, and trying to use that for branching, okay? 318 00:16:36,050 --> 00:16:40,510 So, in a sense we are branching using optimality information, okay? 319 00:16:40,510 --> 00:16:44,790 So, summarizing what I just said. Okay, so we are basically focusing on the 320 00:16:44,790 --> 00:16:47,530 objective here. Okay, once again I'm exaggerating, of 321 00:16:47,530 --> 00:16:50,270 course the MIP system in practice. We'll also focus on some other 322 00:16:50,270 --> 00:16:54,020 constraint, but it's good to exaggerate to, you know, drive the point home here. 323 00:16:54,020 --> 00:16:57,480 So, we are basically focusing on the objective and the relaxation gives you an 324 00:16:57,480 --> 00:17:00,710 optimistic bound all the best value that the MIP can ever get. 325 00:17:00,710 --> 00:17:02,950 Okay? The pruning is based obviously on the 326 00:17:02,950 --> 00:17:05,030 objective and sub-optimality. Okay? 327 00:17:05,030 --> 00:17:09,075 So, when you detect the linear relaxation is not higher than the best solutions 328 00:17:09,075 --> 00:17:12,220 you've found, not better than the best solution you've found so far, you just 329 00:17:12,220 --> 00:17:16,330 prune it away, okay? And obviously the relaxation has been 330 00:17:16,330 --> 00:17:19,290 obtained by relaxing the integer integrality constraints okay? 331 00:17:19,290 --> 00:17:22,382 And we have a global view of all the constraints, you know. 332 00:17:22,382 --> 00:17:25,575 So, in constraint programming all the constraints were acting, you know 333 00:17:25,575 --> 00:17:27,870 independently. Here we relax all the integrality 334 00:17:27,870 --> 00:17:30,675 constraints, but when we look at the constraints, we look at them globally. 335 00:17:30,675 --> 00:17:34,905 Okay, so we have this linear program, which basically look at the constraints 336 00:17:34,905 --> 00:17:38,916 globally, but they just have removed the integrality constraints. 337 00:17:38,916 --> 00:17:41,340 Okay? So, in the Knapsack, in a sense, so when 338 00:17:41,340 --> 00:17:45,060 you look at the relaxation, what we did, this is basically the MIP model for the 339 00:17:45,060 --> 00:17:47,370 knapsack. And the relaxation is only looking at 340 00:17:47,370 --> 00:17:52,400 this, you know, 0,1 that you see there, and basically replacing them by the fact 341 00:17:52,400 --> 00:17:54,090 that oh, it doesn't have to take the values 0. 342 00:17:54,090 --> 00:17:56,849 One, it can take any value between 0 and 1. 343 00:17:56,849 --> 00:17:58,950 Okay? That's the linear relaxation and we can 344 00:17:58,950 --> 00:18:02,774 do that for any MIP model right? So we just remove these integrality 345 00:18:02,774 --> 00:18:07,040 constraints okay? Now, so in the case of the Knapsack, the 346 00:18:07,040 --> 00:18:10,410 linear relaxation is the same as the greedy approach that I've shown you 347 00:18:10,410 --> 00:18:13,710 right? Order the item by the most value per 348 00:18:13,710 --> 00:18:16,220 weight okay, and select them in that order okay? 349 00:18:16,220 --> 00:18:20,930 Until you get a fractional value and you take that fractional value. 350 00:18:20,930 --> 00:18:24,430 to, to, to get a relaxation. So, that's what the linear programming 351 00:18:24,430 --> 00:18:26,980 relaxation is going to do. So, I'm going to talk a lot about this 352 00:18:26,980 --> 00:18:30,060 linear programming relaxation the next couple of, of classes. 353 00:18:30,060 --> 00:18:34,015 It's a beast and, you know, you see it's, it's, it has very interesting behavior. 354 00:18:34,015 --> 00:18:37,000 Okay? Now when we branch, we branch with a 355 00:18:37,000 --> 00:18:40,590 fractional value, and essentially in this particular case of the Knapsack, the 356 00:18:40,590 --> 00:18:44,810 fractional value is going to be the most. You know the, the item with the, the 357 00:18:44,810 --> 00:18:47,680 largest ratio that we can't actually fit in the item. 358 00:18:47,680 --> 00:18:52,265 We fit all of the items which are more valuable per weight, right, better ratio. 359 00:18:52,265 --> 00:18:54,810 Okay? And then we are basically looking at that 360 00:18:54,810 --> 00:18:58,770 last item that we would want to put into the Knapsack, but we could only put in a 361 00:18:58,770 --> 00:19:02,440 fraction of it. That's essentially, you know, the, the 362 00:19:02,440 --> 00:19:05,680 item we're going to branch on, because this is the only item which will have a 363 00:19:05,680 --> 00:19:09,130 fractional value, okay? Now, the question that I have for you, 364 00:19:09,130 --> 00:19:13,100 for you to think of at this point, is that ooh, you know, we're going to take 365 00:19:13,100 --> 00:19:14,890 two things. These are 0,1 variables, right? 366 00:19:14,890 --> 00:19:19,580 So, he's going to be, so that, that the, when we round the fraction downwards or 367 00:19:19,580 --> 00:19:23,940 upwards, what you are going to get is essentially 0 on one side and 1 on the 368 00:19:23,940 --> 00:19:26,060 other side. So, we are going to not take the item or 369 00:19:26,060 --> 00:19:29,130 take the item. So, when we don't take the item, can you 370 00:19:29,130 --> 00:19:31,780 think of what the linear relaxation is going to do, okay? 371 00:19:31,780 --> 00:19:35,524 So, lot of the games in MIP is going to figure out what these [INAUDIBLE] linear 372 00:19:35,524 --> 00:19:38,930 relaxation is going to do. And it's very capricious, you'll see. 373 00:19:38,930 --> 00:19:41,940 Okay? So, in a sense here, you know, what I'm 374 00:19:41,940 --> 00:19:46,077 asking you, is that if we don't take the item, what's going to happen. 375 00:19:46,077 --> 00:19:49,880 Okay, or if we take the item what's going to happen to this linear relaxation, can 376 00:19:49,880 --> 00:19:51,670 you figure that out? Okay? 377 00:19:51,670 --> 00:19:55,240 So in a sense, the question that I'm asking you is, ooh which value is 378 00:19:55,240 --> 00:19:57,390 going to become fractional if you don't take the item? 379 00:19:57,390 --> 00:20:00,350 Okay, think about it. I decide not to take the item. 380 00:20:00,350 --> 00:20:03,080 All the items that were more valuable, what's going to happen to them? 381 00:20:03,080 --> 00:20:05,820 Well, you're going to still take them. And then what you're going to have is a 382 00:20:05,820 --> 00:20:10,590 fractional value for one or more, well, yeah, one or more items, later on. 383 00:20:10,590 --> 00:20:12,900 Okay? So that's what's going to happen. 384 00:20:12,900 --> 00:20:16,540 If you don't take the item. If you take the item, what's happening? 385 00:20:16,540 --> 00:20:19,120 Ooh, before you couldn't put this item in the Knapsack. 386 00:20:19,120 --> 00:20:23,790 No you decided, I want to take that item. So, that means that some of the items 387 00:20:23,790 --> 00:20:27,060 that were before, you won't be able to put inside the Knapsack, okay? 388 00:20:27,060 --> 00:20:30,940 And so the, there is going to be a fractional value for an item that was 389 00:20:30,940 --> 00:20:35,390 more value that's now going to be, that's now going to be fractional okay? 390 00:20:35,390 --> 00:20:38,380 So, this is the kind of reasoning that sometimes you need to think about, you 391 00:20:38,380 --> 00:20:40,320 know, what is the linear relaxation doing. 392 00:20:40,320 --> 00:20:43,870 Because that will give you insight on how to actually improve your models, okay? 393 00:20:43,870 --> 00:20:47,040 So, this is a very simple illustration because this is a really, really simple 394 00:20:47,040 --> 00:20:49,800 example but it's going to drive two points home, okay? 395 00:20:49,800 --> 00:20:53,650 And, and, you know, you'll see them. So, once again, so we had basically these 396 00:20:53,650 --> 00:20:57,180 three, you know, this knapsack with three items, okay? 397 00:20:57,180 --> 00:21:01,926 So, the value of the item is Vi, the weight of the item is Wi, your item 1, 2 398 00:21:01,926 --> 00:21:02,700 ,3. Okay? 399 00:21:02,700 --> 00:21:08,720 So, most valuable item is item 3. Okay, 35 divided by 3 is pretty good. 400 00:21:08,720 --> 00:21:10,210 Okay? Above 10. 401 00:21:10,210 --> 00:21:13,917 Okay? So, a 45 divided by 5 is what is 9 and 48 402 00:21:13,917 --> 00:21:17,270 divided by 8 is some, it's around 6 right? 403 00:21:17,270 --> 00:21:19,916 And so therefore, you know this is the most valuable item that is the next one 404 00:21:19,916 --> 00:21:23,763 and this is the least valuable item from the weights, you know value ratio. 405 00:21:23,763 --> 00:21:26,223 Okay? So, at the top of the, at the top of the 406 00:21:26,223 --> 00:21:29,822 tree at the root node, what you have is a value of 92 and that value of 92 is 407 00:21:29,822 --> 00:21:35,443 basically obtained by selecting item. Well, I think we can let the linear 408 00:21:35,443 --> 00:21:39,573 relaxation do this and this is what the linear relaxation does okay? 409 00:21:39,573 --> 00:21:43,851 So, the linear relaxation is going to take, you know, value, value one for x1, 410 00:21:43,851 --> 00:21:47,953 I'm taking item 1, I'm taking item 3. Okay? 411 00:21:47,953 --> 00:21:50,219 So, these are the two, you know, items with the best ratio. 412 00:21:50,219 --> 00:21:53,939 And then I take only a fraction on the second item, because I can't put the 413 00:21:53,939 --> 00:21:58,132 entire item in okay? And you know once again this is 5 and 3 414 00:21:58,132 --> 00:22:02,445 this is 8 you know I can only take a quarter of that guy. 415 00:22:02,445 --> 00:22:06,913 And this is all you get you know, this this value because you, you, you sum 45 416 00:22:06,913 --> 00:22:12,690 and 35 that's 80 and then a quarter of 48 that's 12 that's the value of the linear 417 00:22:12,690 --> 00:22:15,420 relaxation. So, this linear relaxing is basically 418 00:22:15,420 --> 00:22:17,873 giving you this solution and that particular value. 419 00:22:17,873 --> 00:22:18,820 Okay? What are we going to do? 420 00:22:18,820 --> 00:22:19,950 Okay? I told you. 421 00:22:19,950 --> 00:22:23,340 We look at this thing and we look, ooh, what is the fractional value? 422 00:22:23,340 --> 00:22:26,130 And in this particular case, it's item x2 okay? 423 00:22:26,130 --> 00:22:29,160 So, we're going to branch on x2, and we're going to create two sub-problems, 424 00:22:29,160 --> 00:22:32,308 okay? One where x2 is 0 and one where x2 is 1. 425 00:22:32,308 --> 00:22:35,140 Okay? What happens if x2 is 1, is 0, okay? 426 00:22:35,140 --> 00:22:36,740 So, that's the node that you see over there. 427 00:22:36,740 --> 00:22:39,710 Okay? Now the linear relaxation is 80 okay, you 428 00:22:39,710 --> 00:22:42,200 can select only item 1 and 3. Okay? 429 00:22:42,200 --> 00:22:45,490 So, we solved the linear relaxation at that node, and what do we obtain? 430 00:22:45,490 --> 00:22:49,630 You know, x1 is equal to 1, x2 is equal to 0, x3 is equal to 1. 431 00:22:49,630 --> 00:22:52,990 That's the linear relaxation. The linear relaxation here is finding, 432 00:22:52,990 --> 00:22:56,240 you know, an integral solution. We know that we don't have to branch 433 00:22:56,240 --> 00:22:58,740 anymore. We are fine, okay, this is the best we 434 00:22:58,740 --> 00:23:01,900 would be able to do. It's all integral okay, so we don't have 435 00:23:01,900 --> 00:23:03,820 to branch anymore. It's done, okay? 436 00:23:03,820 --> 00:23:07,395 So, the linear relaxation here is telling you when to stop branching in a sense, 437 00:23:07,395 --> 00:23:10,817 okay? So, we have found a solution we evaluated 438 00:23:10,817 --> 00:23:12,900 okay? The other thing that we wanted to do, is 439 00:23:12,900 --> 00:23:16,330 basically you know, choose x2 is equal to 1, okay? 440 00:23:16,330 --> 00:23:20,790 So we basically fix the value of x2 to 1. We solve the linear relaxation again, and 441 00:23:20,790 --> 00:23:24,284 the linear relaxation is going to give us a value of 71.33. 442 00:23:24,284 --> 00:23:27,570 Okay? You see that now there is this value of 443 00:23:27,570 --> 00:23:31,770 this x3 which is fractional, okay, it was actually, it was actually not fractional 444 00:23:31,770 --> 00:23:35,680 in the original relaxation, okay? So, we know that this is, we would have 445 00:23:35,680 --> 00:23:39,440 to continue branching, but what we have seen here is that the value of the inner 446 00:23:39,440 --> 00:23:42,810 relaxation is 71. The best solution that I have [UNKNOWN] 447 00:23:42,810 --> 00:23:45,680 so I can actually prune that node away already. 448 00:23:45,680 --> 00:23:50,384 So, with one branching essentially I, I solved this problem optimally. 449 00:23:50,384 --> 00:23:53,210 Okay? So, this is essentially illustrating the 450 00:23:53,210 --> 00:23:56,430 various concept here. At the particular node you solve the 451 00:23:56,430 --> 00:23:57,650 linear relaxation. Okay? 452 00:23:57,650 --> 00:24:01,980 You look, the value of the linear, the objective function of the linear program 453 00:24:01,980 --> 00:24:05,446 is basically giving you an optimistic evaluatoin of what the MIP can do. 454 00:24:05,446 --> 00:24:07,360 Okay? At that particular node. 455 00:24:07,360 --> 00:24:08,790 Okay? And then you look at the variables over 456 00:24:08,790 --> 00:24:12,860 there and you take a fractional variable to actually branch okay? 457 00:24:12,860 --> 00:24:15,845 And then you branch left and then you branch right based on that fractional 458 00:24:15,845 --> 00:24:17,180 value. Okay? 459 00:24:17,180 --> 00:24:21,570 Now, one of the questions that you have to think of is when is branching bound 460 00:24:21,570 --> 00:24:23,690 going to be effective? Okay? 461 00:24:23,690 --> 00:24:27,530 What is it's going to be really effective is the value of the linear relaxation is 462 00:24:27,530 --> 00:24:29,790 tight. It's very, very close if the linear 463 00:24:29,790 --> 00:24:32,804 programming relaxation is very close to the optimal value of the MIP. 464 00:24:32,804 --> 00:24:34,490 Okay? Is that sufficient? 465 00:24:34,490 --> 00:24:35,520 huh? Think about it. 466 00:24:35,520 --> 00:24:39,730 So, if I tell you, I guarantee, okay, that this linear relaxation is going to 467 00:24:39,730 --> 00:24:44,150 be 0.5%, always of the best value of the MIP. 468 00:24:44,150 --> 00:24:49,070 Is that sufficient for the MIP to actually behave nicely all the time? 469 00:24:49,070 --> 00:24:50,770 Okay? Question for you. 470 00:24:50,770 --> 00:24:52,760 Okay? I wish we had quiz in this class. 471 00:24:52,760 --> 00:24:55,080 We don't, but anyway. So think about it. 472 00:24:55,080 --> 00:24:56,383 Is it sufficient? Okay? 473 00:24:56,383 --> 00:24:59,829 So, what is a good MIP model? A good MIP model is going to be a model 474 00:24:59,829 --> 00:25:04,199 which is a good linear relaxation. It's not sufficient necessarily. 475 00:25:04,199 --> 00:25:05,834 Okay? I answered that question, right? 476 00:25:05,834 --> 00:25:09,067 But this is a necessary condition, you want a model with a very good linear 477 00:25:09,067 --> 00:25:11,023 relaxation. Why? 478 00:25:11,023 --> 00:25:12,657 Because you're going to prune the search space much better. 479 00:25:12,657 --> 00:25:15,535 Okay? Now, which variable should we branch on? 480 00:25:15,535 --> 00:25:17,992 So, we have a lot of variables, it seems that we have plenty of variables with 481 00:25:17,992 --> 00:25:20,521 fractional values. Which one are we going to branch on? 482 00:25:20,521 --> 00:25:22,894 Okay? So, one of the good heuristic is to 483 00:25:22,894 --> 00:25:26,156 branch with the most fractional value okay? 484 00:25:26,156 --> 00:25:29,448 So why, why would we do that well, you know once again exaggerate. 485 00:25:29,448 --> 00:25:32,712 Assume that you variable which is not very fractional okay? 486 00:25:32,712 --> 00:25:37,085 So, it's like you know 0.99999999999 okay? 487 00:25:37,085 --> 00:25:40,854 And it can take value 0, 1 okay? So, when it is 0.9999999 [UNKNOWN] I hope 488 00:25:40,854 --> 00:25:44,286 I you know, use the same number of nines, but that means that it's really close to 489 00:25:44,286 --> 00:25:48,630 one, probably branching there doesn't make too much sense. 490 00:25:48,630 --> 00:25:52,223 If a variable is 0.5 what does that mean? It means that the linear relaxation is 491 00:25:52,223 --> 00:25:55,439 saying, hm, maybe I should take this item hm, maybe I should not take this item hm, 492 00:25:55,439 --> 00:25:58,352 I do not really know. Okay? 493 00:25:58,352 --> 00:26:02,005 And so therefore these are the type of variables that you need to branch on. 494 00:26:02,005 --> 00:26:06,680 Okay? So, this is a basic introduction to MIP. 495 00:26:06,680 --> 00:26:10,090 Next time we are going to see really cute things, on how you can actually build MIP 496 00:26:10,090 --> 00:26:12,436 model. What does it mean to be a good MIP model? 497 00:26:12,436 --> 00:26:13,970 Okay? come back. 498 00:26:13,970 --> 00:26:15,150 Thank you.