[ANN] New free tool for TSP solving

[dmitrey]

Hi all, 

New free tool for TSP solving is available (for downloading as well) - OpenOpt TSP class: TSP (traveling salesman problem).

It is written in Python, uses NetworkX graphs on input (another BSD-licensed Python library, de-facto standard graph lib for Python language programmers), can connect to MILP solvers like glpk, cplex, lpsolve, has a couple of other solvers - sa (simulated annealing, Python code by John Montgomery) and interalg

If someone is interested, I could implement something from (or beyound) its future plans till next OO stable release 0.41, that will be 2 weeks later (Sept-15).

Regards, D.

[Nathann Cohen]

Helloooooooooooooooooooo !!

New free tool for TSP solving is available (for downloading as well) - OpenOpt TSP class: TSP (traveling salesman problem).

Oh ! Nice ! Is it possible to read its implementation  from a web page ? (sorryyy, I do not have access to a real computer right now, and I will not until several weeks ^^;)

In Sage we just hand the problem to LP solvers, but even if you do the same I would love to see how you formulate it :-) 

Nathann

[dmitrey]

On Monday, 3 September 2012 06:57:41 UTC+3, Nathann Cohen wrote:

Helloooooooooooooooooooo !!

New free tool for TSP solving is available (for downloading as well) - OpenOpt TSP class: TSP (traveling salesman problem).

Oh ! Nice ! Is it possible to read its implementation  from a web page ? (sorryyy, I do not have access to a real computer right now, and I will not until several weeks ^^;)

 

Hi Nathann,
I have updated OO TSP page with link to the OpenOpt TSP class file:

http://trac.openopt.org/openopt/browser/PythonPackages/OpenOpt/openopt/kernel/TSP.py
however it requires some code cleanup, although, also, some OpenOpt kernel hacks beyond standard kernel-solver API are temporary used
Regards, D.

[Nathann Cohen]

Helloooooooo !!

> I have updated OO TSP page with link to the OpenOpt TSP class file:

Thank you ! It looks like you use the MTZ formulation, with some additional simplifications when there are vertices of in/out degree 1 in the graph :-)

The formulation we have in Sage should be very competitive, as it is more topological than MZT.. But of course it probably depends on the instances you want to solve, too :-)

Have fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuunnn !!

Nathann