Less is More

30 January 2009 by Sanjay Saigal.

The market in optimization software is experiencing a state of turbulence last seen in the mid-eighties, when OSL and CPLEX were fighting for dominance. CPLEX won that war, not simply because it was competitive on benchmark models, but by being better engineered, and later, better marketed. With the perspective of 20+ years, Bob Bixby’s decisions – writing in C rather than FORTRAN, centralizing optimizer usage on an API/library rather than an interactive system, focusing on building a market by targeting value-added software vendors rather than just OR professionals – seem obvious. But at the time, they were quite unorthodox.

From the viewpoint of one privileged to witness the development of CPLEX at close range (Bob directed my thesis), the second major factor accounting for CPLEX’s success was its exceptional product R&D team that came together in the mid-late nineties. Its two generals were Ed Rothberg, who came over from the legendary parallel numerical computation group at Silicon Graphics, and, later, Zonghao Gu, a Lindo escapee.

Ed went on to lead CPLEX into the realm of reliably solving mixed-integer programs (MIPs) by smartly adapting academic research on cutting plane methods. To be fair, in the process, Ed, Gu, and the rest of the team created a fair bit of (largely unpublished, for competitivee reasons) new computational science. By the time Ed moved on to real-time semiconductor scheduling, Gu was ready to captain what had become the 800 pound gorilla of the optimization space. For a variety of reasons, in 2008 Bixby, Gu, and Rothberg left Ilog (CPLEX’s home since 1997) and started their own venture, rather unimaginatively called Gurobi Optimization. (Who is who in the picture is left as an exercise to the reader!)

I learned to my surprise that Gurobi planned to build a linear and mixed-integer code from the ground up. First, there was the obvious competitive angle vis-a-vis Ilog – they would have to start from absolute ground zero. Not even a line of CPLEX code could make it into their solver. Secondly, there was the question “why?” Having already built CPLEX into a lasting success, why would they wish to go over the same ground again? I confess that the question is still open. Nevertheless, more power to them, because it is becoming clear, that we may have a new contender on our hands. Via Mike Trick, I learn this morning of recently released third-party benchmarks comparing the performance of Gurobi’s as-yet-unreleased optimizer and CPLEX’s latest release.

Optimizer benchmarks are best taken with a great deal of caution. However, what these results suggest is nothing short of stunning: Less than a year in development, Gurobi is essentially competitive with CPLEX. On a 74-problem MIP test-set:

• Gurobi solves MIPs faster on single-processor machines: It beats or equals CPLEX’s performance 55% of the time. (A third solver – MOSEK – is also compared. It wins or ties for first 5% of the time.)
• Gurobi parallelizes robustly: Having used it in a number of projects over the years, I can attest that CPLEX’s parallel branch and bound is a very solid piece of code. In this one-on-one comparison on a 4-processor machine, Gurobi wins or ties CPLEX 58% of the time.
• Aggregate solution times are less on Gurobi: Considering only problems on which at least one integer solution was found, on a single-CPU system Gurobi runs through the test-set in 25% less time than CPLEX, as measured using the geometric mean of times. On 4-CPU systems, the improvement is still considerable – 15%.
• Gurobi is good at finding integer feasible solutions: CPLEX fails to identify a single integer feasible solution on 2 instances in either mode. Gurobi fails on one instance in single-threaded mode. It finds at least one integer solution on all test-set problems when using four processors.
• CPLEX takes better advantage of parallelization: CPLEX’s speed-up in going from one to four processors is 40%, whereas Gurobi only manages 30%.