{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:35:40Z","timestamp":1787340940101,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"German Federal Ministry of Education and Research"},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M14ZAM"],"award-info":[{"award-number":["05M14ZAM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M20ZBM"],"award-info":[{"award-number":["05M20ZBM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009 [ INFORMS J. Comput., 21 (2009), pp. 641\u2013649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances to exact optimality and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set.<\/jats:p>","DOI":"10.1137\/23m156046x","type":"journal-article","created":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T04:01:20Z","timestamp":1708056080000},"page":"742-763","source":"Crossref","is-referenced-by-count":5,"title":["Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework"],"prefix":"10.1137","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0245-9344","authenticated-orcid":true,"given":"Leon","family":"Eifler","sequence":"first","affiliation":[{"name":"Zuse Institute Berlin, 14195 Berlin, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ambros","family":"Gleixner","sequence":"additional","affiliation":[{"name":"Zuse Institute Berlin, 14195 Berlin, Germany, and HTW Berlin, 10318 Berlin, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,2,16]]},"reference":[{"key":"ref1","unstructured":"T. Achterberg, Constraint Integer Programming, Ph.D. thesis, Technische Universit\u00e4t Berlin, 2007."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38189-8_18"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.09.006"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"J. Berg, B. Bogaerts, J. Nordstr\u00f6m, A. Oertel, and D. Vandesande, Certified core-guided MaxSAT solving, in Proceedings of the 29th International Conference on Automated Deduction, 2023.","DOI":"10.1007\/978-3-031-38499-8_1"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-018-3365-9"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"B. Bogaerts, S. Gocht, C. McCreesh, and J. Nordstr\u00f6m, Certified symmetry and dominance breaking for combinatorial optimisation, Proceedings of the 36th AAAI Conference on Artificial Intelligence, 2022, pp. 3698\u20133707, https:\/\/doi.org\/10.1609\/aaai.v36i4.20283.","DOI":"10.1609\/aaai.v36i4.20283"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/2382585.2382589"},{"key":"ref8","unstructured":"K. Cheung, A. Gleixner, and D. Steffy, Verifying Integer Programming Results, https:\/\/github.com\/ambros-gleixner\/VIPR."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_13"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11008-0"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0324"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-013-0055-6"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01749-5"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3485630"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"J. Elffers, S. Gocht, C. McCreesh, and J. Nordstr\u00f6m, Justifying all differences using pseudo-boolean reasoning, Proceedings of the 34th AAAI Conference on Artificial Intelligence, 2020, pp. 1486\u20131494, https:\/\/doi.org\/10.1609\/aaai.v34i02.5507.","DOI":"10.1609\/aaai.v34i02.5507"},{"key":"ref16","unstructured":"D. G. Espinoza, On Linear Programming, Integer Programming and Cutting Planes, Ph.D. thesis, Georgia Institute of Technology, 2006."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-020-00194-3"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01444-6"},{"key":"ref19","unstructured":"S. Gocht, VeriPB, 2019, https:\/\/doi.org\/10.5281\/zenodo.3548582."},{"key":"ref20","volume-title":"GNU MP 6.0 Multiple Precision Arithmetic Library","author":"Granlund T.","year":"2015"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.11.1.117"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2013.6679408"},{"key":"ref23","unstructured":"A. Hoen and L. Gottwald, scipopt\/papilo: v2.0.0, 2022, https:\/\/doi.org\/10.5281\/zenodo.6414882."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04651-4_46"},{"key":"ref25","volume-title":"Continued Fractions","author":"Khinchin A. Y."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9218-7"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-49988-4_5"},{"key":"ref28","volume-title":"Introduction to Diophantine Approximations","author":"Lang S.","year":"1966"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.12.005"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.3.363.11211"},{"key":"ref31","unstructured":"M. Miltenberger, A. Gleixner, T. Koch, M. Pfetsch, A. Hoen, T. Achterberg, F. Schl\u00f6sser, S. Vigerske, D. Rehfeldt, micwinx, G. Hendel, J. Witzig, M. Besan\u00e7on, D. Steffy, bzfberth, G. gamrath, L. Gottwald, fserra, P. Wellner, A. Ebrahim, H. Mulackal, and J. Nicolas-Thouvenin, scipopt\/soplex: v6.0.0, 2022, https:\/\/doi.org\/10.5281\/zenodo.6414886."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0433-3"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718072"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3461"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.energy.2017.11.064"},{"key":"ref36","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","year":"1986"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1120.0501"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09284-3_31"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/358438.349318"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M156046X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:57:11Z","timestamp":1787338631000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M156046X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,16]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/23M156046X"],"URL":"https:\/\/doi.org\/10.1137\/23m156046x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,16]]}}}