Performance variability: consequences

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, and part 2 provided some readings related to the topic. This post presents three of the many consequences of this phenomenon.

You can’t tune a random seed

When a MIP solver finds it difficult to provide good solutions, one of the most common (and powerful) alternatives is to tune the solver’s parameters. Both Cplex and Gurobi provide automated tuning tools for such purpose. The problem is, you can’t tune a metric that is not supposed to impact performance so it performs better on average. Changing the random seed can improve or worsen solution times on a specific instance, but you will not find a good value for a broad range of instances. Some solver settings might reduce the severity of the problem, however. On many models, the impact of changing the random seed is much larger than tuning the solver’s parameters.

Algorithm development

The magnitude of performance variability brings challenges in terms of algorithmic development. PV introduces some serious noise in the measurement of algorithmic performance. It becomes more difficult to assess whether a new branching rule or a new heuristic improves a MIP code or not. The optimal MIP recipe was already known to be instance-dependent; now, it can also vary according to other parameters such as random seed or input order that are intractable in dimension. This implication was accurately summarized by Emilie Danna in 2008, but it is still very relevant. The same curse applies to tuning, as “good” parameter settings for solvers must hopefully be better over a broad range of instances and be consistent across random runs.

Problem tractability

MIP models are often sorted according to difficulty, such as “models that take less than 1 minute to solve”. In several cases, the impact of PV-induced changes in solving times is enough to make a model jump from a difficulty class to another. A model which would be “easy” if solved with seed n would become difficult if solved with seed n+1.

This has practical implications as well. Let’s say a customer needs a solution to a scheduling problem in 10 minutes at most. Solving times vary from 3 to 15 minutes depending on instance data and random seed. If solution quality increases steadily during the search, then a time limit can be enforced on the solver in order to grab the best solution in 10 minutes at most. However, it is not always the case. Below is the a figure showing the evolution of the gap over time. The blue line represents the optimality gap while the red line represents the value of the best integer solutions, which is what the user is interested in.

P64T28C5

The solver quickly finds a solution after a few seconds, and that solution stays for about 10 minutes. When it finds a much improved solution, the solver terminates very quickly. If we end the search after 10 minutes (600 seconds) we get a very poor quality solution.

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.

Performance variability defined

These days, it seems that one of the most simple and effective ways to tackle difficult mixed-integer programming (MIP) models is to run the model on a state-of-the-art solver with different random seeds. It is very easy to implement and often … [Continue reading]

In-house testing of CPLEX distributed MIP

Distributed optimization is now part of standard CPLEX releases. In fact, it's been there since release 12.5. I decided to do some experiments and post on this after seeing Daniel Junglas' talk at the German OR Conference in September, but writing … [Continue reading]

In-house testing of the Gurobi 6 distributed MIP [dual]

Distributed optimization is now part of the Gurobi 6.0 release. In today's post, I talk about some tests I ran with the distributed MIP algorithm. The associated primal post discusses results presented by Gurobi at the INFORMS 2014 Annual conference. … [Continue reading]

Distributed MIP solving reaches Gurobi [primal]

Distributed optimization has now reached the point where it is incorporated into general-purpose mixed-integer programming (MIP) solvers such as CPLEX and Gurobi. In today's post, I will summarize the implications of some results presented at the … [Continue reading]

Inventory routing when it matters

Leandro CC Seminar

Yesterday we had the pleasure of welcoming Prof. Leandro C. Coelho for a research seminar at the Forac research consortium. He presented his work on the inventory routing problem (IRP) which is a combination between the vehicle routing problem (VRP) … [Continue reading]

Academia and software neutrality

When I started my PhD, the only MIP solver that was used at the lab was Cplex. At that time, it was considered the best by the people I worked with. I say "considered", because I took this assumption as a fact without actually testing it. I could … [Continue reading]

Using the CPLEX tuning tool on difficult models

The question on how a tuning tool can help solve difficult optimization models has been intriguing to me. 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 … [Continue reading]

OR-Enabled Collaborative Logistics

Today's post is about collaborative logistics, one field of study in which I recently started to work in. It is a tricky field for many reasons, and I will try to explain why and how. Operations research is a key enabler of collaboration. Logistics … [Continue reading]