One of the most famous problem in OR/MS and computer science. The reason for this is that the problem is so easy to describe but so difficult to solve as its size (number of cities) increases.
In many OR/MS oriented textbooks, perhaps most, the problem is described mathematically as a linear integer programming problem - a slight complication of the classical Assignment Problem.
It is great pity that such textbooks do not expose students also to other formulations of the problem, formulations that are not linear programming oriented.
One of the things I plan to do, is write a short paper on this topic. I really do hope that I'll have the time to do it. It is long overdue. I should have done this many years ago!
I have been using the problem for many years for several purposes. Firstly, as a tool for exposing students to the idea that the same problem may have completely different formulations. Secondly, as a framework for illustrating the Curse of Dimensionality in the context of dynamic programming.
The tutOR module on the TSP is designed for illustrating the modelling and computational aspects of dynamic programming.
 |