Given a collection of cities and the cost of travel between each pair of them, the The simplicity of the statement of the problem is deceptive -- the TSP is one of the most intensely studied problems in computational mathematics and yet no effective solution method is known for the general case. Indeed, the resolution of the TSP would settle the P versus NP problem and fetch a $1,000,000 prize from the Clay Mathematics Institute. Although the complexity of the TSP is still unknown, for over 70 years its study has led the way to improved solution methods in many areas of mathematical optimization. |