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

Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework

Please always quote using this URN: urn:nbn:de:0297-zib-90159
  • This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set.

Download full text files

Export metadata

Metadaten
Author:Leon EiflerORCiD, Ambros GleixnerORCiD
Document Type:ZIB-Report
Tag:Mixed integer programming, Exact computation, Rational arithmetic, Cutting Planes, Symbolic Computations, Certificate of correctness
MSC-Classification:65-XX NUMERICAL ANALYSIS
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2023/03/22
Series (Serial Number):ZIB-Report (23-09)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.