6037
eng
reportzib
0
--
2016-12-09
--
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.
1438-0064
urn:nbn:de:0297-zib-60370
Tobias Achterberg
Tobias Achterberg
Robert E. Bixby
Zonghao Gu
Edward Rothberg
Dieter Weninger
ZIB-Report
16-44
eng
uncontrolled
integer programming
eng
uncontrolled
presolving
eng
uncontrolled
Gurobi
Software
Explicit machine computation and programs (not the theory of computation or programming)
Mixed integer programming
Mathematical Optimization
Achterberg, Tobias
MODAL-SynLab
https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf