[Boost-users] Re: travelling salesman for BGL ?

From: Dave (better_cs_now_at_[hidden])
Date: 2003-11-12 22:08:54

"Matthias Rupp" <rupp_at_[hidden]> wrote in message
news:200309012315.54905.rupp_at_stud.uni-frankfurt.de...
>
> 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
>
>
>
> ------------------------ 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_at_[hidden]>
>
>
> 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!