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