Performance of LP solvers

You should take a look at Hans Mittelmann's benchmarks, specifically the serial and parallel LP sections (and the large network LP benchmarks if your model has an underlying network structure). You'll see order of magnitude differences in some cases, but good luck finding a consistent winner -- it seems to be rather problem-specific. Interestingly (at least to me), CLP seems to beat both CPLEX's and Gurobi's simplex solvers on some problems (though frequently their barrier solvers seem to beat CLP on the same problems -- perhaps signaling massive degeneracy?).

Hi

For large problems like yours it is our (http://www.mosek.com) experience that interior-point methods (aka barrier methods) are usually faster than simplex methods. To my knowledge only the commercial code offer good interior codes.

You are willing to make your problem available then we can run a benchmark for you.

Best Regards

Erling (CEO at MOSEK)

It is definitely worth a try to use an interior point based solver on your problem type. I have personally seen problem types where the difference between state of the art simplex and interior point implementations was staggering (simplex based methods (Clp, Cplex simplex) taking on the order of hours, whereas all interior-point based methods (Cplex barrier, Mosek) finishing within minutes). This obviously depends on the problem type and for some problems the reverse holds true. Therefore, try both.

Regarding the large scale problem where interior point is much faster than simplex. I have often found that you can substantial speedup the simplex solution times by knowing about the problem structure ex. a certain types of variable should be preferred to some other types of variables in entering or leaving the basis. But this is very problem specific and only for experts to figure out. On the contrary the interior point requires no dirty tricks it runs nicely with default settings, which makes it the preferred algorithm for such problems. Actually the simplex is born under a lucky star, since it's run time complexity in practice "in most cases" is far from the theoretical complexity, but there are bad cases were you see the worst case performance. Understanding and improving the simplex algorithm on these instance is interesting future research..

Please note the problem selection in the benchmark is somewhat biased towards complicated LP problems i.e most of them is either not numerical stable or has structure which can be exploited. So in my opinion this might over estimate the difference between a "not so good" and "good" LP solver. If you want to be sure of good performance, then you should purchase one of the best commercial packages, but you might find that some open source solver provide acceptable performance on your problem structure.