Publication Date:
2021-08-05
Description:
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.
Language:
English
Type:
article
,
doc-type:article
Permalink
