From: rhoads@sceloporus.rutgers.edu (Glenn Rhoads)
Newsgroups: sci.math
Subject: Re: Traveling Salesman
Date: 23 Feb 1996 17:35:31 -0500

reuven@cinenet.net (Reuven Zach) writes:

>: I am looking for libraries (C or Pascal) for solving the traveling
>: salesman problem. I have some literature about heuristic methods,
>: but so far no libraries. I am sure that somebody already wrote such
>: software and I think it would not make much sense to reinvent the
>: wheel.

>Consult the "Numerical Recipes" by Press et. al.

Numercial Recipes is unlikely to have TSP code.

A public domain C program using heuristic methods is available at
http://www.cenaath.cena.dgac.fr/~maugis/tsp.shar

Also, you can send email to churritz@crash.cts.com and request
the program tsp_solve (written in C++) which finds optimal and
heuristic solutions to TSP problems.

You might also be interested in a library of TSP problem instances
which can be found at
http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html

-- Glenn Rhoads

==============================================================================

From: and@sun1 (Andreas Kromke)
Newsgroups: sci.math
Subject: Re: Traveling Salesman
Date: 26 Feb 1996 10:58:54 GMT

Glenn Rhoads (rhoads@sceloporus.rutgers.edu) wrote:
: Numercial Recipes is unlikely to have TSP code.

That's right. There is nothing about tsp in this book.

: A public domain C program using heuristic methods is available at
: http://www.cenaath.cena.dgac.fr/~maugis/tsp.shar

Thank you, I already had this. Unfortunately it does not contain
the appropriate algorithms for large tsp problems. I think the
used algorithm uses O(n^3) operations, and that is too much.

: Also, you can send email to churritz@crash.cts.com and request
: the program tsp_solve (written in C++) which finds optimal and
: heuristic solutions to TSP problems.

I already had done so, but unfortunately his university does not
allow him to give the source code. So this didn't help. This is
a pity because the program he writes seems to be very interesting.

: You might also be interested in a library of TSP problem instances
: which can be found at
: http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html

I already have this.

Nevertheless, thank you very much for your kind help.


--

------------------------
ANDREAS KROMKE

==============================================================================

From: Mark.N@asu.edu
Newsgroups: sci.math.research
Subject: Re: Q: NP problems
Date: Tue, 20 Aug 1996 04:37:44 +0000 (GMT)

John B. Shaw (sti@teleport.com) wrote:

: I am interested in NP problems, but am new to this field.  I have several
: questions regarding NP problems, in particular the traveling salesman
: problem. 

: Is there any method to estimate the length of the shortest path for a
: given problem?

Shortest path and TSP (travelling salesman) are about the same.  A good 
estimate for the TSP is given by Christophides'algorithm, it's guaranteed 
to never exceed the true value by more than 50%.  (Chapter 17 in 
"Combinatorial Optimization" by Papadimitriou and Steiglitz is a good 
place to start)

Mark Neeley