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.

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.

OR dwarfs history¹. According to the U.S. Bureau of Labor Statistics, in 2012 there were 73,200 people working as “operations research analysts” in the United States alone. Moreover, in the present age of ubiquitous computation and optimized logistics, the profession is in good health, with 27% further growth expected by 2022. Yet, like the history of science, OR has never been an especially visible profession. It has often operated in the shadow of such related, but more famous disciplines as computer science.

Some operations researchers are therefore eager—like some historians of science—to take advantage of rare opportunities to promote themselves during a fleeting moment of media attention, and can logically regard correcting mistakes and misperceptions as a part of that. Yet, Brixius urges, most people do not actually need the extremely powerful approaches to the TSP that the OR profession has spent the last 60 years developing. Given that reality, it doesn’t make sense to “shoot a guy because he rolls his own solver for a blog post.”

I share the sentiment, and think historians of science should similarly learn to maybe not be too prickly when scientists decide to talk about the history of science without having achieved the requisite credentials. But that’s a subject for another time, and for my other blog.

For some people, algorithms are never good enough

Here let’s stick with the Traveling Salesman Problem, and why you would want to continue to explore it, as people in the OR profession have, for over 60 years.

While I discuss the TSP in my book Rational Action, all of our knowledge of its history actually comes from operations researchers’ prior efforts to trace it. I have always relied on Alan Hoffman and Philip Wolfe’s outline in the 1985 volume, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. The Olson episode has brought to my attention an updated history in Cook’s own more popular treatment from 2012, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation.²

We can gain some illumination by placing the TSP within the context of its development. Unlike a lot of practical computational problems that arose in the postwar period, the TSP was not immediately motivated by some practical quandary. Sequential analysis was developed during the war to justify and formalize short-cuts that quality-control inspectors were taking. The Office of Naval Research funded theoretical research on inventory control problems into a thriving research niche. Linear programming was itself developed as part of a project to routinize the U.S. Air Force’s staging (i.e., “programming”) of the steps necessary to undertake missions.

But there were no armies of traveling salesmen demanding optimized routing. The specific formulation of the TSP can be traced to the Austrian mathematician Karl Menger (1902–1985); it appears to have been picked up in America in passing by Princeton mathematician Hassler Whitney (1907–1989), before catching the sustained attention of Whitney’s Princeton colleague Merrill Flood (1908–1991) when he was faced with a practical school bus routing problem in 1937. However, there was no real progress until Flood began promoting it once he joined the RAND Corporation in 1949.

At that time RAND was quickly developing a reputation as a place where work often oscillated between practical problem-solving and theoretical exploration. As economist-historian Judy Klein shows, Richard Bellman’s (1920–1984) development of dynamic programming was at once a generalization of the mathematics involved in sequential analysis and inventory theory, and a means of devising target assignments for nuclear bombers and effective in-flight navigation systems for missiles. But a popular exposition of the technique employed the fanciful example of gold prospecting.

Within this environment, the TSP was more like the gold-prospecting example—an imaginative means of exploring and stretching the potential of new computational techniques. In fact, RAND even offered a cash prize for solutions. Julia Robinson (1919–1985) formulated an early approach, but, as a RAND employee at the time, couldn’t claim the prize. One of the persistent questions surrounding the problem was, given its peculiar features, was there even such a thing as a most effective way of solving it?

And this leads to an interesting question for the historian: how can something like the TSP sustain decades‘ worth of research?

If the TSP were a straightforward problem, adding more “cities” would be a trivial modification, and the ability to solve it would depend merely on available computational power. Mathematicians would quickly turn their attentions elsewhere. Because the TSP is decidedly not a straightforward problem: the question is not so much one of firm solution, but of design, which opens up whole terrains of fascinating problems.

The TSP, of course, did ultimately find practical application, and some designs would be geared toward that. However, other designs would accentuate intellectually novel features. Moreover, designs themselves become the subject of intellectual analysis: how can one design be regarded as superior to another, and under what circumstances? You can, of course, race one algorithm against another, but more satisfying analysis takes a theoretical form.

For an OR theorist, there can be no such thing as a sufficient solution to the TSP, any more than there can be a satisfactory understanding of history for the historian. I was astonished to learn from Brixius’s post that solvers have sped up 5,600,000,000 times since 1990. The title of Cook’s book, In Pursuit of the Traveling Salesman, is an apt way of expressing the unending nature of the work.³

But for others, inefficient algorithms suffice very well

For most practical applications, nothing like that kind of computational efficiency is necessary or desired. One selects a ready-made product, or one even “rolls one’s own” solution, and, if you take a few more microseconds of computer time, or travel a few more kilometers, so be it.

The value one derives from not pursuing absolutely optimal solutions has also been modeled—I have no doubt we’ll get to the concept of “bounded rationality” on this blog before too long. Some would even consider the maximization of this value as a theoretical problem, albeit an abstract one, that can be explored in its own right.

But practical strategies have histories of their own, and for good reason. As Brixius rightly observes, not everyone needs to reach for top-shelf tools, nor can everyone even be aware that such a top shelf even exists. The vanguard and the quotidian, as much as the theoretical and practical, tend to exist in tension with each other. But that tension has by no means precluded productive interaction.

—