Have you heard the one about the travelling salesman?

Karen Herland

In math circles, the traveling salesman problem (TSP) involves scheduling a tour that covers every town in the cheapest possible way. It is a notorious problem in a field known as combinatorial optimization, but it also appears in many other domains. The TSP has been used as an exercise in physics, algorithm mathematics, geometry, even neuropsychology (children and adults are invited to attempt the same TSP to compare cognitive and perceptual skills).

Vasek Chvátal (Computer Science and Software Engineering) holds a Canada Research Chair in Combinatorial Optimization. His interest in the TSP came from two sources. He has had an impressive track record of results on “hamiltonian circuits” (a mathematician's term for the salesman's tours), including a result found jointly with one of the greatest mathematicians of the last century, Paul Erdös. He is also the author of a widely popular textbook on linear programming (published by Freeman in 1983 and still going strong), which is the workhorse of all successful TSP methods.

It started when Chvátal was having a drink in Greenwich Village with his friend William Cook. Cook proposed they boldly go where numerous theorists had gone before. “Solving the TSP is a competitive sport and getting into the arena seemed an appealing lark. My only apprehension was that we might get sucked into spending a couple of years there, but Bill was vehement that this was unlikely.

“At first, we would just daydream about ways of winning the gold medal. Then Bill pointed out that a computer might help. So we went to this little shop and got a Compaq.”

That was in 1987, and 19 years later, a 593-page book The Traveling Salesman Problem: A Computational Study has just been published by Princeton University Press.

Early on, Chvatal and Cook asked David Applegate to join them. In 1988, Bernhard Korte took the three of them into his Institut für Diskrete Mathematik in Bonn, where they found an ideal working environment. “Our battle cry was ‘be different!’ Everyone attacked the TSP by the simplex method of linear programming, and so we went a different route." However, being iconoclastic proved unproductive in this case.

They soon returned to the simplex method and recruited a leading expert on its implementations, Robert Bixby, into the team. The four of them designed a TSP computer program named Concorde and eventually they co-authored the book.

Concorde's initial breakthrough came in 1992, when it found the best tour through 3,038 cities (one of a collection of 110 problems of varying complexity used to challenge TSP computer programs).

A few more gradually increasing successes led in 2000 to the prestigious Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming for the team. By April 2006, Concorde had solved the last unsolved instance of the 110 challenges.

Chvátal stresses that producing the best tour is almost always relatively straightforward. The real test is proving that it is the absolute best one that can be produced. Chapter 15 of the new book talks about how to find the solution; the rest of the book is about proving it. He also notes that Concorde is now used in applications of TSP to diverse areas such as genome sequencing and post-manufacture testing of computer chips.

With the TSP finally out of the way, Chvátal can now focus on new challenges. Last year, he organized a two-week summer school called Combinatorial Optimization: Methods and Applications, and then a five-day international workshop at the Centre de recherches mathématiques.

Its agenda coincided with the research plan of a group of his graduate students and colleagues established as ConCoCO for Concordia Computational Combinatorial Optimization.