Info-Gap Decision Theory | Voodoo Decision-Making | Robust Decisions | Severe Uncertainty | Satisficing vs Optimizing | Maximin


Traveling Salesman Problem

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.

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.

On of the things I plan to do this year is write a short paper on it. 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.



Disclaimer: This page, its contents and style, are the responsibility of the author (Moshe Sniedovich) and do not represent the views, policies or opinions of The University of Melbourne.

Disclaimer: This page, its contents and style, are the responsibility of the author (Moshe Sniedovich) and do not represent the views, policies or opinions of the organizations he is associated/affiliated with.