Back to Search Start Over

Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver

Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver

Authors :
Borst, Sander
Eifler, Leon
Gleixner, Ambros
Publication Year :
2024

Abstract

This paper presents the integration of constraint propagation and dual proof analysis in an exact, roundoff-error-free MIP solver. The authors employ safe rounding methods to ensure that all results remain provably correct, while sacrificing as little computational performance as possible in comparison to a pure floating-point implementation. The study also addresses the adaptation of certification techniques for correctness verification. Computational studies demonstrate the effectiveness of these techniques, showcasing a 23% performance improvement on the MIPLIB 2017 benchmark test set.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2403.13567
Document Type :
Working Paper