Performance Variability in Mixed-Integer Programming

By Andrea Lodi, Andrea Tramontani. 2013

141 citations recorded by the source corpus.

The performance of mixed-integer programming solvers is subject to some unexpected variability that appears, for example, when changing from one computing platform to another, when permuting rows and/or columns of a model, when adding seemingly neutral changes to the solution process, etc. This phenomenon has been observed for decades, but only recently has it started to be methodologically analyzed with the two possible aims of either reducing or exploiting it, ideally both. In this tutorial we discuss the roots of performance variability, we provide useful tips to recognize it, and we point out some severe misinterpretations that might be generated by not performing/analyzing benchmark results carefully. Finally, we report on the most recent attempts to gain from variability.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Learning to Run Heuristics in Tree Search (2017, background): “This measure is a standard one for computational MIP studies, as it helps to control for the inherent “performance variability” in solvers – see [Lodi and Tramontani, 2013; Achterberg and Wunderling, 2013] for details.”
MIPLIB 2010 - Mixed Integer Programming Library version 5 (2011, unknown): “We use the term performance variability [42] to denote such changes in performance measures for the same problem that are caused by seemingly performance-neutral changes in the environment or the input format.”
Solving Mixed Integer Programs Using Neural Networks (2020, methodology): “Performance variability with respect to random seed: To account for the performance variability of MIP solvers (Lodi and Tramontani 2014) with respect to changes to a MIP that leave the problem unchanged, such as permuting rows and columns of the constraint matrix, we vary the random seed parameter ”
On handling indicator constraints in mixed integer programming (2016, methodology): “, [18,24]) we selected the 18 instances forwhich adding local implied bound cuts produced a speedup larger than 1.”
On learning and branching: a survey (2017, background): “As pointed out by Lodi (2013), the exact computation performed by MILP solvers relies on a somehow surprising collection of heuristic decisions, two of the most crucial ones being those associated with the branching scheme outlined above, namely – variable selection , which of the variables x…”
Tight and Compact MILP Formulation for the Thermal Unit Commitment Problem (2013, background): “works prefer to look at the number of simplex iterations rather than nodes in order to perform comparisons [15], [31].”