{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:48:55Z","timestamp":1776106135909,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004937","name":"Bundesministerium f\u00fcr Forschung und Technologie","doi-asserted-by":"publisher","award":["05M14ZAM"],"award-info":[{"award-number":["05M14ZAM"]}],"id":[{"id":"10.13039\/501100004937","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004937","name":"Bundesministerium f\u00fcr Forschung und Technologie","doi-asserted-by":"publisher","award":["05M20ZBM"],"award-info":[{"award-number":["05M20ZBM"]}],"id":[{"id":"10.13039\/501100004937","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB\u00a02017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours.\n<\/jats:p>","DOI":"10.1007\/s10107-021-01749-5","type":"journal-article","created":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T12:04:09Z","timestamp":1641557049000},"page":"793-812","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["A computational status update for exact rational mixed integer programming"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0245-9344","authenticated-orcid":false,"given":"Leon","family":"Eifler","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0391-5903","authenticated-orcid":false,"given":"Ambros","family":"Gleixner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,7]]},"reference":[{"key":"1749_CR1","unstructured":"Achterberg, T.: Constraint Integer Programming. Ph.D. thesis, Technische Universit\u00e4t Berlin (2007)"},{"issue":"2","key":"1749_CR2","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1287\/ijoc.2018.0857","volume":"32","author":"T Achterberg","year":"2020","unstructured":"Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E., Weninger, D.: Presolve reductions in mixed integer programming. Inform. J. Comput. 32(2), 473\u2013506 (2020). https:\/\/doi.org\/10.1287\/ijoc.2018.0857","journal-title":"Inform. J. Comput."},{"issue":"1","key":"1749_CR3","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T Achterberg","year":"2005","unstructured":"Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Op. Res. Lett. 33(1), 42\u201354 (2005). https:\/\/doi.org\/10.1016\/j.orl.2004.04.002","journal-title":"Op. Res. Lett."},{"key":"1749_CR4","doi-asserted-by":"publisher","unstructured":"Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: J\u00fcnger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization. pp. 449\u2013481 (2013). https:\/\/doi.org\/10.1007\/978-3-642-38189-8_18","DOI":"10.1007\/978-3-642-38189-8_18"},{"key":"1749_CR5","unstructured":"Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Concorde TSP Solver (2006)"},{"issue":"6","key":"1749_CR6","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.orl.2006.12.010","volume":"35","author":"D Applegate","year":"2007","unstructured":"Applegate, D., Cook, W., Dash, S., Espinoza, D.G.: Exact solutions to linear programming problems. Op. Res. Lett. 35(6), 693\u2013699 (2007). https:\/\/doi.org\/10.1016\/j.orl.2006.12.010","journal-title":"Op. Res. Lett."},{"issue":"1","key":"1749_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-016-0104-z","volume":"9","author":"B Assarf","year":"2017","unstructured":"Assarf, B., Gawrilow, E., Herr, K., Joswig, M., Lorenz, B., Paffenholz, A., Rehn, T.: Computing convex hulls and counting integer points with polymake. Math. Program. Comput. 9(1), 1\u201338 (2017). https:\/\/doi.org\/10.1007\/s12532-016-0104-z","journal-title":"Math. Program. Comput."},{"issue":"1\u20132","key":"1749_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.scico.2007.08.001","volume":"72","author":"R Bagnara","year":"2008","unstructured":"Bagnara, R., Hill, P.M., Zaffanella, E.: The parma polyhedra library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Sci. Comput. Program. 72(1\u20132), 3\u201321 (2008)","journal-title":"Sci. Comput. Program."},{"issue":"6","key":"1749_CR9","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1016\/j.orl.2013.08.007","volume":"41","author":"T Berthold","year":"2013","unstructured":"Berthold, T.: Measuring the impact of primal heuristics. Op. Res. Lett. 41(6), 611\u2013614 (2013). https:\/\/doi.org\/10.1016\/j.orl.2013.08.007","journal-title":"Op. Res. Lett."},{"key":"1749_CR10","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T.: Handbook of satisfiability: volume 185 frontiers in artificial intelligence and applications. IOS Press, NLD (2009)"},{"key":"1749_CR11","doi-asserted-by":"publisher","first-page":"2187","DOI":"10.1007\/s00500-018-3365-9","volume":"23","author":"M Bofill","year":"2019","unstructured":"Bofill, M., Many\u00e0, F., Vidal, A., Villaret, M.: New complexity results for \u0141ukasiewicz logic. Soft Comput. 23, 2187\u20132197 (2019). https:\/\/doi.org\/10.1007\/s00500-018-3365-9","journal-title":"Soft Comput."},{"key":"1749_CR12","doi-asserted-by":"publisher","DOI":"10.1145\/2382585.2382589","author":"BA Burton","year":"2012","unstructured":"Burton, B.A., Ozlen, M.: Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Trans. Math. Softw. (2012). https:\/\/doi.org\/10.1145\/2382585.2382589","journal-title":"ACM Trans. Math. Softw."},{"key":"1749_CR13","doi-asserted-by":"publisher","unstructured":"Cheung, K.K., Gleixner, A., Steffy, D.E.: Verifying Integer Programming Results. In: International Conference on Integer Programming and Combinatorial Optimization. pp. 148\u2013160. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-59250-3_13","DOI":"10.1007\/978-3-319-59250-3_13"},{"key":"1749_CR14","unstructured":"Cheung, K., Gleixner, A., Steffy, D.: VIPR. Verifying Integer Programming Results. https:\/\/github.com\/ambros-gleixner\/VIPR (accessed May 31, 2021)"},{"key":"1749_CR15","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1287\/ijoc.1090.0324","volume":"21","author":"W Cook","year":"2009","unstructured":"Cook, W., Dash, S., Fukasawa, R., Goycoolea, M.: Numerically safe gomory mixed-integer cuts. Inform. J. Comput. 21, 641\u2013649 (2009). https:\/\/doi.org\/10.1287\/ijoc.1090.0324","journal-title":"Inform. J. Comput."},{"issue":"3","key":"1749_CR16","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s12532-013-0055-6","volume":"5","author":"W Cook","year":"2013","unstructured":"Cook, W., Koch, T., Steffy, D.E., Wolter, K.: A hybrid branch-and-bound approach for exact rational mixed-integer programming. Math. Program. Comput. 5(3), 305\u2013344 (2013). https:\/\/doi.org\/10.1007\/s12532-013-0055-6","journal-title":"Math. Program. Comput."},{"key":"1749_CR17","unstructured":"Eifler, L., Gleixner, A.: Exact SCIP - a development version. https:\/\/github.com\/leoneifler\/exact-SCIP (accessed May 31, 2021)"},{"key":"1749_CR18","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-030-73879-2_12","volume-title":"Integer Programming and Combinatorial Optimization","author":"L Eifler","year":"2021","unstructured":"Eifler, L., Gleixner, A.: A computational status update for exact rational mixed integer programming. In: Singh, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, pp. 163\u2013177. Springer International Publishing, Cham (2021)"},{"key":"1749_CR19","unstructured":"Eifler, L., Gleixner, A., Pulaj, J.: A safe computational framework for integer programming applied to Chv\u00e1tal\u2019s conjecture (2020)"},{"key":"1749_CR20","unstructured":"Espinoza, D.G.: On Linear Programming, Integer Programming and Cutting Planes. Ph.D. thesis, Georgia Institute of Technology (2006)"},{"key":"1749_CR21","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-540-79719-7_8","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2008","author":"G Faure","year":"2008","unstructured":"Faure, G., Nieuwenhuis, R., Oliveras, A., Rodr\u00edguez-Carbonell, E.: SAT Modulo the Theory of Linear Arithmetic: Exact, Inexact and Commercial Solvers. In: Kleine B\u00fcning, H., Zhao, X. (eds.) Theory and Applications of Satisfiability Testing - SAT 2008, pp. 77\u201390. Springer, Berlin Heidelberg, Berlin, Heidelberg (2008)"},{"key":"1749_CR22","unstructured":"Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Bodic, P.L., Maher, S.J., Matter, F., Miltenberger, M., M\u00fchmer, E., M\u00fcller, B., Pfetsch, M., Schl\u00f6sser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin (2020)"},{"key":"1749_CR23","unstructured":"Gleixner, A., Gottwald, L., Hoen, A.: PaPILO: Parallel Presolve for Integer and Linear Optimization. https:\/\/github.com\/scipopt\/papilo (accessed May 28, 2021)"},{"key":"1749_CR24","doi-asserted-by":"crossref","unstructured":"Gleixner, A., Hendel, G., Gamrath, G., Achterberg, T., Bastubbe, M., Berthold, T., Christophel, P.M., Jarck, K., Koch, T., Linderoth, J., L\u00fcbbecke, M., Mittelmann, H.D., Ozyurt, D., Ralphs, T.K., Salvagnin, D., Shinano, Y.: MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Mathematical Programming Computation (2020), accepted for publication","DOI":"10.1007\/s12532-020-00194-3"},{"key":"1749_CR25","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10107-019-01444-6","volume":"183","author":"A Gleixner","year":"2020","unstructured":"Gleixner, A., Steffy, D.E.: Linear programming using limited-precision oracles. Math. Program. 183, 525\u2013554 (2020). https:\/\/doi.org\/10.1007\/s10107-019-01444-6","journal-title":"Math. Program."},{"issue":"3","key":"1749_CR26","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1287\/ijoc.2016.0692","volume":"28","author":"A Gleixner","year":"2016","unstructured":"Gleixner, A., Steffy, D.E., Wolter, K.: Iterative refinement for linear programming. Informs. J. Comput. 28(3), 449\u2013464 (2016). https:\/\/doi.org\/10.1287\/ijoc.2016.0692","journal-title":"Informs. J. Comput."},{"key":"1749_CR27","unstructured":"Granlund, T., Team, G.D.: GNU MP 6.0 Multiple Precision Arithmetic Library. Samurai Media Limited, London, GBR (2015)"},{"key":"1749_CR28","doi-asserted-by":"publisher","unstructured":"Higham, N.J.: Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, second edn. (2002). https:\/\/doi.org\/10.1137\/1.9780898718027","DOI":"10.1137\/1.9780898718027"},{"key":"1749_CR29","doi-asserted-by":"publisher","unstructured":"Kenter, F., Skipper, D.: Integer-programming bounds on pebbling numbers of cartesian-product graphs. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) Combinatorial Optimization and Applications. pp. 681\u2013695 (2018). https:\/\/doi.org\/10.1007\/978-3-030-04651-4_46","DOI":"10.1007\/978-3-030-04651-4_46"},{"key":"1749_CR30","doi-asserted-by":"publisher","unstructured":"Lancia, G., Pippia, E., Rinaldi, F.: Using integer programming to search for counterexamples: A case study. In: Kononov, A., Khachay, M., Kalyagin, V.A., Pardalos, P. (eds.) Mathematical Optimization Theory and Operations Research. pp. 69\u201384 (2020). https:\/\/doi.org\/10.1007\/978-3-030-49988-4","DOI":"10.1007\/978-3-030-49988-4"},{"key":"1749_CR31","doi-asserted-by":"publisher","unstructured":"de\u00a0Moura, L., Bj\u00f8rner, N.: Z3: An Efficient SMT Solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. pp. 337\u2013340 (2008). https:\/\/doi.org\/10.1007\/978-3-540-78800-3_24","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"1749_CR32","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10107-003-0433-3","volume":"99","author":"A Neumaier","year":"2002","unstructured":"Neumaier, A., Shcherbina, O.: Safe bounds in linear and mixed-integer programming. Math. Program. 99, 283\u2013296 (2002). https:\/\/doi.org\/10.1007\/s10107-003-0433-3","journal-title":"Math. Program."},{"issue":"322","key":"1749_CR33","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1090\/mcom\/3461","volume":"89","author":"J Pulaj","year":"2020","unstructured":"Pulaj, J.: Cutting planes for families implying Frankl\u2019s conjecture. Math. Comput. 89(322), 829\u2013857 (2020). https:\/\/doi.org\/10.1090\/mcom\/3461","journal-title":"Math. Comput."},{"issue":"2","key":"1749_CR34","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1287\/ijoc.1120.0501","volume":"25","author":"DE Steffy","year":"2013","unstructured":"Steffy, D.E., Wolter, K.: Valid linear programming bounds for exact mixed-integer programming. Inform. J. Comput. 25(2), 271\u2013284 (2013). https:\/\/doi.org\/10.1287\/ijoc.1120.0501","journal-title":"Inform. J. Comput."},{"key":"1749_CR35","doi-asserted-by":"publisher","unstructured":"Wetzler, N., Heule, M.J.H., Hunt, W.A.: DRAT-trim: Efficient checking and trimming using expressive clausal proofs. In: Sinz, C., Egly, U. (eds.) Theory and Applications of Satisfiability Testing \u2013 SAT 2014. pp. 422\u2013429 (2014). https:\/\/doi.org\/10.1007\/978-3-319-09284-3_31","DOI":"10.1007\/978-3-319-09284-3_31"},{"issue":"5","key":"1749_CR36","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/358438.349318","volume":"35","author":"K Wilken","year":"2000","unstructured":"Wilken, K., Liu, J., Heffernan, M.: Optimal instruction scheduling using integer programming. SIGPLAN Not. 35(5), 121\u2013133 (2000). https:\/\/doi.org\/10.1145\/358438.349318","journal-title":"SIGPLAN Not."},{"key":"1749_CR37","unstructured":"Wolter, K.: Exact Mixed-Integer Programming. Ph.D. thesis, Technische Universit\u00e4t Berlin (2019)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01749-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01749-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01749-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:18:04Z","timestamp":1675703884000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01749-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,7]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1749"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01749-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,7]]},"assertion":[{"value":"31 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}