Presolve Reductions in Mixed Integer Programming
epub ahead of print
- 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.
Author: | Tobias AchterbergORCiD, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger |
---|---|
Document Type: | Article |
Parent Title (English): | INFORMS Journal on Computing |
Year of first publication: | 2019 |
Preprint: | urn:nbn:de:0297-zib-60370 |