1 00:00:00,280 --> 00:00:03,890 Okay, discrete optimization, mixed integer programming, branch and cut, 2 00:00:03,890 --> 00:00:04,990 second lecture. Okay? 3 00:00:04,990 --> 00:00:07,450 So, this is the real stuff now. Okay? 4 00:00:07,450 --> 00:00:11,710 So one of the things that we saw in the last lecture is that we can generate 5 00:00:11,710 --> 00:00:13,750 these polyhedron cuts. Okay? 6 00:00:13,750 --> 00:00:18,430 But one other thing that we did was basically adding them all inside Inside 7 00:00:18,430 --> 00:00:20,270 the, you know, formulation, the beginning. 8 00:00:20,270 --> 00:00:23,640 That's not exactly how branch and cut works, so what I want to go and, what I 9 00:00:23,640 --> 00:00:28,870 want to do now, is take this concept and then tell you really what a branch and 10 00:00:28,870 --> 00:00:30,500 cut algorithm is doing. Okay? 11 00:00:30,500 --> 00:00:33,979 So we're going to see two things, cover cuts, okay, and you'll see why, you know, 12 00:00:33,979 --> 00:00:38,840 we, we, we'll talk about them, they're very, you know, very frequent in in mixed 13 00:00:38,840 --> 00:00:43,100 integer programs, and then we move to the TSP, which is probably the biggest 14 00:00:43,100 --> 00:00:47,017 success stories of optimization. We can solve really really large TSP 15 00:00:47,017 --> 00:00:53,439 optimally at this point. Okay, so cover caps first. 16 00:00:53,439 --> 00:00:56,795 Cover caps we are looking at constraint which are inequalities. 17 00:00:56,795 --> 00:01:01,280 Okay, linear inequalities, a sum of coefficients and variables which are 18 00:01:01,280 --> 00:01:06,250 smaller than b The simplest kind of stuff that you find all the time inside your 19 00:01:06,250 --> 00:01:07,020 math. Okay? 20 00:01:07,020 --> 00:01:12,720 So sum, you know, coefficient, ai, aj, you know, multiplied by a, a binary 21 00:01:12,720 --> 00:01:16,294 variable, xj 01, is to be smaller than b, okay? 22 00:01:16,294 --> 00:01:20,710 So, so you know can we find facets for these constraints okay. 23 00:01:20,710 --> 00:01:25,270 Can we find facet of the pole which have arrived from these constraints okay. 24 00:01:25,270 --> 00:01:30,260 And the key concept here you know the title is cover cut right is the concept 25 00:01:30,260 --> 00:01:34,440 of cover and essentially what you need to think about is a cover is going to be a 26 00:01:34,440 --> 00:01:38,180 set of variables if you set them all to 1 you're going to violate the constraints 27 00:01:38,180 --> 00:01:40,570 okay. It's basically telling you these 28 00:01:40,570 --> 00:01:43,680 variables not all of them can be 1. Okay? 29 00:01:43,680 --> 00:01:47,433 And so basically, you know, is what you do is you look at the subset of these 30 00:01:47,433 --> 00:01:48,430 variables. Okay? 31 00:01:48,430 --> 00:01:51,350 You look at the coefficients and if you sum all these coefficient, they are 32 00:01:51,350 --> 00:01:53,860 greater than b. And therefore, you know, you know that if 33 00:01:53,860 --> 00:01:57,042 you select all these variables, put them to 1, you going to violate the 34 00:01:57,042 --> 00:01:57,940 constraints. Okay? 35 00:01:57,940 --> 00:02:01,100 So, that's the concept of cover. Basically, these variable cannot all be 36 00:02:01,100 --> 00:02:03,100 selected at the same time. Okay? 37 00:02:03,100 --> 00:02:07,520 And so a cover is going to be maximal, minimal, okay so that's the opposite of 38 00:02:07,520 --> 00:02:12,300 maximal too, it's going to be minimal if you remove one of these variables, okay, 39 00:02:12,300 --> 00:02:17,216 it's not a cover anymore, okay? It's like the strongest possible cover, 40 00:02:17,216 --> 00:02:20,430 okay? So, so, so when you look at these covers 41 00:02:20,430 --> 00:02:25,050 now, so we have a particular constraints there, we take a cover, We, this, so I'm 42 00:02:25,050 --> 00:02:27,450 going to show you an inequality which is valid. 43 00:02:27,450 --> 00:02:29,590 Okay? And so what we do is basically that's 44 00:02:29,590 --> 00:02:30,540 what I told you before. Right? 45 00:02:30,540 --> 00:02:33,240 If we select all these variables at the same time. 46 00:02:33,240 --> 00:02:34,930 Right? We can evaluate the constraints. 47 00:02:34,930 --> 00:02:38,270 So the constraints is basically say, saying, at least one of them has to be 48 00:02:38,270 --> 00:02:43,020 zero, or the sum of all these guys ahs to be smaller than the size of this cover 49 00:02:43,020 --> 00:02:45,600 minus one. You can't select all the variables. 50 00:02:45,600 --> 00:02:48,950 This is what this is telling you. You can't select all the variables. 51 00:02:48,950 --> 00:02:52,850 So in a sense the sum of them is to be smaller than the size of the set minus 52 00:02:52,850 --> 00:02:54,500 one, or at least one of them has to be zero. 53 00:02:54,500 --> 00:02:57,345 We can think about it hopefully, and that's what we're going to do anyway. 54 00:02:57,345 --> 00:03:00,500 Okay? So these are the cover cuts, okay? 55 00:03:00,500 --> 00:03:03,500 So if you look at these constraints here, this is a big constraint, right? 56 00:03:03,500 --> 00:03:09,430 So, seven variables, with coefficient, you know, 11, 6, 6, 5, 5, 4, 1, OK? 57 00:03:09,430 --> 00:03:12,880 And that has to be smaller, the sum of these things have to be smaller, these 58 00:03:12,880 --> 00:03:15,100 variables. Have to be smaller than 19, okay? 59 00:03:15,100 --> 00:03:19,190 Can we find a cover cut, okay? So that's going to be easy, right? 60 00:03:19,190 --> 00:03:22,180 So we take in this particular case the coefficients by, you know, this is 61 00:03:22,180 --> 00:03:24,440 decreasing order. I made it easy for you, right? 62 00:03:24,440 --> 00:03:28,370 So this is 11, 6, 6. So that's already 23, right? 63 00:03:28,370 --> 00:03:32,820 So this is, this is greater than 19. So this is This is a cover, okay. 64 00:03:32,820 --> 00:03:38,230 And, but, because of that, you know that x1 plus x2 plus x3 has to be smaller or 65 00:03:38,230 --> 00:03:40,790 equal to 2. You can only select two of these 66 00:03:40,790 --> 00:03:43,210 variables, hence, you know, to have a feasible solution. 67 00:03:43,210 --> 00:03:48,716 Okay? Now let's look at x4, x5, x6, x3, x4, x5, 68 00:03:48,716 --> 00:03:51,120 and x6. Okay, if you sum all these things 69 00:03:51,120 --> 00:03:56,320 together Once again you get 20, this is greater than 19, so this is also a cover 70 00:03:56,320 --> 00:03:59,680 and this is the cover inequality that results from them, okay. 71 00:03:59,680 --> 00:04:03,220 The sum of these four variables has to be smaller or equal to 3, okay. 72 00:04:03,220 --> 00:04:07,250 So this is essential, so you, you start from inequality like this with, you know, 73 00:04:07,250 --> 00:04:12,020 big coefficient, and then you have a simple cover inequality there, which is 74 00:04:12,020 --> 00:04:17,639 limiting the set of the sum of, you know, a subset of the variables. 75 00:04:17,639 --> 00:04:19,700 Okay? These are cover cuts, okay? 76 00:04:19,700 --> 00:04:23,170 Now, you can extend, you can make them stronger, and the key idea is that if you 77 00:04:23,170 --> 00:04:27,390 ever cover cut, if you ever cover cut, you can extend it by taking other 78 00:04:27,390 --> 00:04:30,210 variables. Whose coefficients are greater than all 79 00:04:30,210 --> 00:04:31,790 the coefficients of the count. Okay? 80 00:04:31,790 --> 00:04:34,460 So this is what this formula is explaining. 81 00:04:34,460 --> 00:04:39,495 So know instead of leaving the sum all over the set, you have this extended set, 82 00:04:39,495 --> 00:04:42,830 okay? You know you extend the cut c, okay, and 83 00:04:42,830 --> 00:04:48,030 what you do is you take up usually c but also all the other you know variables 84 00:04:48,030 --> 00:04:51,770 whose coefficients is greater than all the coefficients of, of C. 85 00:04:51,770 --> 00:04:55,670 Okay so, you know, by definition that these variables okay so they will, they, 86 00:04:55,670 --> 00:05:00,130 they will essentially, they will, the cut will be, will be stronger. 87 00:05:00,130 --> 00:05:03,312 Let me show you an example, it is easier on the example. 88 00:05:03,312 --> 00:05:06,790 So you see essentially the, the cover cut that we have seen. 89 00:05:06,790 --> 00:05:11,526 We add the cut which is x4, you know, x3, x4, x5, and x6 has to be smaller or equal 90 00:05:11,526 --> 00:05:13,478 to 3. You know, you see that the coefficient of 91 00:05:13,478 --> 00:05:18,240 x1 and x2 are greater than all these coefficients, so you make the case 92 00:05:18,240 --> 00:05:22,510 stronger by adding x1 and x2 on this. If the coefficient would be weaker it 93 00:05:22,510 --> 00:05:26,570 would not be you know, as strong. But here the coefficients are always at 94 00:05:26,570 --> 00:05:29,080 least as strong as the coefficients of the other ones, okay? 95 00:05:29,080 --> 00:05:33,802 So, that's the stronger cover. Okay so this is the idea of branch and 96 00:05:33,802 --> 00:05:35,680 cut, okay? So the branch and cut, you know, consists 97 00:05:35,680 --> 00:05:40,330 of modeling first if the problem is okay. Now have a bit, okay. 98 00:05:40,330 --> 00:05:44,360 So you can use the linear relaxation if the linear relaxation is giving you an 99 00:05:44,360 --> 00:05:49,590 integral solution. Finish okay you have an optimal solution. 100 00:05:49,590 --> 00:05:54,770 Otherwise what you do is, you basically find the polyhedral cut, okay, which cuts 101 00:05:54,770 --> 00:05:57,079 the optimal solution to the linear relaxation. 102 00:05:57,079 --> 00:05:59,970 That's the key step, okay? And obviously you would like to have a 103 00:05:59,970 --> 00:06:03,770 facet if it's possible. And so if you find such a beautiful 104 00:06:03,770 --> 00:06:05,440 thing, right? So what you're going to do is, you go 105 00:06:05,440 --> 00:06:08,040 back to step 2, you solve the linear relaxation, it's stronger. 106 00:06:08,040 --> 00:06:11,110 Why is it stronger? Because you cut the linear, the optimal 107 00:06:11,110 --> 00:06:14,270 solution to the linear relaxation, and you iterate this stuff. 108 00:06:14,270 --> 00:06:18,610 Okay, and at some point you can't find any of these cuts anymore because you've 109 00:06:18,610 --> 00:06:21,630 found all of them or it's too tough to actually find them okay. 110 00:06:21,630 --> 00:06:24,990 And then what you do is branch and then you can repeat these steps, or you can at 111 00:06:24,990 --> 00:06:28,510 some point decide that's it's not even worth generating more cuts okay. 112 00:06:28,510 --> 00:06:32,620 But this is the basic framework for branch and cut okay. 113 00:06:32,620 --> 00:06:37,610 Now the key point here okay, is that we have to generate these polyhedral cut 114 00:06:37,610 --> 00:06:40,620 that are going to remove the value of the optimal solution. 115 00:06:40,620 --> 00:06:45,130 Okay, the linear relaxation, okay? So this is what we need to do, okay? 116 00:06:45,130 --> 00:06:48,070 So we are not going to do what I did in the previous lecture, which is just 117 00:06:48,070 --> 00:06:49,940 listing all the possible cuts we could find. 118 00:06:49,940 --> 00:06:54,020 Okay, what we want to do is, at some point, we look at this linear relaxation, 119 00:06:54,020 --> 00:06:56,230 and you say, wow, okay, so I want to cut it. 120 00:06:56,230 --> 00:06:58,420 Okay? So to give you an analogy, you know, you 121 00:06:58,420 --> 00:07:01,170 have to think about, you know, feeding babies, right? 122 00:07:01,170 --> 00:07:04,070 So so there are two types of parents, right? 123 00:07:04,070 --> 00:07:06,460 So when you have a night, you know, a new kid. 124 00:07:06,460 --> 00:07:10,390 So what you do, you have the parents that read the books and do everything by the 125 00:07:10,390 --> 00:07:10,920 rule. Okay. 126 00:07:10,920 --> 00:07:16,300 It's written in the book that this kid has to basically you know, be eating 127 00:07:16,300 --> 00:07:19,090 every three hours. So this poor kid is sleeping but you 128 00:07:19,090 --> 00:07:22,190 know, three hours has gone so they wake up this kid and feed the kid. 129 00:07:22,190 --> 00:07:24,410 Right. And so then try to put the kid to sleep 130 00:07:24,410 --> 00:07:26,420 and that never works of course. Okay. 131 00:07:26,420 --> 00:07:29,480 So these are, you know, these are you know, essentially generating all the 132 00:07:29,480 --> 00:07:30,540 cuts. Okay? 133 00:07:30,540 --> 00:07:32,340 and then they are the cruel parents, right? 134 00:07:32,340 --> 00:07:34,970 So I'm not saying this is better or worse, right. 135 00:07:34,970 --> 00:07:38,340 But the other parents are saying this kid is you know, sleeping, you know 136 00:07:38,340 --> 00:07:40,940 beautifully. I'm going to let this kid sleep and then 137 00:07:40,940 --> 00:07:45,640 when the kids you know, wake up. And yell you don't know why, but give 138 00:07:45,640 --> 00:07:48,060 basically feed that part. That's demand feeding. 139 00:07:48,060 --> 00:07:51,930 That's what we are doing. We generate these cuts by demands. 140 00:07:51,930 --> 00:07:55,000 Okay. So this is what we going to do and that's 141 00:07:55,000 --> 00:07:58,740 called a seperation problem okay. So what you know is that you have this 142 00:07:58,740 --> 00:08:02,950 optimal solution, okay, to the linearly relaxation and what you want to do is you 143 00:08:02,950 --> 00:08:06,240 want to look. A particular cut, a particular class of 144 00:08:06,240 --> 00:08:11,300 cut that's going to remove the ultimate solution to this linear relaxation, okay, 145 00:08:11,300 --> 00:08:13,350 so this is what we do for cover cut, okay. 146 00:08:13,350 --> 00:08:17,170 So, we've this optimal solution to the linear relaxation and we are wondering, 147 00:08:17,170 --> 00:08:21,180 can I find cover cut that's going to remove this optimal solution of the 148 00:08:21,180 --> 00:08:25,120 linear relaxation, okay. So we know that the cover ca-, the cover 149 00:08:25,120 --> 00:08:28,390 inequality, okay? So this is this b's, re-, re-, vir, 150 00:08:28,390 --> 00:08:32,040 saying that the se-, this subset of variables, if I sum them to one, okay, 151 00:08:32,040 --> 00:08:36,550 is, thas, if I sum them, you know, they, they can't all be one, so they have to 152 00:08:36,550 --> 00:08:41,305 sum, and, you know The sum, their sum should be smaller or equal to the 153 00:08:41,305 --> 00:08:45,910 cardinality of the cover minus 1. So that can be rewritten oh at least one 154 00:08:45,910 --> 00:08:49,100 of them maybe 0 so you do minus the variable okay. 155 00:08:49,100 --> 00:08:54,260 So that's going to be 1 if the variable is 0 or 0 if the variable is 0 okay. 156 00:08:54,260 --> 00:08:57,680 And so you're basically saying here is that the number of variables which is 0 157 00:08:57,680 --> 00:09:01,570 is to be greater than 1 okay. And so essentially finding a cover cut, 158 00:09:01,570 --> 00:09:04,240 okay, will require two condition. Okay? 159 00:09:04,240 --> 00:09:08,470 So, we one of you see to find a cover, that's the second conditions that you 160 00:09:08,470 --> 00:09:09,080 have. Okay? 161 00:09:09,080 --> 00:09:13,050 So when you take the sum of this, when you take, when you take the sum of the 162 00:09:13,050 --> 00:09:15,960 elements in C, okay, the elements in the cover. 163 00:09:15,960 --> 00:09:19,640 That is to be greater than, you know, the sum of the coefficient is to be greater 164 00:09:19,640 --> 00:09:21,350 than the right hand side of the constraint. 165 00:09:21,350 --> 00:09:23,470 Okay? And then we want to be sure. 166 00:09:23,470 --> 00:09:28,020 We want to, we want to have the property that in the linear relaxation these guys 167 00:09:28,020 --> 00:09:32,840 are smaller or equal to one, so they are basically violating the cover cut, okay? 168 00:09:32,840 --> 00:09:37,030 So essentially what we want to find is the cover cut that vi, that is violated 169 00:09:37,030 --> 00:09:40,910 by the linear relaxation, okay, and is a cut, okay, is a cover cut, okay? 170 00:09:40,910 --> 00:09:44,640 So we want these two properties. If you find that essentially what we're 171 00:09:44,640 --> 00:09:47,960 doing is generating these cuts on demand. Okay? 172 00:09:47,960 --> 00:09:50,090 So you say ooh, I have this linear relaxation. 173 00:09:50,090 --> 00:09:52,380 Okay? I want to find a cover cut, and that 174 00:09:52,380 --> 00:09:55,350 cover cut has to violate this, has to be violated. 175 00:09:55,350 --> 00:09:57,330 That's what you are trying to do. Okay? 176 00:09:57,330 --> 00:10:01,360 So, essentially, this is you know, we have two constraints here, okay, so we 177 00:10:01,360 --> 00:10:05,200 could view that as a feasibility problem But we can also view that as an 178 00:10:05,200 --> 00:10:07,680 optimization problem because that's what linear programming does. 179 00:10:07,680 --> 00:10:11,010 Right so or you mixed integer programing does. 180 00:10:11,010 --> 00:10:13,490 So what we do here is minimize this expression. 181 00:10:13,490 --> 00:10:16,080 Okay, that's the expression that we want to be smaller or equal to one. 182 00:10:16,080 --> 00:10:19,630 Smaller than one and then we have a definition of a cover cutter so 183 00:10:19,630 --> 00:10:24,460 essentially what you do is you look for these variables that I okay that J in 184 00:10:24,460 --> 00:10:26,890 this particular case okay. So you look at all of them these are 185 00:10:26,890 --> 00:10:30,310 essentially the you know all the variables that indices of the variables 186 00:10:30,310 --> 00:10:34,870 inside the inside the constraints you want to select a subset of them which 187 00:10:34,870 --> 00:10:37,710 violate the cut and minimize this function okay. 188 00:10:37,710 --> 00:10:41,310 And so now if the value of this function is smaller or equal to 1 you have a cover 189 00:10:41,310 --> 00:10:44,030 cut. Okay and all the elements which are equal 190 00:10:44,030 --> 00:10:48,020 to 1 are the cover. So essentially if you solve this linear 191 00:10:48,020 --> 00:10:51,520 program, okay? This this mix integer problem okay. 192 00:10:51,520 --> 00:10:54,400 So you have a cover cap, you find a cover cap. 193 00:10:54,400 --> 00:10:58,350 Now you tell me wow wow wow you guys are trying to solve mix integer program and 194 00:10:58,350 --> 00:11:01,520 you want to solve another mix integer program to solve that integer program and 195 00:11:01,520 --> 00:11:04,510 you want to do that repeatedly you know what are you doing? 196 00:11:04,510 --> 00:11:07,900 Okay, and so let me address that question in a moment. 197 00:11:07,900 --> 00:11:10,315 Okay, so but first let me give you an example okay. 198 00:11:10,315 --> 00:11:15,470 So, so, what you see here is the, is a big constraint I say bigger than the 199 00:11:15,470 --> 00:11:17,970 other time, you know, the other one that I've showed you before, the right hand 200 00:11:17,970 --> 00:11:23,025 sided 178, and you see coefficients go, you know, ranging from 45 to, you know, 201 00:11:23,025 --> 00:11:24,540 125. Okay. 202 00:11:24,540 --> 00:11:26,940 Now, the linear. Assume that the linear relaxation is 203 00:11:26,940 --> 00:11:31,656 giving you this optimal solution, okay. So, you see that the 1st one is 0, the 204 00:11:31,656 --> 00:11:36,840 2nd one is 0, the 3rd one is 3 quarter, the 4th one is 1, 1/2, and the next one 205 00:11:36,840 --> 00:11:39,270 is 0, okay? So, how do you generate. 206 00:11:39,270 --> 00:11:43,510 Okay, so what is the, what is the big, big program we have to solve to find the 207 00:11:43,510 --> 00:11:47,100 cover cut? So this is the, this is the mid program 208 00:11:47,100 --> 00:11:49,480 actually doing, solving the separation problem, okay? 209 00:11:49,480 --> 00:11:55,280 You minimize that one, why is that 1? Because essentially you take 1 minus the 210 00:11:55,280 --> 00:11:57,520 value in the linear relaxation, which is 0, okay? 211 00:11:57,520 --> 00:12:00,810 So that's why you have that 1, then you have that 2 for the same reason. 212 00:12:00,810 --> 00:12:04,340 Then you have 1 fourth of that tree. Why? 213 00:12:04,340 --> 00:12:11,190 Because you see essentially 3/4 a year so 1 minus 3/4 is 1/4 and that's how you get 214 00:12:11,190 --> 00:12:13,420 this objective function. That's essentially what we saw in the 215 00:12:13,420 --> 00:12:15,630 previous slide. And then, of course, you have to have a 216 00:12:15,630 --> 00:12:16,760 cover cut. Okay. 217 00:12:16,760 --> 00:12:21,270 And so you want, basically, that the choice of the value, the 0 1 values for 218 00:12:21,270 --> 00:12:26,200 disease is going to basically be greater than 178 when multiplied by the 219 00:12:26,200 --> 00:12:27,550 coefficient. Okay? 220 00:12:27,550 --> 00:12:31,710 So essentially this is, this is the mid program that we have to solve for finding 221 00:12:31,710 --> 00:12:35,400 this, for finding this cut. So this is the separation problem. 222 00:12:35,400 --> 00:12:39,830 Okay, if we find the solution to this, we will separating, you know, the, we left 223 00:12:39,830 --> 00:12:43,940 final cut, which essentially separate. The, the solution to the linear 224 00:12:43,940 --> 00:12:46,870 relaxation and the convex cell. Okay? 225 00:12:46,870 --> 00:12:52,060 So this is, you know, I told you this is this beautiful mixed integer program, and 226 00:12:52,060 --> 00:12:55,730 so the question that I'm asking you is, you know, does it remind you of 227 00:12:55,730 --> 00:12:57,110 something? Okay? 228 00:12:57,110 --> 00:13:01,770 So it's minimizing your linear sum of 0, 1 variables subject to sum, you know, the 229 00:13:01,770 --> 00:13:03,925 sum of these variables is to be greater than something. 230 00:13:03,925 --> 00:13:07,130 Okay. Well, look, if I do a variable 231 00:13:07,130 --> 00:13:10,950 transformation. Okay, if we write the jen G into one 232 00:13:10,950 --> 00:13:14,210 minus Y G. Okay, what do I get? 233 00:13:14,210 --> 00:13:16,980 Well, this minimum is going to be a maximum. 234 00:13:16,980 --> 00:13:19,145 Okay. So we're going to maximize some of the 235 00:13:19,145 --> 00:13:23,380 variables. And this inequality here, you know, which 236 00:13:23,380 --> 00:13:26,480 is greater than, is going to turn into an inequality which is smaller than, is 237 00:13:26,480 --> 00:13:28,520 going to be a sum of variables with coefficient. 238 00:13:28,520 --> 00:13:32,680 Smaller than something, so what we have there is a knapsack problem. 239 00:13:32,680 --> 00:13:34,960 Okay? So it's like, you know, we have closed 240 00:13:34,960 --> 00:13:37,520 the loop, in a sense. We started with the knapsack and now we 241 00:13:37,520 --> 00:13:40,740 are generating these branch and cut using a knapsack algorithm here. 242 00:13:40,740 --> 00:13:44,180 Okay? So, this essentially the way you can do 243 00:13:44,180 --> 00:13:47,780 branch and cut, okay. So you basically, you basically solve the 244 00:13:47,780 --> 00:13:50,240 linear relaxation, and then you have various class of cuts, and then you say, 245 00:13:50,240 --> 00:13:56,120 ooh, can I generate a cut That's going to separate, separate, the optimal solution 246 00:13:56,120 --> 00:13:59,110 to the lineal relaxation. And you saw this separation problem and 247 00:13:59,110 --> 00:14:04,461 find this guess on demand. So, before we move to the TSP which is 248 00:14:04,461 --> 00:14:07,350 going to be kind of You know, big notation. 249 00:14:07,350 --> 00:14:10,410 So, I want to go into a little bit of history here. 250 00:14:10,410 --> 00:14:12,420 Okay. And we're going to talk about the, the 251 00:14:12,420 --> 00:14:14,650 Seven Bridges of Konigsberg. Okay. 252 00:14:14,650 --> 00:14:18,840 And so is the city where Euler, the beauty, you know, the great mathematician 253 00:14:18,840 --> 00:14:21,370 Euler was living. And this is a very interesting city, 254 00:14:21,370 --> 00:14:24,420 because it is going to have, as the title indicates, seven bridges. 255 00:14:24,420 --> 00:14:27,380 Right, so let's zoom. You see the river, you know, in blue, 256 00:14:27,380 --> 00:14:30,260 okay. And you see all these bridges in red, I 257 00:14:30,260 --> 00:14:31,740 assume. Okay? 258 00:14:31,740 --> 00:14:35,730 And so what Euler asked, you know, I think this is what he was spending his 259 00:14:35,730 --> 00:14:39,350 free time doing. He said, can I find a tour which would 260 00:14:39,350 --> 00:14:44,995 go, you know, which would walk over every one of these seven bridges exactly once? 261 00:14:44,995 --> 00:14:47,570 Okay? So this is, for instance, the tour that 262 00:14:47,570 --> 00:14:53,510 you see here, okay, which is basicaly going over five of the bridges. 263 00:14:53,510 --> 00:14:58,390 Okay, we can go to five of them exactly one, can we go to seven exactly once. 264 00:14:58,390 --> 00:15:00,740 Okay? And so what Euler did is one of the 265 00:15:00,740 --> 00:15:04,880 founder of use in graph theory, is basically represent that is beautiful 266 00:15:04,880 --> 00:15:06,540 pictures. Okay, right? 267 00:15:06,540 --> 00:15:09,570 And then you looked at that picture and said this is really a graph. 268 00:15:09,570 --> 00:15:12,520 Okay. So, I can associate a note with every one 269 00:15:12,520 --> 00:15:14,610 of these land masses. Okay? 270 00:15:14,610 --> 00:15:18,780 And know the edges between these vertices are going to be the bridges, okay? 271 00:15:18,780 --> 00:15:23,479 So, you see that here, you know, I have 2 bridges between these 2 you know 272 00:15:23,479 --> 00:15:27,090 landmass. Okay and so the question was can I have 2 273 00:15:27,090 --> 00:15:32,500 can I have 2 that visit every one of the edges exactly once okay. 274 00:15:32,500 --> 00:15:35,750 So an earlier look at this problem and say no, I can prove that this is 275 00:15:35,750 --> 00:15:38,540 impossible you don't have to try working this thing forever. 276 00:15:38,540 --> 00:15:43,690 Okay, and one of the ways, the way you actually prove that is by looking at 277 00:15:43,690 --> 00:15:46,980 every one of these vertices. Okay, and of, usually when you walk from 278 00:15:46,980 --> 00:15:50,130 one vertex to another, you go to another popular point and then you go to another 279 00:15:50,130 --> 00:15:52,110 one. So, as soon as you enter a vertex, you 280 00:15:52,110 --> 00:15:55,080 have to leave it, right? So, that basically means that if you go 281 00:15:55,080 --> 00:15:58,982 over all the bridges, okay, you have to make sure that the degree of every one 282 00:15:58,982 --> 00:16:01,690 has to be even. Otherwise you will come and there will be 283 00:16:01,690 --> 00:16:03,750 no bridge to, get out of it. Right? 284 00:16:03,750 --> 00:16:07,170 And so he could prove that in this particular case you could never, never 285 00:16:07,170 --> 00:16:11,858 walk exactly once on these seven bridges. Because, you know, these, all these 286 00:16:11,858 --> 00:16:15,170 vertices here at, you know, an, an odd degree. 287 00:16:15,170 --> 00:16:18,160 Okay? So in a sense he invented kind of these 288 00:16:18,160 --> 00:16:21,300 degree constraints. And they are going to be very useful for 289 00:16:21,300 --> 00:16:24,400 our next topic. Which is the traveling salesman problem. 290 00:16:24,400 --> 00:16:28,140 Now, the traveling salesman problem can be seen as the, you know, the dual kind 291 00:16:28,140 --> 00:16:31,420 of, well, it's not really dual from a mathematical sense, but it's basically 292 00:16:31,420 --> 00:16:36,970 the opposite of the, of the, of the earlier two problems. 293 00:16:36,970 --> 00:16:41,410 What we want to do here is to visit exactly, you know, all of the vertices 294 00:16:41,410 --> 00:16:43,960 exactly once, not the edges. Okay? 295 00:16:43,960 --> 00:16:47,240 And there is a big difference between the yellow tour and this, the Traveling 296 00:16:47,240 --> 00:16:49,350 Salesman Problem. One is easy to solve, the other one is 297 00:16:49,350 --> 00:16:51,170 very complicated to solve. Okay? 298 00:16:51,170 --> 00:16:56,250 So, so what we do in the TSP is we want to find the two which is visiting every 299 00:16:56,250 --> 00:16:58,860 one of these vertices exactly once. Okay? 300 00:16:58,860 --> 00:17:02,350 And so the first thing that we have to do now is to try to model this as a MIP. 301 00:17:02,350 --> 00:17:04,510 Right? So when we do one to do branch and cat, 302 00:17:04,510 --> 00:17:06,890 what you do is you model this thing as a, as a MIP. 303 00:17:06,890 --> 00:17:08,410 Okay? So you have to choose a decision 304 00:17:08,410 --> 00:17:10,332 variable, the constraints, the objective function. 305 00:17:10,332 --> 00:17:11,990 Okay? Now there are many models to do that, 306 00:17:11,990 --> 00:17:13,760 right? So, and we're going to use one which is 307 00:17:13,760 --> 00:17:16,230 very, very good from a computational standpoint. 308 00:17:16,230 --> 00:17:18,300 But you see we've got to build it step by step. 309 00:17:18,300 --> 00:17:21,450 Okay? It's going to be kind of nice. 310 00:17:21,450 --> 00:17:25,540 So, the decision variable here, I'm going to be deciding whether an edge is 311 00:17:25,540 --> 00:17:28,160 part of the tour or not. So, we're going look at every edges. 312 00:17:28,160 --> 00:17:30,150 Okay? And we, we'll associated decision 313 00:17:30,150 --> 00:17:34,020 variable, a binary decision variable, depending is whether that particular edge 314 00:17:34,020 --> 00:17:36,830 is part of an optimal tour or not. Okay. 315 00:17:36,830 --> 00:17:39,150 And so the constraints are going to be this degree constraints. 316 00:17:39,150 --> 00:17:42,820 We know that if we go to a vertex, we have to get out of the vertex, okay. 317 00:17:42,820 --> 00:17:47,330 So, and since we can visit the vertex exactly once, okay. 318 00:17:47,330 --> 00:17:51,040 So, it's not like it has to be even, it has to be exactly two, you want to go the 319 00:17:51,040 --> 00:17:53,090 vertex and you want to get out. Okay. 320 00:17:53,090 --> 00:17:57,880 So essentially if you look at the vertex Two of its adjacent edges, okay, exactly 321 00:17:57,880 --> 00:18:00,180 two of these adjacent edges have to be one. 322 00:18:00,180 --> 00:18:03,660 Okay? So this is the first, so I'm going to 323 00:18:03,660 --> 00:18:07,730 kill you with notation now, but this is essentially the basic of the, of, of the 324 00:18:07,730 --> 00:18:10,550 model, of the first, you know, MIP model. Okay? 325 00:18:10,550 --> 00:18:12,900 So I told you I'm going to kill you with these notations. 326 00:18:12,900 --> 00:18:15,470 So I'm going to try to go slowly, so that you can. 327 00:18:15,470 --> 00:18:18,850 Memorize everything, okay? But essentially the decision variables 328 00:18:18,850 --> 00:18:22,340 are going to be very easy. You know, for every edge e, you have Xe, 329 00:18:22,340 --> 00:18:25,830 which is a decision variable, which is zero if you don't get the edges in an 330 00:18:25,830 --> 00:18:28,400 optimal solution in one if you take it. Okay? 331 00:18:28,400 --> 00:18:31,630 No V is always going to be the set of vertices, E is always going to be the set 332 00:18:31,630 --> 00:18:32,510 of edges. Okay? 333 00:18:32,510 --> 00:18:34,715 And then the three notation are important. 334 00:18:34,715 --> 00:18:37,350 Okay, so the three, the next three notation are important. 335 00:18:37,350 --> 00:18:40,530 So, I'm going to use delta V. Okay. 336 00:18:40,530 --> 00:18:44,150 As the set of edges which are adjacent to vertex V. 337 00:18:44,150 --> 00:18:48,080 So, I'll look at the vertex and then I'll look at all the edges which has V as one 338 00:18:48,080 --> 00:18:50,560 of their end points and thus delta V. Okay. 339 00:18:50,560 --> 00:18:54,400 So, when you see delta V, it's the edges associated with V. 340 00:18:54,400 --> 00:18:55,660 Okay. So far so good? 341 00:18:55,660 --> 00:18:58,920 Okay. Delta V the edges adjacent to V Now delta 342 00:18:58,920 --> 00:19:02,175 S for a set of vertices is a little bit more complicated. 343 00:19:02,175 --> 00:19:08,668 Okay, so is the set of edges which says at least 1 of their end points inside 344 00:19:08,668 --> 00:19:12,980 which has exactly 1 of their end points inside S okay. 345 00:19:12,980 --> 00:19:15,830 So essentially they are adjacent to the set S. 346 00:19:15,830 --> 00:19:20,190 You see a set S of vertices and these are edges which are which have an edge 347 00:19:20,190 --> 00:19:24,180 between an element, a vertex of S and an element which is not in S. 348 00:19:24,180 --> 00:19:26,300 Okay. So that's delta X. 349 00:19:26,300 --> 00:19:32,810 So delta S, Delta V the set of edges adjacent to V delta S the edge adjacent 350 00:19:32,810 --> 00:19:36,700 to you know a set of vertices which meets at least one of them okay. 351 00:19:36,700 --> 00:19:40,400 And then we going to give F gamma S, which is essentially. 352 00:19:40,400 --> 00:19:44,620 Oh the set of edges whose both endpoints are inside s, okay? 353 00:19:44,620 --> 00:19:48,510 So this is like, you look at those sort of vertices, and you look at the edges in 354 00:19:48,510 --> 00:19:51,470 between them. You don't go outside, okay? 355 00:19:51,470 --> 00:19:54,380 So, so these are, own, the only notation that we going to use. 356 00:19:54,380 --> 00:19:59,700 Then we have another, you, we going to say x, and then a set of, of, of edges 357 00:19:59,700 --> 00:20:05,150 to, to denote the sum of the variables associated with every one of these edges, 358 00:20:05,150 --> 00:20:08,700 okay. So, when I say x of e1, e2, e3 and so on, 359 00:20:08,700 --> 00:20:14,120 that basically, the, the sum x for the fist edge, plus x for the second edge 360 00:20:14,120 --> 00:20:18,900 plus x for the last edges and so on. Okay, so once we have this notation this 361 00:20:18,900 --> 00:20:22,246 is how we can have a first mip model for the TSP. 362 00:20:22,246 --> 00:20:28,880 Okay, so what we do is we minimize the the length of the two. 363 00:20:28,880 --> 00:20:34,490 So we take the cost of every edges and multiply by the binary variable telling 364 00:20:34,490 --> 00:20:38,230 you if you take the edges or not. Okay, so that's minimizing the cost. 365 00:20:38,230 --> 00:20:41,460 What you see over there basically the flow conservation or the degree 366 00:20:41,460 --> 00:20:45,160 constraints which are basically telling you that you every time you go to a 367 00:20:45,160 --> 00:20:46,960 vertex you have to get out. Okay. 368 00:20:46,960 --> 00:20:50,660 So and this is basically telling you that if you take the set of variable x. 369 00:20:50,660 --> 00:20:54,680 Okay. Okay and, and the set of adjacent vertex, 370 00:20:54,680 --> 00:20:57,980 the, the set of adjacent edge to the vertex v. 371 00:20:57,980 --> 00:21:00,990 Okay. The sum of these variables is, will be 372 00:21:00,990 --> 00:21:01,940 equal to 2. Okay. 373 00:21:01,940 --> 00:21:05,100 Take the adjacent edge. Took the sum of the brilliant fiber 374 00:21:05,100 --> 00:21:08,015 associated with these edges okay. It has to be equal to two. 375 00:21:08,015 --> 00:21:14,810 And then obviously you know the edges have to equal to one okay so you take a 376 00:21:14,810 --> 00:21:19,000 traveling salesman problem use that midformal solution and this is one of the 377 00:21:19,000 --> 00:21:22,932 things that can happen to you. Okay you are going to get a solution on 378 00:21:22,932 --> 00:21:25,880 this. Okay, so this is not a, usually a tool, 379 00:21:25,880 --> 00:21:29,690 what you get is a bunch of sub tools, okay, tiny tools, okay. 380 00:21:29,690 --> 00:21:32,210 So you have this one, okay, so you have this one. 381 00:21:32,210 --> 00:21:35,120 You have this vertex going into that vertex going into that vertex and then 382 00:21:35,120 --> 00:21:38,075 going back there, okay. So instead of going back to something 383 00:21:38,075 --> 00:21:40,040 else, its basically going back to the first. 384 00:21:40,040 --> 00:21:42,534 You know, vertex of this subtour. And then you have another subtour, a 385 00:21:42,534 --> 00:21:45,380 third subtour, and so on. And obviously, you know, this is very 386 00:21:45,380 --> 00:21:47,890 clever, right? So because you don't have to travel these 387 00:21:47,890 --> 00:21:50,440 long distances between these things. Okay? 388 00:21:50,440 --> 00:21:54,096 So that's terrible. We won't though, and one down. 389 00:21:54,096 --> 00:21:55,394 So what we want to do is we want to look at a particular vertex like this, a 390 00:21:55,394 --> 00:21:56,846 particular subtour like this, and we want to say, ooh, can I remove the fact that 391 00:21:56,846 --> 00:22:02,849 this is a subtour? Okay? 392 00:22:02,849 --> 00:22:06,389 So if you look at that it's three vertices and you see that, that you know, 393 00:22:06,389 --> 00:22:10,106 you ask yourself the questions that how many edges can actually be selected 394 00:22:10,106 --> 00:22:14,832 between these vertices, okay? And adversely you can't have three 395 00:22:14,832 --> 00:22:18,324 otherwise you have a subtour, okay? So the maximum number of edges here for n 396 00:22:18,324 --> 00:22:22,160 vertices is going to be n minus 1, right? So in this particular case it's going to 397 00:22:22,160 --> 00:22:25,510 be two, okay? So, and these are called the subtour 398 00:22:25,510 --> 00:22:26,770 constraints. Okay? 399 00:22:26,770 --> 00:22:30,710 And so what I'm showing you here is a formulation and a better formulation, you 400 00:22:30,710 --> 00:22:33,630 know, for the TSP, where we put these sub two constraints. 401 00:22:33,630 --> 00:22:35,870 Okay? So what we are basically telling you here 402 00:22:35,870 --> 00:22:42,310 is that if you take x and you so, if you take a particular vertex, a particular 403 00:22:42,310 --> 00:22:44,020 set of vertex s. Okay? 404 00:22:44,020 --> 00:22:48,840 And then you take all the edges, you know, which are inside that set. 405 00:22:48,840 --> 00:22:52,730 Okay so that's gamma s. Remember gamma s are all the edges which 406 00:22:52,730 --> 00:22:57,640 are between a vertices of s. You know that the sum of these edges, the 407 00:22:57,640 --> 00:23:00,860 sum of the Boolean variable, are associated with these edges has to be you 408 00:23:00,860 --> 00:23:04,250 know smaller than the communality of s. You know the set of vertices minus one. 409 00:23:04,250 --> 00:23:06,814 Okay so you can't, you have to get out of there. 410 00:23:06,814 --> 00:23:08,490 Okay? So that's what is this basically saying. 411 00:23:08,490 --> 00:23:12,210 You can have, you know, S minus, canonality of S minus one edges, but you 412 00:23:12,210 --> 00:23:14,300 have to be able to exit. Okay? 413 00:23:14,300 --> 00:23:16,050 So that's what you have there. Okay? 414 00:23:16,050 --> 00:23:18,570 So these are called the sub two constraints, okay? 415 00:23:18,570 --> 00:23:22,320 So, you look at every subset and you place these particular constraints. 416 00:23:22,320 --> 00:23:24,840 Okay. But what is the issue with these sub two 417 00:23:24,840 --> 00:23:27,370 constraints? Well, once again there are exponentially 418 00:23:27,370 --> 00:23:29,540 many of them. So, you don't want to write them all 419 00:23:29,540 --> 00:23:31,480 down, right? Because now it's going to be kind of 420 00:23:31,480 --> 00:23:34,380 long, okay. So what you want to do is exactly what we 421 00:23:34,380 --> 00:23:37,540 did with the cover cuts, you want to generate them on demand. 422 00:23:37,540 --> 00:23:39,680 Many of them you will never generate. Why? 423 00:23:39,680 --> 00:23:43,460 Because you know, you take something, you know if you do a tour of the US You never 424 00:23:43,460 --> 00:23:45,760 do caller connect Orlando and Seattle, right? 425 00:23:45,760 --> 00:23:49,430 And then San Francisco. So, you know, generating a sub tool for 426 00:23:49,430 --> 00:23:52,710 this thing is completely useless, it's use, the, the, the relaxation is never 427 00:23:52,710 --> 00:23:54,050 going to do that. Okay? 428 00:23:54,050 --> 00:23:58,050 So what you want to do is look at these sub tool constraints and see which one 429 00:23:58,050 --> 00:24:01,680 are violated by the linear relaxation, okay? 430 00:24:01,680 --> 00:24:05,130 So, you want to generate them on demand. Okay, and to do that you need a 431 00:24:05,130 --> 00:24:08,230 separation problem. Okay, so how do you do the separation 432 00:24:08,230 --> 00:24:09,630 problems. I'm going to give you an intuition, I 433 00:24:09,630 --> 00:24:12,010 won't go into the detail, but it is beautiful, okay. 434 00:24:12,010 --> 00:24:15,640 So what we, we can re-express the constraint by saying that, you know, the 435 00:24:15,640 --> 00:24:22,005 set of the edges The set of the adjacent to us between a set of law to adhere 436 00:24:22,005 --> 00:24:25,470 one.The cutting is to be set at minus one we sit on. 437 00:24:25,470 --> 00:24:31,210 And this is what you see. I took a set yes and then I set a s which 438 00:24:31,210 --> 00:24:38,156 is And, and exactly one of the endpoints is inside s, and so what I'm basically 439 00:24:38,156 --> 00:24:45,514 saying here is that the sum of edges when one of the endpoint is in s, the other 440 00:24:45,514 --> 00:24:51,350 one is outside, is s to be greater or equal to 2. 441 00:24:51,350 --> 00:24:53,120 Okay? Which means, oh, I have to get in and 442 00:24:53,120 --> 00:24:54,770 then I have to get out. Okay? 443 00:24:54,770 --> 00:24:59,120 So that's what you, you can re-express it that way and once you re-express it that 444 00:24:59,120 --> 00:25:04,570 way, the separation problems become a really nice combinatorial problems that 445 00:25:04,570 --> 00:25:07,550 can be solved in polynomial time. The key idea here is that you will build 446 00:25:07,550 --> 00:25:08,740 a graph. Okay. 447 00:25:08,740 --> 00:25:11,440 With the same set of vertices, the same set of edges. 448 00:25:11,440 --> 00:25:13,860 Okay. And the weight of the, and so for every 449 00:25:13,860 --> 00:25:18,630 one of these edges, you are going to assign the weight of the, the weight of 450 00:25:18,630 --> 00:25:21,440 the edges is going to be the value in the linear relaxation. 451 00:25:21,440 --> 00:25:24,040 Okay. So, so, basically build, you know, you 452 00:25:24,040 --> 00:25:27,440 have the same graph but now the edges get a width which is the, which is 453 00:25:27,440 --> 00:25:31,020 essentially the value of the decision variables of that edge inside the linear 454 00:25:31,020 --> 00:25:34,330 relaxation. And now if you, to separate, to find the 455 00:25:34,330 --> 00:25:38,350 sub two constraints, ok? That is violated, what you're going to do 456 00:25:38,350 --> 00:25:42,830 is try to find a min cut in that graph. So that means cutting the graph into two 457 00:25:42,830 --> 00:25:46,200 parts, okay? Such, and, and, such that, you know, you 458 00:25:46,200 --> 00:25:49,820 know, that, of minimal size, okay? To minimize the number. 459 00:25:49,820 --> 00:25:53,490 Of edges between these two different subsets, okay? 460 00:25:53,490 --> 00:25:55,870 And if then the weight of the cut is smaller or equal to two you have a 461 00:25:55,870 --> 00:25:58,085 problem, right? So you are basically violated in the 462 00:25:58,085 --> 00:26:00,960 subtour constraint, okay. So you have isolated the subtour 463 00:26:00,960 --> 00:26:04,230 constraints between some of these vertices and you can, you, you can find 464 00:26:04,230 --> 00:26:06,754 the subtour constraint and stand it inside the linear relaxation. 465 00:26:06,754 --> 00:26:11,880 Okay and finding some of these cuts okay. So finding these cuts is polynomial time. 466 00:26:11,880 --> 00:26:15,520 You know the simpliest algorithms which solves a bunch of max flow min cut 467 00:26:15,520 --> 00:26:19,935 problems and generate the cut by them. But there are better algorithm to do that 468 00:26:19,935 --> 00:26:24,455 acutally in practice. Okay so now you know to separate these 469 00:26:24,455 --> 00:26:28,210 subtour constraints so can do this branching you. 470 00:26:28,210 --> 00:26:32,705 Add them until you can't actually find any subtour constraint which is violated. 471 00:26:32,705 --> 00:26:35,650 Okay. Does that mean that at that point you 472 00:26:35,650 --> 00:26:37,710 have a solution to the TSP? No. 473 00:26:37,710 --> 00:26:40,320 Okay. So why this is a solution. 474 00:26:40,320 --> 00:26:41,960 Okay. Which satisfies all the subtour 475 00:26:41,960 --> 00:26:44,160 constraints. All the degree constraints. 476 00:26:44,160 --> 00:26:46,210 Okay. So you can't imagine how long I took to 477 00:26:46,210 --> 00:26:47,690 generate this. Okay. 478 00:26:47,690 --> 00:26:50,510 And, but it violates some of the subtour constraints. 479 00:26:50,510 --> 00:26:51,980 Okay? It vi, well, it, it, no. 480 00:26:51,980 --> 00:26:54,390 It doesn't violate the subtour constraint, but it says a fraction of 481 00:26:54,390 --> 00:26:55,200 solution. Okay? 482 00:26:55,200 --> 00:26:57,050 And they're actually cycles. Okay? 483 00:26:57,050 --> 00:26:59,980 So what you see here, look at this part. You get a cycle here. 484 00:26:59,980 --> 00:27:02,070 Okay? So all the values are one half. 485 00:27:02,070 --> 00:27:05,166 When you sum, okay The sum is smaller or equal to 2. 486 00:27:05,166 --> 00:27:07,180 Okay. It's 1.5, so it's smaller or equal to 2. 487 00:27:07,180 --> 00:27:10,970 Which is fine, fine, you're not violating any of the sub 2 constraints but still 488 00:27:10,970 --> 00:27:13,670 you have a cycle and you have fractional values there. 489 00:27:13,670 --> 00:27:16,530 So, what does that mean? That means that, you know, the convex 490 00:27:16,530 --> 00:27:20,820 side of the TSB is not characterized by the sub 2 formulation that I've shown 491 00:27:20,820 --> 00:27:22,844 you. We need more of these cuts. 492 00:27:22,844 --> 00:27:27,240 Okay and so, you know, in, it's the whole industry to actually generate very good 493 00:27:27,240 --> 00:27:30,460 cuts for the TSV okay. And there are some beautiful results in 494 00:27:30,460 --> 00:27:33,030 that space. And so I'm going to, I'm going to, I'm 495 00:27:33,030 --> 00:27:36,120 going to give you one class, okay, which is very useful in practice which I'll 496 00:27:36,120 --> 00:27:38,440 call the comb cut, comb, you know like combing. 497 00:27:38,440 --> 00:27:42,350 Okay, and so the basic intuition here is that if you look at the two and take a, 498 00:27:42,350 --> 00:27:44,570 you know, kind of an of a line. Okay. 499 00:27:44,570 --> 00:27:47,630 And wonder how many of these edges are intersecting. 500 00:27:47,630 --> 00:27:50,850 You know, you are going to intersect an even number of that, okay? 501 00:27:50,850 --> 00:27:53,370 Whatever you do is always going to be an even number, okay? 502 00:27:53,370 --> 00:27:57,670 So, now you can start reasoning about these crossings and that's what comb cats 503 00:27:57,670 --> 00:27:59,980 are doing. You know, if people in optimization are 504 00:27:59,980 --> 00:28:03,560 really created in finding good Okay, so what is a comb cat. 505 00:28:03,560 --> 00:28:08,020 Okay, so this is something that is a handle and a bunch of teeth, okay. 506 00:28:08,020 --> 00:28:11,730 And then you have nodes, where you have edges, which are purely between elements 507 00:28:11,730 --> 00:28:16,440 of the handles, and then edges which are purely inside the teeth. 508 00:28:16,440 --> 00:28:18,710 and then you have edges between the handle and the teeth. 509 00:28:18,710 --> 00:28:23,150 And the key idea is that what you want is what the comb is going to do is bond the 510 00:28:23,150 --> 00:28:27,660 number of edges that you can have inside the, purely inside the lid because that 511 00:28:29,710 --> 00:28:33,600 tells you that you need a certain number of these things that are connecting the 512 00:28:33,600 --> 00:28:37,070 handle and the teeth. Okay, and so this is an example of, this 513 00:28:37,070 --> 00:28:40,260 is a cut, okay, there are many examples of these comb cuts, but this is, this is 514 00:28:40,260 --> 00:28:43,880 a general comb cut. Okay, it's basically, you know, looking 515 00:28:43,880 --> 00:28:48,320 at. limiting the, the variables, the 516 00:28:48,320 --> 00:28:52,610 variables which are basically the edges inside the angle and inside the teeth, 517 00:28:52,610 --> 00:28:56,860 that's what you see here on the On the right hand side, so this is the number of 518 00:28:56,860 --> 00:29:00,400 edges inside the angle, the number of edges inside the T's, and that's 519 00:29:00,400 --> 00:29:04,830 basically bonded by the size of the angle, the size of the T, and the T's 520 00:29:04,830 --> 00:29:07,310 minus these things. Which are basically, you know, expressing 521 00:29:07,310 --> 00:29:10,040 the fact that you have to connect the handle and the T's, okay. 522 00:29:10,040 --> 00:29:13,180 So in this particular case, if you compute this expression on this example, 523 00:29:13,180 --> 00:29:15,880 this is going to give you the value 7. Just do it for yourself. 524 00:29:15,880 --> 00:29:19,370 It's very interesting, okay. And so 7 here is very interesting because 525 00:29:19,370 --> 00:29:21,210 why? When you look at the edges inside the 526 00:29:21,210 --> 00:29:25,270 handle, there are 6 of them. There are also an edge inside that T, 527 00:29:25,270 --> 00:29:28,080 that's also 7, so this constraint is actually tight, okay. 528 00:29:28,080 --> 00:29:30,530 So that means that you can't select more edges. 529 00:29:30,530 --> 00:29:34,050 If you select these edges, you can't select more edges inside the handle. 530 00:29:34,050 --> 00:29:36,680 So for instance, you could not select an edge going from here to there. 531 00:29:36,680 --> 00:29:38,950 Okay. So that, that would not be good. 532 00:29:38,950 --> 00:29:41,470 Okay. So essentially these comcast are 533 00:29:41,470 --> 00:29:47,180 basically, you know, more interesting, you know, facets of the polyhedral casts 534 00:29:47,180 --> 00:29:51,250 of, of the traveling salesman problem. Now I want to, a little bit, give you a 535 00:29:51,250 --> 00:29:55,230 perspective on how strong the relaxation becomes when you put these things. 536 00:29:55,230 --> 00:29:59,210 When you put the subtour elimination on the set of benchmark of the TSP, which 537 00:29:59,210 --> 00:30:02,960 has some really nice problems, which are not that easy, but the, some of them are 538 00:30:02,960 --> 00:30:07,100 really large, OK? So you come within 2% of the optimality 539 00:30:07,100 --> 00:30:09,060 gap. So the distance between the optimal 540 00:30:09,060 --> 00:30:12,780 solution And, and the linear relaxation is 2%. 541 00:30:12,780 --> 00:30:18,360 So if you, if you, if you do the subtour and the comps, okay, so you get to 0.5% 542 00:30:18,360 --> 00:30:22,560 of optimality which is really, really good, okay? 543 00:30:22,560 --> 00:30:25,860 For, for, you know largest, larger instances, you will need more cuts, there 544 00:30:25,860 --> 00:30:28,060 are things like local cuts, things like this. 545 00:30:28,060 --> 00:30:32,860 That will be needed to actually prove optimality or really really large TSP. 546 00:30:32,860 --> 00:30:36,910 So if you want to know more about this there is a beautiful book by Bill Cook 547 00:30:36,910 --> 00:30:41,290 just on the traveling salesman problem. And it's a fantastic book because it 548 00:30:41,290 --> 00:30:46,720 gives you history and all kind of things. It's like addressing, you know. 549 00:30:46,720 --> 00:30:50,220 People who don't necessarily have a background in optimization, but also 550 00:30:50,220 --> 00:30:53,340 giving you some of the technical of detail, so it's really a nice balance. 551 00:30:53,340 --> 00:30:55,140 So, if you want to know more read that book, okay? 552 00:30:55,140 --> 00:30:57,580 So, this is basically covering branch and cut, okay? 553 00:30:57,580 --> 00:31:00,290 So what we saw, branch and cut in summary, okay? 554 00:31:00,290 --> 00:31:03,450 So what you do is the solve the linear reaction based on the myth, and then you 555 00:31:03,450 --> 00:31:07,850 generate on demand. Okay all this constraints to keep the 556 00:31:07,850 --> 00:31:10,500 optimal solution to the linear relaxation. 557 00:31:10,500 --> 00:31:13,920 And then strengthen the relaxation. When you stack you going to branch and 558 00:31:13,920 --> 00:31:21,150 you can repeat the process. Thank you.