The day I put my hand into the shredder

…or so to speak. Recently, I’ve been working (in collaboration with two people) on a production planning model for a network of sawmills. It is not yet customized for a particular company. We came to this particular model after a few meetings, and it is rather clean and easy to read. The project went very well, maybe too well, because at some point, someone said “maybe we should include backorders into this models”. It seemed quite simple and straightforward to include backorders into the model…

…but it wasn’t. We went up adding many variables to account for promised quantities versus delivered quantities, amount of backorders per customer, as well as accounting constraints.  We are close to double the size of the initial model, and we spent a long time debugging it and changing things. For something we might not need in the end.

[Edit: finally, we found a cleaner way to include backorders without being too messy. Still, we spent as much time dealing with backorders as we did for the rest of the model.]

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 … [Continue reading]

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]