Progress in Presolving for Mixed Integer Programming

Please always quote using this URN: urn:nbn:de:0297-zib-42530
  • Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Gerald Gamrath, Thorsten Koch, Alexander Martin, Matthias Miltenberger, Dieter Weninger
Document Type:ZIB-Report
Tag:mixed-integer programming; preprocessing; 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 / 90-08 Computational methods
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
CCS-Classification:G. Mathematics of Computing / G.4 MATHEMATICAL SOFTWARE
Date of first Publication:2013/09/23
Series (Serial Number):ZIB-Report (13-48)
ISSN:1438-0064
Published in:Appeared in: Mathematical Programming Computation, vol. 7 iss. 4 (2015), pp. 367-398
Preprint:urn:nbn:de:0297-zib-42530
DOI:http://dx.doi.org/10.1007/s12532-015-0083-5

$Rev: 13581 $