This post is inspired by a blog post by analytics and software engineer Nathan Brixius concerning recent media interest in the Traveling Salesman Problem (TSP). The TSP, for the uninitiated, is to find a minimum-distance route between a set number of points; as the number of points increases, the problem of being certain one has found a solution becomes computationally formidable. Thus, the problem is really to find an efficient algorithm for finding solutions.
Randal Olson’s minimum-distance road trip
Come out with guns blazing, or lay out the welcome mat?
Michigan State computer science grad student Randal Olson developed, and blogged about, an algorithm to solve the Traveling Salesman Problem for a 48-stop tour of the United States. This is almost the exact same version of the problem featured in 1954 in the first publication to use linear programming methods to address the TSP. Olson’s approach was picked up by blogs at the Washington Post and New York TImes websites as an interest story. Unfortunately, Olson also suggested that guaranteeing a solution is computationally impossible—for 48 stops it is actually very simple to prove optimality.
TSP expert Bill Cook, Professor of Combinatorics and Optimization at the University of Waterloo, quickly pointed out that the true shortest route—35,940 meters shorter than Olson’s—could be easily computed on an iPhone using his Concorde TSP app. Brixius writes that, good as it is to point out OR’s extensive work on the TSP, it was important to go gently on Olson’s misstatements so that the OR profession would not come out of the episode looking bad.
And it’s here where, as a historian of science who happens to study the history of OR, I find I recognize the issue from two complementary perspectives.