Re: [Help-glpk] Need some help: very urgent

[Michael Hennebry]

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   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."