Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization

Leon Eifler (), Jules Nicolas-Thouvenin () and Ambros Gleixner ()
Additional contact information
Leon Eifler: Zuse Institute Berlin, 14195 Berlin, Germany
Ambros Gleixner: HTW Berlin, 10318 Berlin, Germany

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 933-944

Abstract: This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers in practice, that is, without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: the speed of LP iterative refinement, in particular, in the majority of cases when a double-precision floating-point solver is able to compute approximate solutions with small errors, and the robustness of precision boosting whenever extended levels of precision become necessary. We compare the practical performance of the resulting algorithm with both pure methods on a large set of LPs and mixed-integer programs (MIPs). The results show that the combined algorithm solves more instances than a pure LP iterative refinement approach while being faster than pure precision boosting. When embedded in an exact branch-and-cut framework for MIPs, the combined algorithm is able to reduce the number of failed calls to the exact LP solver to zero while maintaining the speed of the pure LP iterative refinement approach.

Keywords: linear programming; mixed-integer programming; rational arithmetic; exact computation; numerically exact linear programming; iterative refinement; high-precision optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0409 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:4:p:933-944

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().