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?