TY - JOUR
A1 - Achterberg, Tobias
A1 - Bixby, Robert E.
A1 - Gu, Zonghao
A1 - Rothberg, Edward
A1 - Weninger, Dieter
T1 - Presolve Reductions in Mixed Integer Programming
T2 - INFORMS Journal on Computing
N2 - 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.
Y1 - 2019
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7262
ER -