Presolve Reductions in Mixed Integer Programming

Tobias Achterberg (), Robert E. Bixby (), Zonghao Gu (), Edward Rothberg () and Dieter Weninger ()
Additional contact information
Tobias Achterberg: Gurobi GmbH, 10245 Berlin, Germany
Robert E. Bixby: Gurobi Optimization, Beaverton, Oregon 97008
Zonghao Gu: Gurobi Optimization, Beaverton, Oregon 97008
Edward Rothberg: Gurobi Optimization, Beaverton, Oregon 97008
Dieter Weninger: University Erlangen-Nürnberg, 91054 Erlangen, Germany

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 473-506

Abstract: Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the “strength” of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed integer programs and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature.

Keywords: mixed integer programming; presolving (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0857 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:2:p:473-506

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().