Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization

References

• Applegate D, Cook W, Dash S, Espinoza DG (2007) Exact solutions to linear programming problems. Oper. Res. Lett. 35(6):693–699.Crossref, Google Scholar
• Bofill M, Manyà F, Vidal A, Villaret M (2019) New complexity results for Łukasiewicz logic. Soft Comput. 23:2187–2197.Crossref, Google Scholar
• Burton BA, Ozlen M (2012) Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Trans. Math. Software 39(1):1–18.Crossref, Google Scholar
• Cook W, Koch T, Steffy DE, Wolter K (2013) A hybrid branch-and-bound approach for exact rational mixed-integer programming. Math. Prog. Comput. 5(3):305–344.Crossref, Google Scholar
• Dhiflaoui M, Funke S, Kwappik C, Mehlhorn K, Seel M, Schömer E, Schulte R, Weber D (2003) Certifying and repairing solutions to large LPs how good are LP-solvers? Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA ‘03) (Society for Industrial and Applied Mathematics, Philadelphia), 255–256.Google Scholar
• Eifler L, Gleixner A (2023) A computational status update for exact rational mixed integer programming. Math. Prog. 197:793–812.Crossref, Google Scholar
• Eifler L, Gleixner A (2024) Safe and verified Gomory mixed integer cuts in a rational MIP framework. SIAM J. Optim. 34(1):742–763.Crossref, Google Scholar
• Eifler L, Gleixner A, Pulaj J (2022) A safe computational framework for integer programming applied to Chvátal’s conjecture. ACM Trans. Math. Software 48(2):1–12.Crossref, Google Scholar
• Espinoza DG (2006) On linear programming, integer programming and cutting planes. Unpublished PhD thesis, Georgia Institute of Technology, Atlanta.Google Scholar
• Fousse L, Hanrot G, Lefèvre V, Pélissier P, Zimmermann P (2007) MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Trans. Math. Software 33(2):13-es.Crossref, Google Scholar
• Gleixner A, Steffy DE (2020) Linear programming using limited-precision oracles. Math. Prog. 183:525–554.Crossref, Google Scholar
• Gleixner A, Gottwald L, Hoen A (2023) PaPILO: A parallel presolving library for integer and linear optimization with multiprecision support. INFORMS J. Comput. 35(6):1329–1341.Google Scholar
• Gleixner A, Steffy DE, Wolter K (2016) Iterative refinement for linear programming. INFORMS J. Comput. 28(3):449–464.Link, Google Scholar
• Granlund T, Team GD (2015) GNU MP 6.0 Multiple Precision Arithmetic Library (Samurai Media Limited, London).Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• Hales T, Adams M, Bauer G, Dang TD, Harrison J, Hoang LT, Kaliszyk C, et al. (2017) A formal proof of the Kepler conjecture. Forum Math. Pi 5:e2.Crossref, Google Scholar
• Kenter F, Skipper D (2018) Integer-programming bounds on pebbling numbers of Cartesian-product graphs. Kim D, Uma RN, Zelikovsky A, eds. Combin. Optim. Appl. COCOA 2018, Lecture Notes in Computer Science, vol. 11346 (Springer, Cham, Switzerland), 681–695.Google Scholar
• Khachiyan L (1980) Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20(1):53–72.Crossref, Google Scholar
• Lancia G, Pippia E, Rinaldi F (2020) Using integer programming to search for counterexamples: A case study. Kononov A, Khachay M, Kalyagin VA, Pardalos P, eds. Math. Optim. Theory Oper. Res. MOTOR 2020, Lecture Notes in Computer Science, vol. 12095 (Springer, Cham, Switzerland), 69–84.Google Scholar
• Lerman JA, Hyduke DR, Latif H, Portnoy VA, Lewis NE, Orth JD, Schrimpe-Rutledge AC, et al. (2012) In silico method for modelling metabolism and gene product expression at genome scale. Nature Comm. 3(1):929.Crossref, Google Scholar
• Lourenco CJ, Chen J, Moreno-Centeno E, Davis TA (2022) Algorithm 1021: SPEX Left LU, exactly solving sparse linear systems via a sparse left-looking integer-preserving LU factorization. ACM Trans. Math. Software 48(2):1–23.Crossref, Google Scholar
• Lourenco C, Escobedo AR, Moreno-Centeno E, Davis TA (2019) Exact solution of sparse linear systems via left-looking roundoff-error-free LU factorization in time proportional to arithmetic work. SIAM J. Matrix Anal. Appl. 40(2):609–638.Crossref, Google Scholar
• Pulaj J (2020) Cutting planes for families implying Frankl’s conjecture. Math. Comput. 89(322):829–857.Crossref, Google Scholar
• Saunders BD, Wood DH, Youse BS (2011) Numeric-symbolic exact rational linear system solver. ISSAC ‘11. Proc. 36th Internat. Sympos. Symbolic Algebraic Comput. (ACM, New York), 305–312.Google Scholar
• Wan Z (2006) An algorithm to solve integer linear systems exactly using numerical methods. J. Symbolic Comput. 41(6):621–632.Crossref, Google Scholar
• Wilkinson JH (1994) Rounding Errors in Algebraic Processes (Dover Publications, Inc., New York).Google Scholar