The million-dollar problem explained
On March 19, William J. Cook presented a lively talk entitled In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation to a crowd of around 100 people at Concordia University.
Cook was on campus to discuss a mathematical conundrum that is subject matter of his new book, The Traveling Salesman Problem: A Computational Study. Co-authored by David Applegate, Robert Bixby, and Concordia's own Canada Research Chair in Combinatorial Optimization, Vasek Chvátal, the book examines what’s known as the travelling salesman problem, or TSP. Simply put, the problem assumes a salesman has a list of customers to visit in multiple locations and tries to find the most effective route possible between them.
It seems simple but the TSP has been confounding mathematicians since it was first defined in the 1800s. The problem began to be studied more thoroughly in the 1930s by mathematicians Karl Menger and Hassler Whitney. By the late 1940s, when linear programming was introduced by Julia Robinson, TSP-related research really began to take off.
Explains Cook, “mathematical shortcuts provided by linear programming meant mathematicians no longer had to attempt to solve the TSP by mapping an endless number of possible routes by hand. It was a very exciting time for applied mathematicians. Digital computers were in their final planning stages, and there was plenty of funding available for research.”
In 1954, George Dantzig, Ray Fulkerson and Selmer Johnson of the RAND Corporation in Santa Monica wrote a technical paper on the subject. The paper was immensely important in the world of applied mathematics and became known as the ‘Big Bang’ of TSP-related research. “It’s really what set the tone and techniques that still dominate today,” Cook said.
Despite these advancements, the solution to the travelling salesman problem still eludes mathematicians today. The Clay Mathematics Institute is offering a $1-million prize to anyone who can solve it — making the TSP, quite literally, a million-dollar problem. Cook explains that, due to certain constraints, it may never be solved.
“That doesn’t make the travelling salesman problem go away,” according to Cook. “There are still all these nice, beautiful algorithmic and geometric considerations, but more importantly there are certain limits to general computing. What are those limits, and how tightly do they constrain our quest for knowledge, science, economics and elsewhere? That’s what the travelling salesman problem is all about, and that’s why we’re doing all this.”
Third-year journalism student Lesley De Marinis is an intern with Concordia's University Communications Services.
Related links:
• Concordia's Faculty of Engineering and Computer Science
• Article on Cook in the New York Times (scroll down to March 14 entry)
• Book listing on Princeton University Press site