The salesman’s expedition

The last chapter ended with a question. Routing, scheduling and cutting problems are NP-hard, and most experts are sure that no fast exact algorithm exists for them. Yet logistics people solve them every day for thousands of vans. To do it, they give up one of three demands: exactness, a guarantee, or the worst case. An approximation algorithm settles for a route that is nearly the best. A heuristic promises nothing in advance but in practice comes out close to the optimum. An exact solver finishes the job on the inputs that turn up in real life, though not on every input. Each of these concessions gives a tool of its own, and we’ll try them all on one problem by holding a contest.

1962. A ten-thousand-dollar contest

We’ll hold our own contest under the same rules. Our thirty-three towns are Moravian: the most populous towns and villages of the South Moravian Region, where in Chapter 23 we ran power lines along a spanning tree. Distances are measured in straight lines. The first contestant is you.

The search for the shortest round trip is known as the traveling salesman problem, after the salesman of old textbooks who had to make the rounds of a string of towns. Its version “is there a round trip of length at most $L$?” is NP-complete: in the last chapter seating the guests reduced to it. Finding the shortest trip itself is NP-hard. Our distances are ordinary straight-line ones, and they satisfy the triangle inequality: the direct road from A to C is no longer than the road through B. Almost every guarantee below rests on this inequality.

How many routes are there? Start in Brno (which town you start from makes no difference) and choose an order for the other 32: that gives $32!$ possibilities, and every tour is counted twice, once in each direction. So there are $32!/2 \approx 1.3 \cdot 10^{35}$ tours. A computer that checks a billion tours a second would spend $4 \cdot 10^{18}$ years on them, hundreds of millions of times the age of the universe. Here is how the cleverest of the exact methods, one you can write in ten lines, copes with that.

Contestant one: exact computation

The dynamic programming of Chapter 22 can handle this problem too. For the traveling salesman it was proposed independently in 1962, the year of the contest, by Richard Bellman and by the pair Michael Held and Richard Karp; Karp is the author of the twenty-one problems from the last chapter. The subproblem: the shortest path that leaves town 0, passes through exactly the set of towns $S$, and ends at town $j$. The answer for $S$ is assembled from the answers for sets one town smaller: we have to choose the town $k$ from which we came to $j$. A set is conveniently stored as a bit mask, a number whose bit $j$ is one if town $j$ is in the set; we took shifts and masks apart in Chapter 28.

Instead of $n!$ tours we have $n^2 2^n$ steps: for sixteen towns that takes a fraction of a second, whereas trying every tour would take years. But the exponential hasn’t gone anywhere. Thirty-three towns take several days and a table of seventy billion cells that won’t fit in the memory of an ordinary computer. Fifty towns take thousands of years. The exact method, which knows nothing beyond the definition of the problem, is the first to drop out of our contest.

Contestant two: the nearest neighbor

The most natural strategy is the one a person without a map would use: from each town, go to the nearest one you haven’t visited yet. Chapter 23 warned that greed goes wrong here. The question is by how much. To compare, we need the optimum: it is 393.88 km, and at the end of the chapter the judge will prove it.

Starting from Brno, the greedy driver covers almost 40% more than necessary. The picture shows why. At first every step is short, but the towns get picked off one at a time until only the forgotten ones on the edges remain, and reaching them means crossing the whole map. Try all 33 starts and keep the best, and the loss drops to 14%. On random points the nearest neighbor is on average about a quarter longer than the optimum. That is bad but not a disaster, and it is computed instantly, in $O(n^2)$, which makes it a good starting point for the contestants that follow.

Contestant three: the tree walked twice

The greedy route comes with no guarantee: you can build a map on which it is worse than the optimum by any factor you like. The next contestant thinks longer but makes a promise. It takes the minimum spanning tree from Chapter 23, walks around it like a tour guide, depth first, along every edge there and back, and then takes shortcuts: if the next town has already been visited, it drives straight on to the next new one.

This is an approximation algorithm: it runs in polynomial time and guarantees an answer within a given factor of the optimum, here a factor of two. On the Moravian towns it lost 27%, more than the best greedy start: the guarantee speaks of the worst case and promises nothing about the usual one. But hidden in the proof is the judge’s first tool. The length of the tree, 318.6 km, is a lower bound: the optimum can’t be shorter. Before we even know the optimum, we know it lies between 318.6 and 498.4 km.

In 1976 Nicos Christofides, and independently the Soviet mathematician Anatoliy Serdyukov (who published in 1978), found a way to save on the return trips. The towns with an odd number of tree edges are paired up as cheaply as possible (this is a matching problem, a relative of those in Chapter 25), and once these edges are added, every town has an even degree. The resulting graph can be traversed using each edge once, as in Euler’s problem, and then shortcut. The guarantee is one and a half times the optimum. For forty-four years nobody could improve on it. In 2020 Anna Karlin, Nathan Klein and Shayan Oveis Gharan did, by an amount on the order of $10^{-36}$, and the ratio became slightly less than 1.5. The gain is negligible, but the work proved that one and a half is not the limit, and it is regarded as a major achievement.

Contestant four: 2-opt

Back to the greedy route. It has crossings, places where the route runs across itself. Anyone who sees one will untangle the loop. Say the route goes A → B, then a long way, then C → E, and the edges AB and CE cross. Replace them with AC and BE, and drive the stretch between B and C in reverse. In the plane this always pays off: the two diagonals of a quadrilateral are longer than a pair of its opposite sides, by the triangle inequality once again. Such a move is called 2-opt, because two edges change. G. A. Croes proposed it in 1958.

Each frame is one untangling. In twenty-five moves the greedy route turns into a tour of about 399 km, a little over one percent worse than the optimum. Out of a hundred random starts, 2-opt finds the optimum itself sixteen times, and sometimes gets stuck as much as 16% above it. It gets stuck on a route where no pair of edges can be improved any more, even though a better route exists: to reach it, you would first have to make things worse.

The general scheme is called local search: take a solution and improve it with small moves while improvements can be found. A solution that no single move can improve is a local optimum. Think of a hilltop in fog: everything around is lower, but somewhere there may be a mountain. The moves can be made bigger, changing three edges instead of two, or chains of edges of varying length. That is how the Lin–Kernighan algorithm (1973) works, and its descendant LKH, by Keld Helsgaun, still finds the best known routes for huge problems. For millions of points it produces tours that, judging by the lower bounds, are within a fraction of a percent of the optimum. But even it has its hills. How do you come down from a hill in order to climb the mountain?

Contestant five: annealing

A smith who wants strong metal heats it and then lets it cool slowly. Hot atoms jostle and can jump from a bad position into a good one, and if the metal cools slowly they have time to settle into a regular lattice. Cool it at once, and the atoms freeze in disorder, in a local minimum of energy. In 1983 three physicists at IBM, Scott Kirkpatrick, Charles Gelatt and Mario Vecchi, proposed in a paper in Science that routes be treated the same way, and called the method simulated annealing. They took the rule from a 1953 paper by Metropolis and his coauthors, the same Metropolis who gave the Monte Carlo method its name in Chapter 26.

The rule goes like this. Pick a random 2-opt move. If it shortens the route, always make it. If it lengthens the route by $\Delta$ kilometers, make it with probability $e^{-\Delta/T}$, where $T$ is the “temperature.” At a high temperature almost any move is accepted, and the search wanders freely among the routes. At a low one only improvements get through, and the search becomes ordinary 2-opt. The temperature is lowered little by little. Try it yourself: below, the temperature is in your hands.

All five runs, each from a random route, arrive at 393.88 km, the optimum, and each takes a fraction of a second. But annealing is a heuristic without guarantees too: on other maps and with other schedules it gets stuck, so it is run several times and the best result is kept. The subtle part is the cooling schedule. Too fast, and the search freezes on the first hill it comes across; too slow, and time is wasted. The schedule is chosen by experience, the way a smith chooses it. In the same paper Kirkpatrick and his coauthors applied annealing to a problem that mattered to IBM: how to place the components on a chip so that the wires between them come out shorter. Annealing is still at work today in chip design software, in scheduling and in cutting problems.

Contestant six: evolution

The last heuristic contestant borrowed its method from nature. Genetic algorithms, developed by John Holland in the 1970s, keep a whole population of solutions at once. The best survive and interbreed, their offspring undergo mutations, and generation by generation the population improves. For routes, crossover is arranged so that the child is still a route: it takes a piece from the mother, and the remaining towns in the order they appear in the father’s route.

Evolution starts from random routes three times longer than the optimum and in four hundred generations gets within a few percent of it. In our contest that is a modest result: annealing on its own did better and faster. On the traveling salesman, pure genetic algorithms usually lose to good local search, and the winners are hybrids, in which every child is also untangled with 2-opt. Evolution comes into its own on problems where almost nothing is known about how solutions are built and no clever move suggests itself: antenna shapes, engine parameters, the settings of other algorithms.

The judge: how to prove nothing is better

Heuristics produce a route but say nothing about how far it is from the optimum. The judge needs the other side of the bracket, a lower bound: a number proved to be no greater than the length of any tour. We already know one, the spanning tree at 318.6 km. It is weak, but it can be tightened. In 1970 Held and Karp proposed the 1-tree: a spanning tree on all the towns but one, plus the two shortest edges from that one. Every tour is a 1-tree too: remove one town from it, and what remains is a path, which is a tree. So the shortest 1-tree is no longer than the optimum.

The next step is to add surcharges. Give each town a penalty $\pi_i$ and count the length of an edge $(i, j)$ as $d_{ij} + \pi_i + \pi_j$. In any tour every town has two edges, so all tours grow by the same $2\sum\pi_i$ and their order doesn’t change. But 1-trees change by different amounts. Penalize the towns that have more than two edges in the 1-tree, reward the leaves, and step by step the 1-tree comes to look like a tour.

In fifty steps the bound grows from 333 km to 393.7. By the hundredth step it trails the length of annealing’s tour by one meter, and by the three hundredth it matches it outright: what remains is less than a nanometer, which is rounding error in floating-point arithmetic. That is the judge’s verdict. No route is shorter than 393.88 km, annealing found the optimum, and your result, like those of the other contestants, can be measured against this number. We have proved optimality without trying a single tour: the upper bound from a heuristic and the lower bound from 1-trees met in the middle.

It doesn’t always work out like this: on large, hard maps the bracket between the bounds doesn’t close. Then two techniques come into play, which together make up integer programming. The problem is written as a linear program with variables meaning “do we drive along road $(i, j)$”: $x_{ij} \in \{0, 1\}$.

Allow the variables fractional values between 0 and 1, and you get an ordinary linear program, which can be solved in polynomial time, as Leonid Khachiyan proved in 1979. Its answer is again a lower bound, since an integer tour is a special case of a fractional one. If the fractional answer happens to be integer, we have an optimal tour. If not, there are two moves. A cut: find an inequality that holds for every tour but is violated by the fractional answer, like the “no separate loops” condition that Dantzig added as the need arose, and solve again. A branch: pick a fractional variable and solve two problems, one with $x_{ij} = 0$ and one with $x_{ij} = 1$, throwing out the branches whose lower bound is already worse than a tour found earlier. This branch-and-bound method was proposed by Ailsa Land and Alison Doig in 1960.

These ideas are the foundation of Concorde, a program by David Applegate, Robert Bixby, Vašek Chvátal and William Cook. In 2006, with the help of Helsgaun’s heuristic, it found the shortest tour through 85,900 points and proved that none is shorter. The points come from a chip layout that arose at Bell Labs in the late 1980s. By the authors’ count, the computation took over 136 CPU-years. The same branching and cutting are at work in industrial integer programming solvers, which draw up airline and railroad schedules and plan production and deliveries. And that answers the question from the start of the chapter, how logistics people cope. The problem is NP-hard, but practical instances have structure, and a solver can often push them all the way to a proved optimum or to a guarantee like “at most 0.3% worse than the optimum.”

An exhibition performance: the SAT solver

Here it is, the certificate for a “no” answer that co-NP so badly lacked on the map of complexity classes: two hundred terabytes of steps, each of which a separate program checks mechanically. We’ll try the same problem with the solver cs.sat.solve. It is the DPLL you wrote in the last chapter, only with two watched literals.

Up to three thousand, the solver colors the numbers instantly, with hardly any dead ends. At 3,500 there are already more than ten thousand dead ends, and at 4,000 it gives up, even though a coloring certainly exists there, all the way to 7,824. Heule and his coauthors needed a solver of a newer generation. In DPLL a dead end teaches only one lesson: this branch is bad, go back a step. Modern solvers, starting with GRASP (1996) and Chaff (2001), analyze every dead end: which chain of inferences led to it and which of the decisions made along the way are to blame. The analysis yields a new clause that forbids the guilty combination. The clause is added to the formula, so the solver never makes the same mistake twice, and the solver jumps straight back to the guilty decision, however many steps ago it was made. Such solvers are called CDCL, for conflict-driven clause learning. They handle formulas with millions of variables, verify processor designs and programs, resolve dependencies in package managers and build timetables.

And here is the solver at work on sudoku, whose NP-completeness in the general case we discussed in the last chapter. There are 729 variables, “cell $r, c$ holds digit $d$,” and about twelve thousand clauses: every cell has a digit, no cell has two digits at once, and in every row, column and box each digit appears and doesn’t repeat.

The newspaper puzzle gets solved without a single decision: everything follows from unit propagation, the way an experienced player writes in a digit only when it is the only one possible. Puzzles with the bare minimum of clues need a few decisions and backtracks. Without propagation, though, the same solver drowns in brute force: every inference used to cut off a whole branch of possibilities, and now each of them has to be walked through.

Out of competition: fire stations

One last problem from Karp’s list shows that greed sometimes does come with a guarantee. The region has decided to build fire stations in some of its 675 villages so that no village is more than 8 km from the nearest station. How can it make do with the fewest stations? Each candidate village covers a set of villages around it, and we need to choose as few sets as possible that together cover everything. This is set cover, an NP-hard problem. The greedy approach is obvious: each time, take the village that covers the most villages not yet covered.

For 675 villages $\ln n \approx 6.5$: the greedy 56 stations could be six and a half times as many as the best cover needs, though in practice the gap is far smaller. The guarantee was found in the 1970s by David Johnson, László Lovász and Vašek Chvátal. And in 2014 Irit Dinur and David Steurer proved that if $\mathrm P \ne \mathrm{NP}$, no polynomial algorithm can guarantee noticeably better than $\ln n$. So as far as guarantees go, greed is the best that can be done here. In the task “Greedy cover” you will make it fast.

The results

Here are the results on the thirty-three Moravian towns. You know your own place in the table from the arena at the start of the chapter.

This table adds up to a recipe for the day a hard problem turns up at work. First, recognize it: if it is the traveling salesman, coloring, the knapsack or set cover in disguise, don’t look for a fast exact algorithm. Estimate the size: with twenty objects, exhaustive search with pruning or dynamic programming over subsets will do, and there is nothing to think about. Look closely at the structure: perhaps your data are a special case where greed works, as with the spanning tree. If the problem is large and general, write it down in a language that ready-made solvers understand, a formula for a SAT solver or an integer program, and try them: they often deliver a proved optimum. If that doesn’t help either, build a good solution with heuristics: a greedy start, then local search, then annealing if local search gets stuck. And always keep a lower bound at hand, so you know how much more there is to gain: three percent from the optimum is a reason to stop, thirty is a reason to keep thinking.

Tasks

Three tasks for the chapter’s three tools: local search, annealing, and greed with a guarantee.

What next

Hardness, it turns out, is something you can live with. The exact answer for thirty-three towns came in a fraction of a second, even though the problem is NP-hard: a heuristic supplied the route, and a lower bound proved that nothing is better. For thousands of towns we would settle for a route one percent worse than the optimum, and we would know that it is only one percent.

But hardness can’t always be sidestepped. In the last chapter the solver factored ten-digit numbers, and every extra bit made its job harder. For 600-digit numbers there is no way around it: no heuristic from this chapter will cope with them. So hardness is not only a nuisance. A lock can be built on it, hiding a secret so that without the key neither annealing nor solvers nor all the computers in the world can find it. But before building locks on hardness, it is worth seeing how the old locks were built and broken, the ones that relied on cunning and secrecy. That is where Part X begins, with “The cipher bureau.”