CODEWITHSUNDEEP
discrete-mathematicslinear-programmingtraveling-salesmanglpkinteger-programming
ire_and_curses
ire_and_curses

Reputation: 70142

What size tour can I reasonably expect to solve with GLPK?

I'm playing around with the travelling salesman example provided with GLPK, and trying to get a feel for what problem size I can reasonably expect to solve. I've managed to solve a 50 node graph, but 100 nodes doesn't seem to be converging in a reasonable timescale (30 minutes or so on modern hardware).

GLPK has lots of options for the MIP solver. I've tried various combinations but I'm not at all clear what options might help. This page has some discussion but is somewhat out of date and the advice is rather general.

Is it reasonable to expect GLPK to solve a 100 node tour or greater in a practical time frame (say, less than 4 hours)? When does the problem size become intractable? Are any of the many command-line options likely to help?

Upvotes: 0

Views: 827

Answers (2)

Granada
Granada

Reputation: 363

I was able to solve eil51 in 2 seconds and rat99 in about 50 seconds by starting with a relaxation of the TSP and then eliminating sub-tours until a feasible solution is found. Doing a better modelling is going to achieve more than fiddling with the solver options. GLPK should be able to deal with bigger instances if the modelling is good enough. eil51 and rat99 are instances documented on TSPLIB.

I recommend reading some material on tsp modelling, there are a lot of articles and books out there. A nice starting point maybe 'Applied Integer Programming' by Der-San Chen et al.

Upvotes: 1

Ali
Ali

Reputation: 58431

Are any of the many command-line options likely to help?

The tspsol command line applicaton (based on the GLPK C library) or the C API in glptsp.h are tailor-made for solving TSP.

Is it reasonable to expect GLPK to solve a 100 node tour or greater in a practical time frame (say, less than 4 hours)? When does the problem size become intractable?

My guess is that it also greatly depends on the problem instance as well. If you look into the C code, you will see that heuristics are used to generate an initial tour. How well a heuristic works, well...

I assume you know that the TSP is famous for being difficult to solve, see computational complexity.

Upvotes: 1

Related Questions