Progress in presolving for mixed integer programming

Gamrath G, Koch T, Martin A, Miltenberger M, Weninger D (2015)


Publication Language: English

Publication Type: Journal article, Original article

Publication year: 2015

Journal

Publisher: Springer Verlag

Book Volume: 7

Pages Range: 367-398

Journal Issue: 4

DOI: 10.1007/s12532-015-0083-5

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.

Authors with CRIS profile

Related research project(s)

Involved external institutions

How to cite

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: Download