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.