World's most popular travel blog for travel bloggers.

Performance gain by implementing streamlined simplex

, ,
Problem Detail:

I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of the problems are in the order of N=10.000 sources and N=10.000 destinations, and 2N=20.000 restrictions of equality, one for each source and one for each destination.

I've been using Python's PuLP with the standard solver(COIN-OR) and with GLPK. As a general rule, the performance of COIN-OR is superior than that of GLPK, but even with COIN-OR the problems are taking too long to be solved. As far I as know, there's a streamlined version of the simplex algorithm for transportation problems, but I ignore the magnitude of the improvement in performance I should expect by using that streamlined version of simplex algorithm.

So, my first question is if those solvers identify the transportation problem structure of the problems I'm dealing with and act accordingly.

If the answer turns out to be no, then my second question is if I can exploit that particular structure of the transportation problems with a free solver that has a Python interface.

Also, will I note some improvement if I implement myself the streamlined version of the simplex algorithm? Or implementations must be too far from naive to really beat a well-established simplex solver like the ones I mentioned before?

By "streamlined", I assume you are talking about a minimum cost flow algorithm, and you have been using the standard LP solver from Coin-OR. Then I would advise using the solver from the Lemon library (from Coin-OR as well). It has Python bindings.

As for the performance, I never benchmarked it myself. Given the algorithms involved, however, just the datastructure specialization may well be a 10x improvement. For some problems, I guess the difference may well be orders of magnitude.

I don't think Coin-LP detects the network structure - I'm pretty sure neither it nor GLPK does.

There are algorithms specialized for transportation problems (even more specific than MCF), but here you'd probably have to reimplement them, and not gain as much as going from generic simplex to minimum cost flow.

While looking for benchmarks, I just found two other solvers linked from this blog post, with performance claims: Google OR-tools and PyMCFSimplex.