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 provides better improvement than tuning the solver or using custom heuristics or solution procedures. This post is the first of a series of short posts on this phenomenon.

A working definition

The best definition I found for PV comes from Danna (2008):

Performance variability is a change in performance (solving times, # nodes, # of interations) for the same model created by a change in the solver or the environment that is seemingly performance neutral.

Some example of changes that should be performance neutral include change in the random seed, changes in the order of input of the variables or constraints of the model. The latter, in particular, is counter-intuitive.

How serious an issue PV is?

Quite serious. While small levels of variability are to be expected and are not problematic (say, a variation of about 10% in solving times), more drastic changes are common.Danna’s presentation starts with an example for which the solution time increases by a factor of 100!  These changes in order of magnitude of problems are especially problematic, because it makes problem classification very difficult. Is the model really difficult to solve or has the solver simply made some very bad random choices during the solution?

What are the causes?

While we have a good idea about some of the factors contributing to performance variability in general, the specific causes are not well known. It is very difficult to predict whether a model is likely to be heavily affected by PV issues for a given solver, except by trial and error. Moreover, PV can be experienced very differently on similar instances of the same model. This means that many insights found when solving a particular model are not necessarily applicable to similar models.

In the next post, I present some relevant readings on PV.

Trackbacks

  1. […] 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 […]

Speak Your Mind

*