Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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

Author:Gerald GamrathORCiD, Thorsten KochORCiD, Alexander Martin, Matthias MiltenbergerORCiD, 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 / 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)
Published in:Appeared in: Mathematical Programming Computation, vol. 7 iss. 4 (2015), pp. 367-398
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.