Can the CPLEX tuning tool help solving hard models?

The CPLEX MIP Solver has had a tuning tool for some time. For those new to the concept, the tuning tool tries different parameter settings and seeks to find good parameters for the solver for a given optimization model. I have tested the tuning tool on 10 relatively difficult-to-solve models. By difficult, I mean models that take between 4 and 12 hours of clock time to solve with CPLEX 12.5 (default settings) on a decent 4-core machine. Five of these models are capacitated lot-sizing models and the other 5 are capacitated facility location models.

The conclusions of my limited investigations are:

  • When used with default settings, the tuning tool often takes a long time to solve. On some models, the tuning took more than 10 hours. This is annoying, but it can easily be circumvented by setting a time limit (see tip #1).
  • On 9 out of 10 models, the tuning tool suggested alternative settings that improved solution times. However, the reduction in solution times were not astonishing (between 2% and 14%).
  • On 1 model, the actual parameter tuning proposed results in slightly longer solution times (around 13%).

Discussion

While the tuning tool may help solve some models faster, it is unlikely that the improved settings may move  a wide range of models from “unsolvable” to “solvable” or from hard to easy. I have used the tuning on other models in the past year and it yielded similar results: improvements in performance, but no drastic reduction of run times.

I am also aware of several parameter tuning algorithms that may well offer superior performance than CPLEX’s own tuning tool [1]. However, CPLEX’s tool is still worthy of testing : since the tool comes with the solver, it requires no particular skills to use (such as programming) and no separate installation.

Tip #1: set a time limit

By default, when used on difficult models, the tuning tool may take too much time and computer resources. You can however easily set a limit to CPLEX’s greed by using the set tune timelimit parameter (in seconds). Be aware, however, that this parameter sets the maximum number of seconds allowed per try of the algorithm, not the total amound of time allowed for the entire tests. As a rule of thumb, it takes about 6 times the value of the parameter (if set restrictively) to perform all the tests, so if you want to allow a total of 10 minutes (600 secs) for testing, you should enter about 100 as a parameter value.

From what I have experienced so far, the tuning tool can find good parameter values even when operating on very restrictive schedules. However, make sure that your parameter exceeds the time required to solve the LP relaxation and for the algorithm to perform a few branching operations.

Note to CPLEX 12.4 and prior users: I have seen some CPLEX 12.4 crashes if the solver runs out of memory when executing the tuning. This problem has been fixed in version 12.5. If possible, I urge you to upgrade to CPLEX 12.5.

[1]      Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown and Thomas Stützle. ParamILS: An Automatic Algorithm Configuration Framework. Journal of Artificial Intelligence Research, 36: 267-306, 2009.

Comments

  1. I’m just wondering if tuning tools are comparable to random perturbations of the problem:
    http://mat.tepper.cmu.edu/blog/?p=1695

    CPLEX 12.5 has random seed feature to do just that:
    http://bit.ly/XMJjJr

    • As far as I know, the tuning tool does not work on permuting the model itself like what’s done in M. Fischetti’s work, but it does change different rules regarding the algorithms (node selection, variable selection, presolve techniques, activation of heuristics, etc.)

  2. I usually try to run smaller instances of difficult problems, hoping on the one hand that the tuning tool will run faster on the smaller instances and on the other hand that the smaller instances are sufficiently representative of the larger ones that the tuning tool’s parameter suggestions are appropriate.

    • That’s a nice idea. I wonder whether option proves to give the better insights: running the tool on smaller instances or quick runs on instances of the same size. That’s to be investigated.

Speak Your Mind

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.