Speedups: comparing against moving targets

[This is post #1 of 2 that were inspired by a tweet from IBM’s Jean-François Puget]

Over the course of my studies, I had to develop custom solution methods for very challenging supply chain network design problems. While striving to create better models and solution algorithms, I had to compare the performance of my approach with those of generic solvers, mostly CPLEX and Gurobi. As we were improving our methods, commercial solvers were also improving, and by orders of magnitude. It was a fun but challenging – and sometimes stressful – experience.

First contact with solver upgrades

My advisor wasn’t what I would call a “metaheuristic jovialist”, so I had to prove that what we were developing was more efficient than commercial solvers on these particular problems. (We did select agent-based optimization in the end, but that’s another story). While I was preparing my thesis proposal, we were pretty confident that the problems we were investigating would remain challenging for several years – being large-scale and often nonlinear. A typical mixed-integer instance would have between 500,000 and 2 million variables and about 35 constraint types (250 000 total).

One of the first things we developed was a set of simplified instances of the problem. These had about 50,000 variables and 2000 constraints. At that time our lab had about twelve CPLEX 10.x licenses – they were not yet free for academics. One particular problem (let’s call it #13) solved in a little more than one hour. Not bad. A little while later, we upgraded to CPLEX 11.1. I was quite astonished by solution times: that the very same model was solved in 10 minutes!

More upgrades!

At the CO Logistics 2010 spring school in Montreal, Canada, Robert Bixby presented a chart that estimated the cumulative speedup from CPLEX 1.2 to CPLEX 11 at around 29530 (it’s on slide #27 of his presentation). This is the software speedup, not taking into account hardware evolution. I was both amazed and a little nervous for my thesis: what would happen if one day a solver is able to solve my difficult models in a few minutes? This was a source of both motivation and fear.

A little while later, CPLEX 12 was out, and with parallel processing enabled by default. After a few experimentations, I decided to run it on single-thread mode because of memory consumption as well as the huge variance in run times for a given model. This rather unfortunate behavior was corrected CPLEX 12.4 and 12.5.  During the course of my thesis I used 8 different versions of CPLEX, and experimented with 2 Gurobi versions. I briefly switched to Gurobi while CPLEX 12.1 was out, then came back to CPLEX around 12.3 or 12.4.

A glance at solver speedup

To have a glance of solver speedup during my thesis, I computed the run time required to prove optimality on instance #13 on a good old application server we have since 2009. The chart is on logarithmic scale (basis 10). While I needed 2842 seconds to solve instance #13 with CPLEX 10, version 12.5 needs only 56 seconds to solve it – a speedup of about 50 times! I did not perform this experiment on all test instances I used, but I guess that the average speedup would be around 8 – 10 times, which is still huge.

PNE-013-Speedup

How is this possible?

While virtually every component of the MIP solver toolbox has improved lately, two culprits can be found explaining for that huge speedup:

  • The ability to obtain primal solutions quickly. It’s much more difficult for a generci algorithm to generate a feasible solution to a multi-period SCND model, than to a multi-period lot-sizing model, not only because of instance size, but because most SCND models have different structures in different periods. CPLEX 10.x needed a few thousand nodes before encountering a feasible solution to instance #13, while CPLEX 12.5 can find one at toot node.
  • Parallel processing makes sure than node exploration goes much faster. On a four core CPU, that part of the search is simply 4 times faster.

I have no hard evidence on this. Besides intuition and experience, my conclusions are probably influenced by Professor John Chinneck‘s work on integer feasibility and solver performance.

At the time of finishing my thesis, neither CPLEX nor Gurobi were able to solve my models to optimality. However, their ability to find good solutions on the more difficult models had improved. Who knows, maybe CPLEX 13 or Gurobi 6 will tackle my most difficult instances easily!

Trackbacks

  1. […] Always upgrade to the latest version of the solver you use […]

  2. […] Every major release of mathematical programming solver comes with pretty significant performance improvements. For instance, Gurobi reports 22% average improvements on mixed-integer programming (MIP) and 10% on pure linear programming models between versions 6.5 and 7. CPLEX is usually in the same ballpark of version-to-version improvements. Mosek reports 40% mean improvements for conic quadratic problems between versions 7 and 8. These are pretty significant, especially when compounded over multiple versions. I give a personal example here. […]

Speak Your Mind

*