> 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:
- Gabor Pataki (2003), “Teaching Integer Programming Formulations Using the Traveling Salesman Problem”, SIAM Review, Vol. 45, No. 1, pp. 116-123, http://www.unc.edu/~pataki/papers/teachtsp.pdf
- A.J. Orman & H.P. Williams(2004), “A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem,” The London School of Economics and Political Science, http://www.lse.ac.uk/collections/operationalResearch/pdf/Working%20Paper%2004.67.pdf
- Lee J., and J.F. Raffensperger (2006), "Using AMPL for teaching the TSP," INFORMS Transactions on Education, Vol. 7, No 1,
- An MS-Access based front-end for tsp42 is described in how-to-call-gams-from-access.
- More GAMS examples based on Burma-14 dataset from TSPLIB: powerset example.
- Drawing TSP tours in GAMS: post.