Presolve Reductions in Mixed Integer Programming

Please always quote using this URN: urn:nbn:de:0297-zib-60370
  • 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.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger
Document Type:ZIB-Report
Tag:Gurobi; integer programming; presolving
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-04 Explicit machine computation and programs (not the theory of computation or programming)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
CCS-Classification:D. Software
Date of first Publication:2016/12/09
Series (Serial Number):ZIB-Report (16-44)
ISSN:1438-0064

$Rev: 13581 $