On Tue, 18 Oct 2011, Andrew Makhorin wrote:
the normal way to solve small traveling salesman problems is:
Solve the LP problem without subtour constraints.
Identify subtours.
Add subtour constraints.
Resolve the LP
Repeat the last two steps until no new subtour arises.
With this algorithm, one does not necessarily get an integer solution.
See
http://www.tsp.gatech.edu/methods/opt/subtour.htm
A good book on the topic is
David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook
The Traveling Salesman Problem: A Computational Study
There exist closed mip formulations of tsp. See
http://yetanothermathprogrammingconsultant.blogspot.com/2008/08/how-write-tsp-model-in-gams.html
It needs to be really small.
The closed-form forumlations are really loose.
See also glpk/examples/tsp.mod.
--
Michael [email protected]
"Pessimist: The glass is half empty.
Optimist: The glass is half full.
Engineer: The glass is twice as big as it needs to be."
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
