A guest post today from Debra Johnson. I have not altered the American spelling or the politically incorrect title!
Given a salesman who needs to travel to a certain set of cities, what is the least expensive way for him to get to all of his destinations and return home? This question is known as the traveling salesman problem (TSP), and it is an important problem for computational mathematicians. Because the problem is one of general optimization, its solution has applications for diverse fields including transportation, electronics and genetics. Even though it has been formally studied by mathematicians since the 1930s, no general solution has yet been discovered for the TSP.
Attempts at solving specific instances of the TSP have taken different forms and have been made by mathematicians, computer scientists, chemists, physicists and other scientists. In the 1950s and 1960s, integer linear programming was used to solve an instance of 49 cities. In the 1990s, a group of mathematicians developed a computer program called Concorde that is capable of solving for larger numbers of cities. In fact, William Cook, one of the program’s developers, worked with other scientists to solve a record 33,810 city tour based on a layout problem for a microchip.
The actual problem is, on its surface, a simple one. However, current methods require each instance to be solved individually. A general solution has eluded mathematicians for decades. This difficulty is due to the fact that the TSP is an NP-hard problem. This means that, among other things, the TSP is a problem in which correct solutions are easy to verify, but there is no efficient way to solve the problem itself. This also means that a solution to the TSP would put to rest the question of whether or not it is possible to solve NP-complete problems. Called the P versus NP problem, this is one of the most challenging questions facing mathematicians today. In fact, it was designated a millennium prize problem by the Clay Mathematics Institute. This means that the one who solves this problem will win a million dollar prize.
In addition to putting the P versus NP problem to rest, a solution to the TSP would revolutionize many fields. Far from being merely a mathematical curiosity, the TSP has many practical applications. Obviously, it directly applies to logistics and transportation. This makes finding a solution valuable to the military, commercial delivery services, companies that schedule home service calls, bus companies and many others. The model is also general enough that it can be applied to other fields such as microchip design, genome sequencing, fiber optic network design and others. The wide applicability of the TSP model, the million dollar prize and the difficulty of finding a general solution make the TSP an intriguing and important problem in applied mathematics.
About the Author:
This guest post is contributed by Debra Johnson, blogger and editor of live in nanny.
She welcomes your comments at her email Id: – jdebra84 @ gmail.com.
Sometimes, Best is the enemy of Good (Enough). Sure, a general solution would be marvelous, but a good computational heuristics for cases where n is < 1000 would be tremendously useful to a lot of applications.
As it stands, the NP scarecrow turns everyone away on the basis that no general solution has been found…leaving truck drivers in the neighborhood to a random walk of fuel-inefficient deliveries.
I don’t agree. I think that the world is big enough for the Good and the Best to coexist.
I have been to several conference talks (most recently just last December) where somebody presented a new and improved heuristic for TSP. Even if there were an abstract proof that P=NP, this activity would continue.
A similar case fairly recently was the proof that primality testing can be done in polynomial time. It was certainly not the case that people immediately stop using probabilistic algorithms for primality testing. Or again, Khachian’s ellipsoid method showed that linear programming is polynomial-time, but a lot of people went on using the simplex method (and still do).
Another point is that complexity theory is wide enough to embrace approximation. There are some cases where, even though exact calculation is hard, there is an efficient approximation algorithm; but many more where this is not known.
I didn’t mean mathematicians around the world should stop looking for a general solution, Peter.
All I meant is that, in my very specific, pointy-haired environment, if someone puts the NP tag on an approach, it’s the kiss of death. We won’t consider any approximation, any heuristics…anything, we will move right along and try to sidestep the “problem”, as if it were the plague.
What I meant is that, even though some problems are truly NP, under certain conditions (where n is kept below a limit), they are tractable and can be addressed quite elegantly using an approximation or a heuristics.
In my environment, which is not focused on mathematics, no one should read the NP sign as meaning “dead end”.
In that spirit, could you share a link to that talk of last December?
An interesting result I saw recently had to do with the so-called gas station problem. It’s a case where adding a realistic constraint to the problem makes it solvable.
http://www.cs.umd.edu/projects/gas/gas-station.pdf
Just picking a nit… the NP tag on its own does not mean that the problem is necessarily hard; all polynomial time or even trivial decision problems are in NP.
It is the NP-hard or NP-complete problems that cause difficulties.
The actual problem is, on its surface, a simple one. However, current methods require each instance to be solved individually. A general solution has eluded mathematicians for decades. This difficulty is due to the fact that the TSP is an NP-hard problem. This means that, among other things, the TSP is a problem in which correct solutions are easy to verify, but there is no efficient way to solve the problem itself. This also means that a solution to the TSP would put to rest the question of whether or not it is possible to solve NP-complete problems. Called the P versus NP problem, this is one of the most challenging questions facing mathematicians today. In fact, it was designated a millennium prize problem by the Clay Mathematics Institute. This means that the one who solves this problem will win a million dollar prize.