Spring 2021

Exact Mixed-Integer Programming over the Rational Numbers

Tuesday, March 30th, 2021 8:30 am10:30 am

Add to Calendar


Ambros Gleixner (Zuse Institute Berlin and HTW Berlin)

The presence of floating-point roundoff errors compromises the results of virtually all fast mixed integer programming solvers available today. The last milestone achievement for the numerically exact solution of general mixed integer programs over the rational numbers dates back to the hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. In this talk, we describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal floating-point heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality.  We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB~2017 benchmark set, we observe an average speedup of 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours.