7262
2019
eng
article
0
2019-11-08
--
--
Presolve Reductions in Mixed Integer Programming
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.
INFORMS Journal on Computing
yes
epub ahead of print
2018-08-31
urn:nbn:de:0297-zib-60370
Tobias Achterberg
Franziska SchlĂ¶sser
Robert E. Bixby
Zonghao Gu
Edward Rothberg
Dieter Weninger
Mathematical Optimization
Mathematical Optimization Methods
Achterberg, Tobias
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt