Progress in presolving for mixed integer programming

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autor(en): 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


Abstract


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-Autoren / FAU-Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Wirtschaftsmathematik
Weninger, Dieter Dr.
Lehrstuhl für Wirtschaftsmathematik


Autor(en) der externen Einrichtung(en)
Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


Zitierweisen

APA:
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. https://dx.doi.org/10.1007/s12532-015-0083-5

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

BibTeX: 

Zuletzt aktualisiert 2018-12-12 um 13:50