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.