*Result*: Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization.
*Further Information*
*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. History: Accepted by Antonio Frangioni, Area Editor for Design and Analysis of Algorithms: Continuous. Funding: The work for this article has been conducted within the Research Campus Modal funded by the German Federal Ministry of Education and Research (BMBF) [Grants 05M14ZAM and 05M20ZBM]. [ABSTRACT FROM AUTHOR]
Copyright of INFORMS Journal on Computing is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*
*Full text is not displayed to guests* *Login for full access*