Re: travelling salesman for BGL ?

From: Matthias Rupp (rupp_at_[hidden])
Date: 2003-09-01 16:15:54

Hello Philippe,

> I'm looking for a free "travelling salesman problem" solver.
> Does anyone know if something exists for the Boost Graph Library ? 
> Is anybody interested in porting existing code, for example
> http://www.math.princeton.edu/tsp/concorde.html on BGL ?

I have recently busied myself with computing exact solutions to the TSP. From 
the freely available code packages that i found, i preferred the concorde 
code you mentioned above. Unfortunately, for larger problems it requires the 
CPLEX solver, which is quite expensive.

I know of no code using the BGL. I considered using the held-karp based solver 
from the concorde code, but the code itself is not documented, so i didn't 
pursue that avenue much further. I'm not so sure if the BGL is appropiate 
here (except as a way to pass a graph to the solver) because efficiency is 
rather important.

I'm interested in (symmetric) TSP instances with up to ca. 70 vertices 
(200-300 would be perfect, but i don't think this can be done with a 
combinatorial based solver, and i'm not very familiar with Integer 
Programming). I would be interested in a fast, portable and free solver for 
TSP instances in the above range.

Regards,

Matthias Rupp