travelling salesman for BGL ?
I'm looking for a free "travelling salesman problem" solver. Does anyone know if something exists for the Boost Graph Library ? I found nothing in the book... Is anybody interested in porting existing code, for example http://www.math.princeton.edu/tsp/concorde.html on BGL ? -- Philippe Guglielmetti - www.dynabits.com
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
"Matthias Rupp"
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.
the freely available code packages that i found, i preferred the concorde code you mentioned above. Unfortunately, for larger problems it requires
From 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
------------------------ Yahoo! Groups Sponsor ---------------------~--> Buy Ink Cartridges or Refill Kits for Your HP, Epson, Canon or Lexmark Printer at Myinks.com. Free s/h on orders $50 or more to the US & Canada. http://www.c1tracking.com/l.asp?cid=5511 http://us.click.yahoo.com/l.m7sD/LIdGAA/qnsNAA/EbFolB/TM ---------------------------------------------------------------------~->
Info: http://www.boost.org Wiki: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl Unsubscribe: mailto:boost-users-unsubscribe@yahoogroups.com
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
You'll be a millionaire (literally!) if you figure out the exact solution to TSP in an efficient manner!
participants (3)
-
Dave -
Matthias Rupp -
Philippe Guglielmetti