Performance variability: good readings

If you work on difficult mixed-integer programming (MIP) models, you have experienced performance variability. This refers as the impact on performance of seemingly performance neutral changes induced in the model or the solver. Part 1 of this series presented the problem and its relevance. This post presents some good readings related to the topic. Many thanks to my colleague Leandro C. Coelho (@leandro_cc on Twitter) for his help in building this list!

Some good readings related to performance variability

[1] Lodi, A., Tramontani, A. (2013). Performance Variability in Mixed-Integer Programming, in Tutorials in Operations Research, 1-12.

An recent introductory text on performance variability. It is a bit brief, but if you only have one hour to devote to this topic, this is what you should read. However, the paper requires some good familiarity with components common to modern MIP solvers.

[2] Fischetti, M., Monaci, M. (2014). Exploiting Erraticism in Search. Operations Research, 62(1): 114-122.

That a paper about performance variability can get published in Operations Research tells a lot about the importance of the topic in MIP computation.  Rather than providing a diagnosis of performance variability, the  authors propose a solution approach that exploitsit, by starting short runs with different initial conditions then completing the most promising among them.

[3] E. Danna. Performance variability in mixed integer programming. Presentation, Workshop on Mixed Interger Programming (MIP 2008), Columbia University, New York. Accessed July 21, 2013, http://coral.ie.lehigh.edu/~jeff/mip-2008/talks/danna.pdf, 2008.

It’s slides rather than a paper, but there is lot of very useful information out there. In this talk, Emilie provides a good definition for performance variability and investigates many possible factors that might cause or influence performance variability.

[4] Klotz, E., Newman, A.M. (2013). Practical Guidelines for Solving Difficult Mixed Integer Linear Programs. Surveys in Operations Research and Management Science, 18(1-2): 18-32.

This paper provides very useful information on what are the most common sources of bottlenecks limiting performance in solving MIPs. It explains how to identify the cause of performance drag as well as some tactics on how to tune the solver to tackle this difficulty. If you are working on difficult MIPs and interested in ways to make the solver work (instead of developing a heuristic or a model-specific algorithm), this is a must read. A preleminary version is available on the author’s website.

If you have suggestions of additional references, please send them to me and I will add them to the post.

Comments

  1. Jeff Linderoth says

    The correct (and old) web location for Emilie’s talk
    has my full first name (jeff), not “je” 🙂

Speak Your Mind

*

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