IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v37y2025i4p933-944.html

Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization

Author

Listed:
  • Leon Eifler

    (Zuse Institute Berlin, 14195 Berlin, Germany)

  • Jules Nicolas-Thouvenin

  • Ambros Gleixner

    (HTW Berlin, 10318 Berlin, Germany)

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.

Suggested Citation

  • Leon Eifler & Jules Nicolas-Thouvenin & Ambros Gleixner, 2025. "Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization," INFORMS Journal on Computing, INFORMS, vol. 37(4), pages 933-944, July.
    • Handle: RePEc:inm:orijoc:v:37:y:2025:i:4:p:933-944
    DOI: 10.1287/ijoc.2023.0409
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.0409
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.0409?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Ambros M. Gleixner & Daniel E. Steffy & Kati Wolter, 2016. "Iterative Refinement for Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 449-464, August.
    2. Joshua A. Lerman & Daniel R. Hyduke & Haythem Latif & Vasiliy A. Portnoy & Nathan E. Lewis & Jeffrey D. Orth & Alexandra C. Schrimpe-Rutledge & Richard D. Smith & Joshua N. Adkins & Karsten Zengler & , 2012. "In silico method for modelling metabolism and gene product expression at genome scale," Nature Communications, Nature, vol. 3(1), pages 1-10, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. repec:plo:pone00:0098372 is not listed on IDEAS
    2. Hao Leng & Yinzhao Wang & Weishu Zhao & Stefan M. Sievert & Xiang Xiao, 2023. "Identification of a deep-branching thermophilic clade sheds light on early bacterial evolution," Nature Communications, Nature, vol. 14(1), pages 1-14, December.
    3. Ambros M. Gleixner & Daniel E. Steffy & Kati Wolter, 2016. "Iterative Refinement for Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 449-464, August.
    4. Serap Tekbaş & Nevin Hotun Şahin & Niyazi Cenk Sayın, 2022. "The Effect of Treatment on Quality of Life, Symptoms, and Social Life in Gynecologic Cancer Patients," Clinical Nursing Research, , vol. 31(6), pages 1063-1071, July.
    5. Josef Kallrath, 2025. "Large-Number Optimization: Exact-Arithmetic Mathematical Programming with Integers and Fractions Beyond Any Bit Limits," Mathematics, MDPI, vol. 13(19), pages 1-40, October.
    6. Mohammadhossein Mohammadisiahroudi & Ramin Fakhimi & Tamás Terlaky, 2024. "Efficient Use of Quantum Linear System Algorithms in Inexact Infeasible IPMs for Linear Optimization," Journal of Optimization Theory and Applications, Springer, vol. 202(1), pages 146-183, July.
    7. Alexander Kroll & Yvan Rousset & Xiao-Pan Hu & Nina A. Liebrand & Martin J. Lercher, 2023. "Turnover number predictions for kinetically uncharacterized enzymes using machine and deep learning," Nature Communications, Nature, vol. 14(1), pages 1-14, December.
    8. Iván Domenzain & Benjamín Sánchez & Mihail Anton & Eduard J. Kerkhoven & Aarón Millán-Oropeza & Céline Henry & Verena Siewers & John P. Morrissey & Nikolaus Sonnenschein & Jens Nielsen, 2022. "Reconstruction of a catalogue of genome-scale metabolic models with enzymatic constraints using GECKO 2.0," Nature Communications, Nature, vol. 13(1), pages 1-13, December.
    9. Christian Schulz & Tjasa Kumelj & Emil Karlsen & Eivind Almaas, 2021. "Genome-scale metabolic modelling when changes in environmental conditions affect biomass composition," PLOS Computational Biology, Public Library of Science, vol. 17(5), pages 1-22, May.
    10. Robert Planqué & Josephus Hulshof & Bas Teusink & Johannes C Hendriks & Frank J Bruggeman, 2018. "Maintaining maximal metabolic flux by gene expression control," PLOS Computational Biology, Public Library of Science, vol. 14(9), pages 1-20, September.
    11. Guido Zampieri & Supreeta Vijayakumar & Elisabeth Yaneske & Claudio Angione, 2019. "Machine and deep learning meet genome-scale metabolic modeling," PLOS Computational Biology, Public Library of Science, vol. 15(7), pages 1-24, July.
    12. Philipp Wendering & Marius Arend & Zahra Razaghi-Moghadam & Zoran Nikoloski, 2023. "Data integration across conditions improves turnover number estimates and metabolic predictions," Nature Communications, Nature, vol. 14(1), pages 1-12, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:37:y:2025:i:4:p:933-944. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.