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
- 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.
- Subjects :
- Mathematics - Optimization and Control
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2403.13567
- Document Type :
- Working Paper