Progress in presolving for mixed integer programming

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autorinnen und Autoren: Gamrath G, Koch T, Martin A, Miltenberger M, Weninger D
Zeitschrift: Mathematical Programming Computation
Verlag: Springer Verlag
Jahr der Veröffentlichung: 2015
Band: 7
Heftnummer: 4
Seitenbereich: 367-398
ISSN: 1867-2949
eISSN: 1867-2957
Sprache: Englisch


This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Martin, Alexander Prof. Dr.
Professur für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Weninger, Dieter Dr.
Professur für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


Gamrath, G., Koch, T., Martin, A., Miltenberger, M., & Weninger, D. (2015). Progress in presolving for mixed integer programming. Mathematical Programming Computation, 7(4), 367-398.

Gamrath, Gerald, et al. "Progress in presolving for mixed integer programming." Mathematical Programming Computation 7.4 (2015): 367-398.


Zuletzt aktualisiert 2018-12-12 um 13:50