Okay, discrete optimization, mixed integer programming, branch and cut, second lecture. Okay? So, this is the real stuff now. Okay? So one of the things that we saw in the last lecture is that we can generate these polyhedron cuts. Okay? But one other thing that we did was basically adding them all inside Inside the, you know, formulation, the beginning. That's not exactly how branch and cut works, so what I want to go and, what I want to do now, is take this concept and then tell you really what a branch and cut algorithm is doing. Okay? So we're going to see two things, cover cuts, okay, and you'll see why, you know, we, we, we'll talk about them, they're very, you know, very frequent in in mixed integer programs, and then we move to the TSP, which is probably the biggest success stories of optimization. We can solve really really large TSP optimally at this point. Okay, so cover caps first. Cover caps we are looking at constraint which are inequalities. Okay, linear inequalities, a sum of coefficients and variables which are smaller than b The simplest kind of stuff that you find all the time inside your math. Okay? So sum, you know, coefficient, ai, aj, you know, multiplied by a, a binary variable, xj 01, is to be smaller than b, okay? So, so you know can we find facets for these constraints okay. Can we find facet of the pole which have arrived from these constraints okay. And the key concept here you know the title is cover cut right is the concept of cover and essentially what you need to think about is a cover is going to be a set of variables if you set them all to 1 you're going to violate the constraints okay. It's basically telling you these variables not all of them can be 1. Okay? And so basically, you know, is what you do is you look at the subset of these variables. Okay? You look at the coefficients and if you sum all these coefficient, they are greater than b. And therefore, you know, you know that if you select all these variables, put them to 1, you going to violate the constraints. Okay? So, that's the concept of cover. Basically, these variable cannot all be selected at the same time. Okay? And so a cover is going to be maximal, minimal, okay so that's the opposite of maximal too, it's going to be minimal if you remove one of these variables, okay, it's not a cover anymore, okay? It's like the strongest possible cover, okay? So, so, so when you look at these covers now, so we have a particular constraints there, we take a cover, We, this, so I'm going to show you an inequality which is valid. Okay? And so what we do is basically that's what I told you before. Right? If we select all these variables at the same time. Right? We can evaluate the constraints. So the constraints is basically say, saying, at least one of them has to be zero, or the sum of all these guys ahs to be smaller than the size of this cover minus one. You can't select all the variables. This is what this is telling you. You can't select all the variables. So in a sense the sum of them is to be smaller than the size of the set minus one, or at least one of them has to be zero. We can think about it hopefully, and that's what we're going to do anyway. Okay? So these are the cover cuts, okay? So if you look at these constraints here, this is a big constraint, right? So, seven variables, with coefficient, you know, 11, 6, 6, 5, 5, 4, 1, OK? And that has to be smaller, the sum of these things have to be smaller, these variables. Have to be smaller than 19, okay? Can we find a cover cut, okay? So that's going to be easy, right? So we take in this particular case the coefficients by, you know, this is decreasing order. I made it easy for you, right? So this is 11, 6, 6. So that's already 23, right? So this is, this is greater than 19. So this is This is a cover, okay. And, but, because of that, you know that x1 plus x2 plus x3 has to be smaller or equal to 2. You can only select two of these variables, hence, you know, to have a feasible solution. Okay? Now let's look at x4, x5, x6, x3, x4, x5, and x6. Okay, if you sum all these things together Once again you get 20, this is greater than 19, so this is also a cover and this is the cover inequality that results from them, okay. The sum of these four variables has to be smaller or equal to 3, okay. So this is essential, so you, you start from inequality like this with, you know, big coefficient, and then you have a simple cover inequality there, which is limiting the set of the sum of, you know, a subset of the variables. Okay? These are cover cuts, okay? Now, you can extend, you can make them stronger, and the key idea is that if you ever cover cut, if you ever cover cut, you can extend it by taking other variables. Whose coefficients are greater than all the coefficients of the count. Okay? So this is what this formula is explaining. So know instead of leaving the sum all over the set, you have this extended set, okay? You know you extend the cut c, okay, and what you do is you take up usually c but also all the other you know variables whose coefficients is greater than all the coefficients of, of C. Okay so, you know, by definition that these variables okay so they will, they, they will essentially, they will, the cut will be, will be stronger. Let me show you an example, it is easier on the example. So you see essentially the, the cover cut that we have seen. We add the cut which is x4, you know, x3, x4, x5, and x6 has to be smaller or equal to 3. You know, you see that the coefficient of x1 and x2 are greater than all these coefficients, so you make the case stronger by adding x1 and x2 on this. If the coefficient would be weaker it would not be you know, as strong. But here the coefficients are always at least as strong as the coefficients of the other ones, okay? So, that's the stronger cover. Okay so this is the idea of branch and cut, okay? So the branch and cut, you know, consists of modeling first if the problem is okay. Now have a bit, okay. So you can use the linear relaxation if the linear relaxation is giving you an integral solution. Finish okay you have an optimal solution. Otherwise what you do is, you basically find the polyhedral cut, okay, which cuts the optimal solution to the linear relaxation. That's the key step, okay? And obviously you would like to have a facet if it's possible. And so if you find such a beautiful thing, right? So what you're going to do is, you go back to step 2, you solve the linear relaxation, it's stronger. Why is it stronger? Because you cut the linear, the optimal solution to the linear relaxation, and you iterate this stuff. Okay, and at some point you can't find any of these cuts anymore because you've found all of them or it's too tough to actually find them okay. And then what you do is branch and then you can repeat these steps, or you can at some point decide that's it's not even worth generating more cuts okay. But this is the basic framework for branch and cut okay. Now the key point here okay, is that we have to generate these polyhedral cut that are going to remove the value of the optimal solution. Okay, the linear relaxation, okay? So this is what we need to do, okay? So we are not going to do what I did in the previous lecture, which is just listing all the possible cuts we could find. Okay, what we want to do is, at some point, we look at this linear relaxation, and you say, wow, okay, so I want to cut it. Okay? So to give you an analogy, you know, you have to think about, you know, feeding babies, right? So so there are two types of parents, right? So when you have a night, you know, a new kid. So what you do, you have the parents that read the books and do everything by the rule. Okay. It's written in the book that this kid has to basically you know, be eating every three hours. So this poor kid is sleeping but you know, three hours has gone so they wake up this kid and feed the kid. Right. And so then try to put the kid to sleep and that never works of course. Okay. So these are, you know, these are you know, essentially generating all the cuts. Okay? and then they are the cruel parents, right? So I'm not saying this is better or worse, right. But the other parents are saying this kid is you know, sleeping, you know beautifully. I'm going to let this kid sleep and then when the kids you know, wake up. And yell you don't know why, but give basically feed that part. That's demand feeding. That's what we are doing. We generate these cuts by demands. Okay. So this is what we going to do and that's called a seperation problem okay. So what you know is that you have this optimal solution, okay, to the linearly relaxation and what you want to do is you want to look. A particular cut, a particular class of cut that's going to remove the ultimate solution to this linear relaxation, okay, so this is what we do for cover cut, okay. So, we've this optimal solution to the linear relaxation and we are wondering, can I find cover cut that's going to remove this optimal solution of the linear relaxation, okay. So we know that the cover ca-, the cover inequality, okay? So this is this b's, re-, re-, vir, saying that the se-, this subset of variables, if I sum them to one, okay, is, thas, if I sum them, you know, they, they can't all be one, so they have to sum, and, you know The sum, their sum should be smaller or equal to the cardinality of the cover minus 1. So that can be rewritten oh at least one of them maybe 0 so you do minus the variable okay. So that's going to be 1 if the variable is 0 or 0 if the variable is 0 okay. And so you're basically saying here is that the number of variables which is 0 is to be greater than 1 okay. And so essentially finding a cover cut, okay, will require two condition. Okay? So, we one of you see to find a cover, that's the second conditions that you have. Okay? So when you take the sum of this, when you take, when you take the sum of the elements in C, okay, the elements in the cover. That is to be greater than, you know, the sum of the coefficient is to be greater than the right hand side of the constraint. Okay? And then we want to be sure. We want to, we want to have the property that in the linear relaxation these guys are smaller or equal to one, so they are basically violating the cover cut, okay? So essentially what we want to find is the cover cut that vi, that is violated by the linear relaxation, okay, and is a cut, okay, is a cover cut, okay? So we want these two properties. If you find that essentially what we're doing is generating these cuts on demand. Okay? So you say ooh, I have this linear relaxation. Okay? I want to find a cover cut, and that cover cut has to violate this, has to be violated. That's what you are trying to do. Okay? So, essentially, this is you know, we have two constraints here, okay, so we could view that as a feasibility problem But we can also view that as an optimization problem because that's what linear programming does. Right so or you mixed integer programing does. So what we do here is minimize this expression. Okay, that's the expression that we want to be smaller or equal to one. Smaller than one and then we have a definition of a cover cutter so essentially what you do is you look for these variables that I okay that J in this particular case okay. So you look at all of them these are essentially the you know all the variables that indices of the variables inside the inside the constraints you want to select a subset of them which violate the cut and minimize this function okay. And so now if the value of this function is smaller or equal to 1 you have a cover cut. Okay and all the elements which are equal to 1 are the cover. So essentially if you solve this linear program, okay? This this mix integer problem okay. So you have a cover cap, you find a cover cap. Now you tell me wow wow wow you guys are trying to solve mix integer program and you want to solve another mix integer program to solve that integer program and you want to do that repeatedly you know what are you doing? Okay, and so let me address that question in a moment. Okay, so but first let me give you an example okay. So, so, what you see here is the, is a big constraint I say bigger than the other time, you know, the other one that I've showed you before, the right hand sided 178, and you see coefficients go, you know, ranging from 45 to, you know, 125. Okay. Now, the linear. Assume that the linear relaxation is giving you this optimal solution, okay. So, you see that the 1st one is 0, the 2nd one is 0, the 3rd one is 3 quarter, the 4th one is 1, 1/2, and the next one is 0, okay? So, how do you generate. Okay, so what is the, what is the big, big program we have to solve to find the cover cut? So this is the, this is the mid program actually doing, solving the separation problem, okay? You minimize that one, why is that 1? Because essentially you take 1 minus the value in the linear relaxation, which is 0, okay? So that's why you have that 1, then you have that 2 for the same reason. Then you have 1 fourth of that tree. Why? Because you see essentially 3/4 a year so 1 minus 3/4 is 1/4 and that's how you get this objective function. That's essentially what we saw in the previous slide. And then, of course, you have to have a cover cut. Okay. And so you want, basically, that the choice of the value, the 0 1 values for disease is going to basically be greater than 178 when multiplied by the coefficient. Okay? So essentially this is, this is the mid program that we have to solve for finding this, for finding this cut. So this is the separation problem. Okay, if we find the solution to this, we will separating, you know, the, we left final cut, which essentially separate. The, the solution to the linear relaxation and the convex cell. Okay? So this is, you know, I told you this is this beautiful mixed integer program, and so the question that I'm asking you is, you know, does it remind you of something? Okay? So it's minimizing your linear sum of 0, 1 variables subject to sum, you know, the sum of these variables is to be greater than something. Okay. Well, look, if I do a variable transformation. Okay, if we write the jen G into one minus Y G. Okay, what do I get? Well, this minimum is going to be a maximum. Okay. So we're going to maximize some of the variables. And this inequality here, you know, which is greater than, is going to turn into an inequality which is smaller than, is going to be a sum of variables with coefficient. Smaller than something, so what we have there is a knapsack problem. Okay? So it's like, you know, we have closed the loop, in a sense. We started with the knapsack and now we are generating these branch and cut using a knapsack algorithm here. Okay? So, this essentially the way you can do branch and cut, okay. So you basically, you basically solve the linear relaxation, and then you have various class of cuts, and then you say, ooh, can I generate a cut That's going to separate, separate, the optimal solution to the lineal relaxation. And you saw this separation problem and find this guess on demand. So, before we move to the TSP which is going to be kind of You know, big notation. So, I want to go into a little bit of history here. Okay. And we're going to talk about the, the Seven Bridges of Konigsberg. Okay. And so is the city where Euler, the beauty, you know, the great mathematician Euler was living. And this is a very interesting city, because it is going to have, as the title indicates, seven bridges. Right, so let's zoom. You see the river, you know, in blue, okay. And you see all these bridges in red, I assume. Okay? And so what Euler asked, you know, I think this is what he was spending his free time doing. He said, can I find a tour which would go, you know, which would walk over every one of these seven bridges exactly once? Okay? So this is, for instance, the tour that you see here, okay, which is basicaly going over five of the bridges. Okay, we can go to five of them exactly one, can we go to seven exactly once. Okay? And so what Euler did is one of the founder of use in graph theory, is basically represent that is beautiful pictures. Okay, right? And then you looked at that picture and said this is really a graph. Okay. So, I can associate a note with every one of these land masses. Okay? And know the edges between these vertices are going to be the bridges, okay? So, you see that here, you know, I have 2 bridges between these 2 you know landmass. Okay and so the question was can I have 2 can I have 2 that visit every one of the edges exactly once okay. So an earlier look at this problem and say no, I can prove that this is impossible you don't have to try working this thing forever. Okay, and one of the ways, the way you actually prove that is by looking at every one of these vertices. Okay, and of, usually when you walk from one vertex to another, you go to another popular point and then you go to another one. So, as soon as you enter a vertex, you have to leave it, right? So, that basically means that if you go over all the bridges, okay, you have to make sure that the degree of every one has to be even. Otherwise you will come and there will be no bridge to, get out of it. Right? And so he could prove that in this particular case you could never, never walk exactly once on these seven bridges. Because, you know, these, all these vertices here at, you know, an, an odd degree. Okay? So in a sense he invented kind of these degree constraints. And they are going to be very useful for our next topic. Which is the traveling salesman problem. Now, the traveling salesman problem can be seen as the, you know, the dual kind of, well, it's not really dual from a mathematical sense, but it's basically the opposite of the, of the, of the earlier two problems. What we want to do here is to visit exactly, you know, all of the vertices exactly once, not the edges. Okay? And there is a big difference between the yellow tour and this, the Traveling Salesman Problem. One is easy to solve, the other one is very complicated to solve. Okay? So, so what we do in the TSP is we want to find the two which is visiting every one of these vertices exactly once. Okay? And so the first thing that we have to do now is to try to model this as a MIP. Right? So when we do one to do branch and cat, what you do is you model this thing as a, as a MIP. Okay? So you have to choose a decision variable, the constraints, the objective function. Okay? Now there are many models to do that, right? So, and we're going to use one which is very, very good from a computational standpoint. But you see we've got to build it step by step. Okay? It's going to be kind of nice. So, the decision variable here, I'm going to be deciding whether an edge is part of the tour or not. So, we're going look at every edges. Okay? And we, we'll associated decision variable, a binary decision variable, depending is whether that particular edge is part of an optimal tour or not. Okay. And so the constraints are going to be this degree constraints. We know that if we go to a vertex, we have to get out of the vertex, okay. So, and since we can visit the vertex exactly once, okay. So, it's not like it has to be even, it has to be exactly two, you want to go the vertex and you want to get out. Okay. So essentially if you look at the vertex Two of its adjacent edges, okay, exactly two of these adjacent edges have to be one. Okay? So this is the first, so I'm going to kill you with notation now, but this is essentially the basic of the, of, of the model, of the first, you know, MIP model. Okay? So I told you I'm going to kill you with these notations. So I'm going to try to go slowly, so that you can. Memorize everything, okay? But essentially the decision variables are going to be very easy. You know, for every edge e, you have Xe, which is a decision variable, which is zero if you don't get the edges in an optimal solution in one if you take it. Okay? No V is always going to be the set of vertices, E is always going to be the set of edges. Okay? And then the three notation are important. Okay, so the three, the next three notation are important. So, I'm going to use delta V. Okay. As the set of edges which are adjacent to vertex V. So, I'll look at the vertex and then I'll look at all the edges which has V as one of their end points and thus delta V. Okay. So, when you see delta V, it's the edges associated with V. Okay. So far so good? Okay. Delta V the edges adjacent to V Now delta S for a set of vertices is a little bit more complicated. Okay, so is the set of edges which says at least 1 of their end points inside which has exactly 1 of their end points inside S okay. So essentially they are adjacent to the set S. You see a set S of vertices and these are edges which are which have an edge between an element, a vertex of S and an element which is not in S. Okay. So that's delta X. So delta S, Delta V the set of edges adjacent to V delta S the edge adjacent to you know a set of vertices which meets at least one of them okay. And then we going to give F gamma S, which is essentially. Oh the set of edges whose both endpoints are inside s, okay? So this is like, you look at those sort of vertices, and you look at the edges in between them. You don't go outside, okay? So, so these are, own, the only notation that we going to use. Then we have another, you, we going to say x, and then a set of, of, of edges to, to denote the sum of the variables associated with every one of these edges, okay. So, when I say x of e1, e2, e3 and so on, that basically, the, the sum x for the fist edge, plus x for the second edge plus x for the last edges and so on. Okay, so once we have this notation this is how we can have a first mip model for the TSP. Okay, so what we do is we minimize the the length of the two. So we take the cost of every edges and multiply by the binary variable telling you if you take the edges or not. Okay, so that's minimizing the cost. What you see over there basically the flow conservation or the degree constraints which are basically telling you that you every time you go to a vertex you have to get out. Okay. So and this is basically telling you that if you take the set of variable x. Okay. Okay and, and the set of adjacent vertex, the, the set of adjacent edge to the vertex v. Okay. The sum of these variables is, will be equal to 2. Okay. Take the adjacent edge. Took the sum of the brilliant fiber associated with these edges okay. It has to be equal to two. And then obviously you know the edges have to equal to one okay so you take a traveling salesman problem use that midformal solution and this is one of the things that can happen to you. Okay you are going to get a solution on this. Okay, so this is not a, usually a tool, what you get is a bunch of sub tools, okay, tiny tools, okay. So you have this one, okay, so you have this one. You have this vertex going into that vertex going into that vertex and then going back there, okay. So instead of going back to something else, its basically going back to the first. You know, vertex of this subtour. And then you have another subtour, a third subtour, and so on. And obviously, you know, this is very clever, right? So because you don't have to travel these long distances between these things. Okay? So that's terrible. We won't though, and one down. So what we want to do is we want to look at a particular vertex like this, a particular subtour like this, and we want to say, ooh, can I remove the fact that this is a subtour? Okay? So if you look at that it's three vertices and you see that, that you know, you ask yourself the questions that how many edges can actually be selected between these vertices, okay? And adversely you can't have three otherwise you have a subtour, okay? So the maximum number of edges here for n vertices is going to be n minus 1, right? So in this particular case it's going to be two, okay? So, and these are called the subtour constraints. Okay? And so what I'm showing you here is a formulation and a better formulation, you know, for the TSP, where we put these sub two constraints. Okay? So what we are basically telling you here is that if you take x and you so, if you take a particular vertex, a particular set of vertex s. Okay? And then you take all the edges, you know, which are inside that set. Okay so that's gamma s. Remember gamma s are all the edges which are between a vertices of s. You know that the sum of these edges, the sum of the Boolean variable, are associated with these edges has to be you know smaller than the communality of s. You know the set of vertices minus one. Okay so you can't, you have to get out of there. Okay? So that's what is this basically saying. You can have, you know, S minus, canonality of S minus one edges, but you have to be able to exit. Okay? So that's what you have there. Okay? So these are called the sub two constraints, okay? So, you look at every subset and you place these particular constraints. Okay. But what is the issue with these sub two constraints? Well, once again there are exponentially many of them. So, you don't want to write them all down, right? Because now it's going to be kind of long, okay. So what you want to do is exactly what we did with the cover cuts, you want to generate them on demand. Many of them you will never generate. Why? Because you know, you take something, you know if you do a tour of the US You never do caller connect Orlando and Seattle, right? And then San Francisco. So, you know, generating a sub tool for this thing is completely useless, it's use, the, the, the relaxation is never going to do that. Okay? So what you want to do is look at these sub tool constraints and see which one are violated by the linear relaxation, okay? So, you want to generate them on demand. Okay, and to do that you need a separation problem. Okay, so how do you do the separation problems. I'm going to give you an intuition, I won't go into the detail, but it is beautiful, okay. So what we, we can re-express the constraint by saying that, you know, the set of the edges The set of the adjacent to us between a set of law to adhere one.The cutting is to be set at minus one we sit on. And this is what you see. I took a set yes and then I set a s which is And, and exactly one of the endpoints is inside s, and so what I'm basically saying here is that the sum of edges when one of the endpoint is in s, the other one is outside, is s to be greater or equal to 2. Okay? Which means, oh, I have to get in and then I have to get out. Okay? So that's what you, you can re-express it that way and once you re-express it that way, the separation problems become a really nice combinatorial problems that can be solved in polynomial time. The key idea here is that you will build a graph. Okay. With the same set of vertices, the same set of edges. Okay. And the weight of the, and so for every one of these edges, you are going to assign the weight of the, the weight of the edges is going to be the value in the linear relaxation. Okay. So, so, basically build, you know, you have the same graph but now the edges get a width which is the, which is essentially the value of the decision variables of that edge inside the linear relaxation. And now if you, to separate, to find the sub two constraints, ok? That is violated, what you're going to do is try to find a min cut in that graph. So that means cutting the graph into two parts, okay? Such, and, and, such that, you know, you know, that, of minimal size, okay? To minimize the number. Of edges between these two different subsets, okay? And if then the weight of the cut is smaller or equal to two you have a problem, right? So you are basically violated in the subtour constraint, okay. So you have isolated the subtour constraints between some of these vertices and you can, you, you can find the subtour constraint and stand it inside the linear relaxation. Okay and finding some of these cuts okay. So finding these cuts is polynomial time. You know the simpliest algorithms which solves a bunch of max flow min cut problems and generate the cut by them. But there are better algorithm to do that acutally in practice. Okay so now you know to separate these subtour constraints so can do this branching you. Add them until you can't actually find any subtour constraint which is violated. Okay. Does that mean that at that point you have a solution to the TSP? No. Okay. So why this is a solution. Okay. Which satisfies all the subtour constraints. All the degree constraints. Okay. So you can't imagine how long I took to generate this. Okay. And, but it violates some of the subtour constraints. Okay? It vi, well, it, it, no. It doesn't violate the subtour constraint, but it says a fraction of solution. Okay? And they're actually cycles. Okay? So what you see here, look at this part. You get a cycle here. Okay? So all the values are one half. When you sum, okay The sum is smaller or equal to 2. Okay. It's 1.5, so it's smaller or equal to 2. Which is fine, fine, you're not violating any of the sub 2 constraints but still you have a cycle and you have fractional values there. So, what does that mean? That means that, you know, the convex side of the TSB is not characterized by the sub 2 formulation that I've shown you. We need more of these cuts. Okay and so, you know, in, it's the whole industry to actually generate very good cuts for the TSV okay. And there are some beautiful results in that space. And so I'm going to, I'm going to, I'm going to give you one class, okay, which is very useful in practice which I'll call the comb cut, comb, you know like combing. Okay, and so the basic intuition here is that if you look at the two and take a, you know, kind of an of a line. Okay. And wonder how many of these edges are intersecting. You know, you are going to intersect an even number of that, okay? Whatever you do is always going to be an even number, okay? So, now you can start reasoning about these crossings and that's what comb cats are doing. You know, if people in optimization are really created in finding good Okay, so what is a comb cat. Okay, so this is something that is a handle and a bunch of teeth, okay. And then you have nodes, where you have edges, which are purely between elements of the handles, and then edges which are purely inside the teeth. and then you have edges between the handle and the teeth. And the key idea is that what you want is what the comb is going to do is bond the number of edges that you can have inside the, purely inside the lid because that tells you that you need a certain number of these things that are connecting the handle and the teeth. Okay, and so this is an example of, this is a cut, okay, there are many examples of these comb cuts, but this is, this is a general comb cut. Okay, it's basically, you know, looking at. limiting the, the variables, the variables which are basically the edges inside the angle and inside the teeth, that's what you see here on the On the right hand side, so this is the number of edges inside the angle, the number of edges inside the T's, and that's basically bonded by the size of the angle, the size of the T, and the T's minus these things. Which are basically, you know, expressing the fact that you have to connect the handle and the T's, okay. So in this particular case, if you compute this expression on this example, this is going to give you the value 7. Just do it for yourself. It's very interesting, okay. And so 7 here is very interesting because why? When you look at the edges inside the handle, there are 6 of them. There are also an edge inside that T, that's also 7, so this constraint is actually tight, okay. So that means that you can't select more edges. If you select these edges, you can't select more edges inside the handle. So for instance, you could not select an edge going from here to there. Okay. So that, that would not be good. Okay. So essentially these comcast are basically, you know, more interesting, you know, facets of the polyhedral casts of, of the traveling salesman problem. Now I want to, a little bit, give you a perspective on how strong the relaxation becomes when you put these things. When you put the subtour elimination on the set of benchmark of the TSP, which has some really nice problems, which are not that easy, but the, some of them are really large, OK? So you come within 2% of the optimality gap. So the distance between the optimal solution And, and the linear relaxation is 2%. So if you, if you, if you do the subtour and the comps, okay, so you get to 0.5% of optimality which is really, really good, okay? For, for, you know largest, larger instances, you will need more cuts, there are things like local cuts, things like this. That will be needed to actually prove optimality or really really large TSP. So if you want to know more about this there is a beautiful book by Bill Cook just on the traveling salesman problem. And it's a fantastic book because it gives you history and all kind of things. It's like addressing, you know. People who don't necessarily have a background in optimization, but also giving you some of the technical of detail, so it's really a nice balance. So, if you want to know more read that book, okay? So, this is basically covering branch and cut, okay? So what we saw, branch and cut in summary, okay? So what you do is the solve the linear reaction based on the myth, and then you generate on demand. Okay all this constraints to keep the optimal solution to the linear relaxation. And then strengthen the relaxation. When you stack you going to branch and you can repeat the process. Thank you.