Boost logo

Boost Users :

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
> 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.


Matthias Rupp

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at