Thursday, May 21, 2009

Gurobi v/s CPLEX: A real-life LP example

The general availability of Gurobi, the new solver in town means that it allows us to compare how the de-facto commercial standard for the last 3 decades matches up. For starters, lets look at that good old work-horse, the Simplex Method. In particular, we will look at the dual simplex performance on a particular LP from real-life that has very few rows and many, many bounded columns that tries to maximize a linear objective function subject to "<=" constraints. Perfect for dual simplex since most of your work is with 6x6 linear systems for this instance.

Let's see what the default solvers of CPLEX and Gurobi do with it. You would like to think that there should not be much difference when it comes to 'mature' technology. Surprise.
These are run on my personal Ubuntu-Linux quad-core PC, 4GB RAM in serial mode. While the data is not available for public use, it should be easy to generate random instances of similarly sized LPs and do your own tests.

The result:CPLEX-dual simplex is nearly 40X slower on this instance.

--------------------------------------------------------
Problem stats: 6 Rows, 935645 Columns, 3192263 Non zeros

Gurobi solves it in 76 iterations and 10.16 seconds
Optimal objective 9.531245720e+05


CPLEX
-----
Tried aggregator 1 time.
LP Presolve eliminated 0 rows and 392 columns.
Reduced LP has 6 rows, 935253 columns, and 3191065 nonzeros.
Presolve time = 3.06 sec.

Initializing dual steep norms . . .

Iteration log . . .
Iteration: 1 Dual objective = 1203067.101646
....
Solution status = Optimal
Solution value = 953124.5720420766
Solution time = 391.32 seconds

It is well known that f your dual-simplex implementation is fast, all your branch-and-cut operations that rely on dual-simplex will also be that much more faster.

CPLEX-Primal was even slower, but CPLEX-Barrier does it in about 100 seconds (including the cross-over to a corner solution), which is still 10X slower. I tried many other tweaks with CPLEX for what should have been a relatively quick and simple problem to solve for an industry-standard LP solver, but without much improvement. To be fair to CPLEX, which is still a fantastic product, this is just one instance. Without the barrier solver as yet, Gurobi may be slower on LPs that are strongly amenable to interior point methods (more on that in a future post).

Hopefully, the owners of these products will continue to devote R&D effort toward these two great products and keep pushing the envelope, so we practitioners get the best of both worlds!

-------------------------------------------------------------------------------
Disclaimer: These are purely my personal observations made in an unofficial capacity, based on tests on a very limited sample of real-life data sets, and do not reflect the views of my employers or associates. I am not affiliated with Gurobi or ILOG-IBM.
-------------------------------------------------------------------------------

7 comments:

  1. I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. OKP Holdings Real Estate Developer

    ReplyDelete
  2. The ascent in the quantity of property holders who are submerged on their home loans has expanded so a lot of that an exceptionally huge number of them have concluded that they can't bear to remain in their homes. Local Realty Service

    ReplyDelete
  3. This is a fantastic website and I can not recommend you guys enough. I really appreciate your post. It is very helpful for all the people on the web. croyde holiday cottages

    ReplyDelete
  4. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article. https://realcricketmodapk.com

    ReplyDelete
  5. This appears undeniably remarkable. All of these very small facts are constructed choosing large selection about qualifying measures know-how. Document gift a good deal quite a lot. sales

    ReplyDelete
  6. It was wondering if I could use this write-up on my other website, I will link it back to your website though.Great Thanks. Chloe

    ReplyDelete

Note: Only a member of this blog may post a comment.