Seeds and Parallel MIP solvers, part I

Over recent years, mixed-integer programming (MIP) solver developers worked really hard to provide parallel codes that are both fast and quite stable. A few years ago, using a parallel code resulted in huge variations in run times: successive runs of the same model on the same machine could result in drastically different run times. This behavior is now quite rare, as the codes have been tremendously improved.  This post compares the effect of randomness in solving mixed-integer programming (MIP) models with parallel commercial codes. To that end, I use a set of 30 lot-sizing models (with 40 products and 14 periods) that are available here

Stability of run times

Gurobi developers worked really hard to make sure their parallel MIP solver would produce similar run times when run multiple times. CPLEX now proposes two parallel operation modes, a deterministic mode that guarantees similar tick counts (resulting in similar wall clock times) for runs on a given machine, and an opportunistic mode. The opportunistic mode is faster on average, but it does not offer the same guaranteed (deterministic) stability of run time. On CPLEX 12.6, the deterministic mode (D-mode) is about 19,6% slower on average than its opportunistic counterpart.  You essentially pay for stability of results: solving the same model on the same machine with the same random seed result in near-identical run times for Gurobi and CPLEX in D-mode. However, in CPLEX opportunistic mode, it typically varies from 15% to 50% per run depending on the model (all settings being identical). So in average, it gets better, but you might just be unlucky that day and get a longer run time.

What if I use a different seed?

Even with deterministic solvers, you can end up getting different run times if you change the random seed. What if for your given problem, it just turns out the default seed is not a good one? Instead of trying to tune the solver, what if you tried just to change the random seed you use?  To assess this kind of variability, I used 6 different random seeds. The default seed number is used as a basis for comparison, while seeds 1-5 are used for comparison. I compute the variation as the ratio between the run time for seed i (measured in ticks) / run time for default (in ticks).

  • On a given model, changing the random seed typically results in a variation of ±20% of run time for Gurobi, of 30% of run time for CPLEX in D-mode and 40% for CPLEX in O-mode.

For those who prefer charts, here is the distribution of run time ratios (compared to the default random seed) for CPLEX in deterministic and opportunistic mode.

RandomSeeds-CPLEX

 

Here is exactly the same graph for the deterministic algorithm of Gurobi 5.6:

RandomSeeds-SLSM-Gurobi

I did these experiments on a computer having 32 GB of RAM, an Intel Core i7-3770 CPU and running Windows Server 2012 R2.

Comments

  1. For CPLEX opportunistic mode, is the denominator default seed-opportunistic or default seed-deterministic?

    • The denominator is default seed-deterministic for each. If you want the picture with the opportunistic version compared against its own (opportunistic) default run, here it is: CPLEX chart, 2nd version Unfortunately in this case, the denominator is also some kind of random variable, so if I ran the experiment again I would get different pictures at both numerator and denominator.

Trackbacks

  1. […] a previous post, I showed that changing the random seed on a given problem yielded varies solution times by […]

Speak Your Mind

*