A bound that may be off by a third

A salesman must visit every city on a list once and return home, and wants the shortest route. For a handful of cities every route can be tried; for fifty the routes outnumber the atoms in the Earth, and no method is known that always finds the best one in time growing only polynomially with the number of cities. The problem is the standard example of a hard one.

What can be computed quickly is a lower bound. The lines the optimum lies under described the move: replace the whole-number decisions of a problem by fractional ones, solve the resulting linear programme — which is fast — and read its optimum as a bound the true answer cannot beat. It ended on the travelling salesman, where that bound is called the subtour relaxation, and on the question of how far below the shortest tour it can lie.

The answer is not known. The worst instances anyone has found fall short by a factor approaching $\tfrac{4}{3}$; the best proof says the factor never exceeds $\tfrac{3}{2}$; and the gap between those two numbers has stood since 1980. This essay builds the relaxation, solves it exactly on the instance that comes closest to $\tfrac43$, and measures how rarely typical instances come near.

Two triangles and three paths #

A tour uses each road it takes once, and every city is entered once and left once. Write a variable $x_e$ for each road $e$, equal to 1 if the tour uses it and 0 if not. Then the tour’s length is $\sum d_e x_e$, and a tour satisfies: every city has two roads at weight 1, and — the condition that stops the route breaking into separate loops — every division of the cities into two groups is crossed by at least two roads. Relax “0 or 1” to “anything between 0 and 1” and keep the rest. That is the subtour relaxation, introduced by George Dantzig, Ray Fulkerson and Selmer Johnson in 1954, when they used it to solve a tour through 49 American cities by hand.

The instance in the figure is built to defeat it. Two triangles are joined by three paths, each of $k$ edges — here $k = 3$, twelve cities in all — and the distance between two cities is the length of the shortest route between them along the drawn edges. The relaxation’s optimum puts weight 1 on every path edge and weight $\tfrac12$ on every triangle edge. Every city then has total weight 2 — a path city from its two path edges, a triangle corner from one path edge and two halves — and any division of the cities cuts either all three paths or a triangle, which carries weight at least 2. The cost is $3k$ for the paths plus $3$ for the halves: 12.

A tour cannot do anything so economical. It must visit every city on all three paths, and a tour that runs down the first path, back up the second and down the third finds itself at the far end, with a return trip of about $k$ still to pay. The exact shortest tour, found by trying every order with Michael Held and Richard Karp’s dynamic programme, costs 14 here, and $4k + 2$ in general. The relaxation pays for each path once; the tour must effectively pay for one of them twice.

Why the tour must pay for a path twice #

The reason the tour costs about $4k$ is a parity argument, and it is worth seeing because it is exactly what the relaxation cannot see. Call the two triangles the left end and the right end. A tour is a closed loop, so it crosses from the left end to the right end as often as it crosses back: an even number of times in all. The only cheap way across is along a path, and a tour that runs the full length of all three paths, entering each at one end and leaving at the other, crosses three times — an odd number. So at least one path is not run end to end.

A path that is not run end to end still has its $k - 1$ inner cities to visit, and every way of visiting them without running the path through costs about $k$ more: the tour must go in and come back out at the same end, or jump into the middle from somewhere far away. In the figure’s tour for $k = 3$ it is the jumps between the ends of different paths that pay the extra. Either way the tour costs about $3k$ for the three paths plus about $k$ for the parity, and the exact computation gives $4k + 2$.

The relaxation escapes the parity argument because a half-weight is not a crossing. The weights $\tfrac12$ on each triangle’s edges let the three paths each carry weight 1 end to end — three crossings — while the triangles absorb the imbalance by splitting their weight across all three corners. Every cut is still crossed at least twice, every city still has degree 2, and the odd count that dooms a tour is invisible to constraints that only ever ask whether something is at least 2. The gap is the price of a parity condition written as an inequality.

The cut that forbids two loops #

The cut conditions are what make the relaxation a bound worth having, and there are too many of them to write down: one for every way of splitting the cities into two groups, which is about $2^n$ conditions. They are added only when needed. Solve the programme with just the degree conditions and check the answer: if some division is crossed by less than 2, add that one condition and solve again.

Finding a violated condition is itself a classical problem. The weights on the roads are capacities, and a division crossed by weight less than 2 is a cut of capacity less than 2 — so the question is whether the network’s minimum cut is below 2, which the bottleneck is the whole story showed how to answer quickly through maximum flow. Mechthild Stoer and Frank Wagner’s algorithm of 1994 finds a minimum cut of the whole network directly, and it is what this computation uses.

A solver can go further than one cut at a time. Ralph Gomory and T. C. Hu showed in 1961 that all the minimum cuts separating every pair of cities in a network can be recorded in a single tree with one edge per city, one tree for every cut — so a single computation of $n - 1$ flows finds a violated condition separating every pair of cities that any violated condition separates, and large solvers add them in batches rather than one by one.

The figure shows the smallest case. With degree conditions alone, two clusters of four cities far apart are served by two separate quadrilaterals — each city with two roads, the total barely more than the clusters’ perimeters. The minimum cut is the division between the clusters, crossed by nothing. Adding the condition that it be crossed twice forces two long bridges, and with that one constraint the relaxation’s optimum becomes a genuine tour and the bound is exact. The linear programme’s dual attaches a price to that constraint, as what a constraint is worth described for any binding condition: it is the rate at which the bound would change if the cut had to be crossed a little more or a little less than twice, and it is large here precisely because crossing the gap is expensive.

Climbing towards a third #

For each $k$ from 1 to 5 both numbers were computed exactly — the relaxation by the simplex method with cuts added as found, the tour by Held and Karp’s method, which is exact but slow, and at 18 cities is near the limit of what it can do quickly. The ratios are $1$, $\tfrac{10}{9}$, $\tfrac{14}{12}$, $\tfrac{18}{15}$ and $\tfrac{22}{18}$: exactly $(4k+2)/(3k+3)$, which tends to $\tfrac43$ as the paths lengthen.

No instance is known on which the relaxation does worse. The conjecture that $\tfrac43$ is the worst possible gap for distances satisfying the triangle inequality is decades old, and it is supported by computation on small instances and by every family anyone has built. The upper bound is further away. Laurence Wolsey proved in 1980 that the gap never exceeds $\tfrac32$, by showing that a tour of length at most $\tfrac32$ times the relaxation’s optimum can always be constructed — the argument that tours within half again of the best takes apart.

In 2020 Anna Karlin, Nathan Klein and Shayan Oveis Gharan pushed the upper bound below $\tfrac32$ for the first time — by about $10^{-36}$. The size of that improvement is itself a measure of how hard the problem is: a new algorithm, combining a random spanning tree with the relaxation’s weights and an analysis of dozens of pages, moved a forty-year-old constant in its thirty-sixth decimal place.

On random cities the bound is exact #

The bad family is special, and ordinary instances look nothing like it. On forty sets of fifteen cities scattered at random in a square, the relaxation’s optimum is itself a tour in thirty-five, and the bound is exact. In the other five it falls short by at most half a per cent. For larger random instances, measurements by David Johnson and his colleagues in the 1990s found the bound typically within about one per cent of the shortest tour, and it is the reason tours through tens of thousands of cities can be proved optimal: a branch-and-bound search only has to close a gap of a per cent, not a third.

For random cities there is even a law. Jillian Beardwood, John Halton and John Hammersley proved in 1959 that the shortest tour through $n$ random points in a unit square has length about $\beta\sqrt n$ for a constant $\beta$ that no one has computed exactly; the best estimates put it near $0.7124$. The relaxation’s optimum grows the same way with its own constant, estimated near $0.7080$, so for large random instances the two differ by about six tenths of a per cent — a gap that neither shrinks nor grows as the instances get bigger.

The contrast is between the worst case and the typical case, and both matter. The typical case is why the relaxation is the working heart of every exact solver for the travelling salesman, from Dantzig, Fulkerson and Johnson’s 49 cities to William Cook and his colleagues’ proof in 2017 of the optimal tour through 49,687 pubs in the United Kingdom. The worst case is what the conjecture is about, and it is a statement about all instances, which no amount of typical behaviour can settle.

Halves, and the corners they sit at #

The constraints of the relaxation cut out a polytope in a space with one coordinate per road, and the optimum sits at one of its corners, as prices at every corner explained for any linear programme. Every tour is a corner; the danger is the other corners, the fractional ones, which may lie lower. In the two-triangle family the optimum corner has halves on six edges. Among the random instances, four of forty stopped at fractional corners, and every fraction that appeared was a half.

Halves are common in fractional corners for a reason visible in the family: a pair of triangles sharing their weight, each edge at one half, satisfies the degree conditions with odd cycles that no tour could use. Where the corners stop being whole met exactly this for the assignment problem, where adding one edge that closes an odd cycle creates a corner with a half in every coordinate. For the travelling salesman the corners can be more complicated — thirds and other fractions do occur on other instances — but the odd cycle at weight one half is the simplest way to cheat.

The cut conditions forbid some of these corners and not others. The comb inequalities, found by Václav Chvátal and by Martin Grötschel and Manfred Padberg in the 1970s, cut off many of the half-integral corners that the subtour conditions allow, and adding them to the relaxation closes much of the gap on instances like the family. Whether any finite list of such inequality families closes the gap to within less than $\tfrac43$ in the worst case is part of the same open question.

What the relaxation is really measuring #

The subtour relaxation has an unexpected second description. Held and Karp found in 1970 that its optimum equals the best of a family of simpler bounds: choose a penalty for each city, add it to every road at that city, and compute the shortest 1-tree — a tree through all the cities but one, plus the two cheapest roads from that city. Every tour is a 1-tree, so each penalised 1-tree length (minus twice the penalties) is a lower bound, and the best choice of penalties gives exactly the subtour relaxation’s optimum. It is linear programming duality in the form two numbers that have to meet described: the penalties are the dual variables of the degree conditions.

The 1-tree form is what practical solvers compute, because a tree is fast to find. It also shows why the bound is good on random instances: a tour is a 1-tree in which every city has degree exactly two, and the penalties push the tree towards that shape. When they succeed completely, the 1-tree is a tour and the bound is exact — thirty-five times out of forty above. When they fail, it is because the cities’ geometry leaves no cheap way to straighten the tree, and the two-triangle family is a geometry designed to leave none.

Still open: whether a third is the worst #

The four-thirds conjecture asks whether, for every set of cities with distances obeying the triangle inequality, the shortest tour is at most $\tfrac43$ times the subtour relaxation’s optimum. It has been verified for all small instances by exhaustive computation over the fractional corners, and for some special classes of distances. It is not known in general, and the best bound is Karlin, Klein and Oveis Gharan’s $\tfrac32 - 10^{-36}$.

A proof would say something about algorithms as well as bounds. Every improvement to the upper bound so far has come with an algorithm that constructs a tour within the new factor of the relaxation, and a proof of $\tfrac43$ would very likely yield a $\tfrac43$-approximation algorithm — a large improvement on anything known. The obstacle is the corners: a proof must show that every fractional corner of the polytope, however intricate, can be rounded to a tour paying at most a third more, and the known roundings lose half.

What the pictures cannot show #

Every number here was computed exactly: the relaxation by the simplex method with minimum-cut separation until no violated condition remained, the tours by Held and Karp’s dynamic programme over all subsets of cities, which is exact and limited to about eighteen cities. The formula $4k + 2$ for the family’s shortest tour was checked for $k$ up to 5 and not beyond; the pattern is the standard one, and its general proof counts how often a tour must cross the three paths.

The random instances are samples, drawn with a fixed seed so that the same forty instances appear every time the figure is made, and their share of exact bounds would drift somewhat with a different draw. Forty instances of fifteen cities say little about the worst case, and nothing about large instances, where the gap on random cities is known from much bigger computations. The conjecture itself cannot be tested by sampling at all: a counterexample, if one exists, would be a carefully built instance, like the family here, not a typical one.