Exact mixed-integer programming: a status update on MIP solving without numerical errors

Abstract: 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. This is joint work with Leon Eifler.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.