Wednesday, August 6, 2008

How write a TSP model in GAMS

> My TSP model does not work: it has sub-tours

The TSP (Traveling Salesman Problem) is not complete trivial to write as a MIP.
Direct MIP models are only suited for very small problem. For larger models
you need more advanced strategies.

You can see some examples in the model library all written by me: tsp1, tsp2, tsp3, tsp4, tsp42 (the listed author is incorrect: I wrote this model). The last one is actually an algorithm that adds subtour elimination cuts to a relaxation.

For more information see the following papers and posts: