Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver
2024
Online
report
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.
Titel: |
Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver
|
---|---|
Autor/in / Beteiligte Person: | Borst, Sander ; Eifler, Leon ; Gleixner, Ambros |
Link: | |
Veröffentlichung: | 2024 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|