{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T13:02:34Z","timestamp":1779800554315,"version":"3.53.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T00:00:00Z","timestamp":1775779200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T00:00:00Z","timestamp":1775779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Linear optimization solvers commonly employ presolve techniques to simplify and improve the solution characteristics of models before a simplex or interior point algorithm is used for solution. The Fourier-Motzkin elimination, a well-known mathematical algorithm for removing columns from linear inequality systems, has not been utilized as a presolve method in existing solvers due to its exponential row growth. We propose a novel presolve method based on the Fourier-Motzkin elimination, along with postsolve algorithms to recover the primal and dual optimal solutions. The algorithm controls row growth by judiciously selecting which columns to eliminate after computing an upper bound on model size prior to each variable elimination step. Our computational results demonstrate that the proposed presolve with Fourier-Motzkin elimination effectively reduces the number of rows, columns, and nonzero elements in general linear optimization problems. As a result, the algorithm reduces the total number of iterations of simplex methods in CPLEX. Additionally, when combined with the CPLEX presolve, our FME implementation leads to models smaller than those obtained by CPLEX presolve alone, leading to speed-ups for CPLEX\u2019s primal simplex, dual simplex, and barrier methods.<\/jats:p>","DOI":"10.1007\/s12532-026-00316-3","type":"journal-article","created":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:21:28Z","timestamp":1775816488000},"page":"345-378","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A novel linear optimization presolve technique based on Fourier-Motzkin elimination"],"prefix":"10.1007","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0249-0547","authenticated-orcid":false,"given":"Yi","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5876-9945","authenticated-orcid":false,"given":"Nikolaos","family":"Ploskas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2087-9131","authenticated-orcid":false,"given":"Nikolaos V.","family":"Sahinidis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,10]]},"reference":[{"key":"316_CR1","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. INFORMS J. Comput. 32, 473\u2013506 (2020)","journal-title":"INFORMS J. Comput."},{"key":"316_CR2","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1080\/10556789508805634","volume":"6","author":"ED Andersen","year":"1995","unstructured":"Andersen, E.D.: Finding all linearly dependent rows in large-scale linear programming. Optimization Methods and Software 6, 219\u2013227 (1995)","journal-title":"Optimization Methods and Software"},{"key":"316_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF01586000","volume":"71","author":"ED Andersen","year":"1995","unstructured":"Andersen, E.D., Andersen, K.D.: Presolving in linear programming. Math. Program. 71, 221\u2013245 (1995)","journal-title":"Math. Program."},{"key":"316_CR4","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/197405.197406","volume":"26","author":"DF Bacon","year":"1994","unstructured":"Bacon, D.F., Graham, S.L., Sharp, O.J.: Compiler transformations for high-performance computing. ACM Comput. Surv. 26, 345\u2013420 (1994)","journal-title":"ACM Comput. Surv."},{"key":"316_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1023\/A:1018368920203","volume":"10","author":"E Balas","year":"1998","unstructured":"Balas, E.: Projection with a minimal system of inequalities. Comput. Optim. Appl. 10, 189\u2013193 (1998)","journal-title":"Comput. Optim. Appl."},{"key":"316_CR6","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1080\/10556788.2020.1712600","volume":"36","author":"SI Bastrakov","year":"2021","unstructured":"Bastrakov, S.I., Churkin, A.V., Zolotykh, N.Y.: Accelerating fourier-motzkin elimination using bit pattern trees. Optimization Methods and Software 36, 1082\u20131095 (2021)","journal-title":"Optimization Methods and Software"},{"key":"316_CR7","first-page":"383","volume":"10","author":"K Bestuzheva","year":"2023","unstructured":"Bestuzheva, K., Chmiela, A., M\u00fcller, B., Serrano, F., Vigerske, S., Wegscheider, F.: Global optimization of mixed-integer nonlinear programs with SCIP 8. J. Global Optim. 10, 383\u2013421 (2023)","journal-title":"J. Global Optim."},{"key":"316_CR8","unstructured":"Bik, A.J., Wijshoff, H.A.: Implementation of fourier-motzkin elimination. Citeseer, (1994)"},{"key":"316_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10479-006-0091-y","volume":"149","author":"R Bixby","year":"2007","unstructured":"Bixby, R., Rothberg, E.: Progress in computational mixed integer programming\u2013A look back from the other side of the tipping point. Ann. Oper. Res. 149, 37\u201341 (2007)","journal-title":"Ann. Oper. Res."},{"key":"316_CR10","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/BF01580428","volume":"8","author":"AL Brearley","year":"1975","unstructured":"Brearley, A.L., Mitra, G., Williams, H.P.: Analysis of mathematical programming problems prior to applying the simplex algorithm. Math. Program. 8, 54\u201383 (1975)","journal-title":"Math. Program."},{"key":"316_CR11","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1287\/ijoc.15.1.114.15159","volume":"15","author":"MR Bussieck","year":"2003","unstructured":"Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib-A collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15, 114\u2013119 (2003)","journal-title":"INFORMS J. Comput."},{"key":"316_CR12","unstructured":"Cernikov, S.N.: Contraction of finite systems of linear inequalities. In Doklady Akademii Nauk, volume 152, pages 1075\u20131078. Russian Academy of Sciences, (1963)"},{"key":"316_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1093\/comjnl\/36.5.463","volume":"36","author":"V Chandru","year":"1993","unstructured":"Chandru, V.: Variable elimination in linear constraints. Comput. J. 36, 463\u2013472 (1993)","journal-title":"Comput. J."},{"key":"316_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.2307\/1905523","volume":"17","author":"GB Dantzig","year":"1949","unstructured":"Dantzig, G.B.: Programming in a linear structure. Econometrica 17, 73\u201374 (1949)","journal-title":"Econometrica"},{"key":"316_CR15","doi-asserted-by":"publisher","DOI":"10.7249\/R366","volume-title":"Linear Programming and Extensions","author":"GB Dantzig","year":"1963","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963)"},{"key":"316_CR16","doi-asserted-by":"crossref","unstructured":"Dines, L.L.: Systems of linear inequalities. Annals of Mathematics, pages 191\u2013199, (1919)","DOI":"10.2307\/1967869"},{"key":"316_CR17","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201\u2013213 (2002)","journal-title":"Math. Program."},{"key":"316_CR18","doi-asserted-by":"crossref","unstructured":"Duffin, R.J.: On Fourier\u2019s analysis of linear inequality systems. In Pivoting and Extension, pages 71\u201395. Springer, (1974)","DOI":"10.1007\/BFb0121242"},{"key":"316_CR19","unstructured":"Elble, J.M.: Computational experience with linear optimization and related problems. PhD thesis, University of Illinois at Urbana-Champaign, (2010)"},{"key":"316_CR20","first-page":"100","volume":"99","author":"JBJ Fourier","year":"1826","unstructured":"Fourier, J.B.J.: Solution d\u2019une question particuliere du calcul des in\u00e9galit\u00e9s. Nouveau Bulletin des Sciences par la Soci\u00e9t\u00e9 philomatique de Paris 99, 100 (1826)","journal-title":"Nouveau Bulletin des Sciences par la Soci\u00e9t\u00e9 philomatique de Paris"},{"key":"316_CR21","unstructured":"Gattegno, I.B., Goldfeld, Z., Permuter, H.H.: Fourier-Motzkin elimination software for information theoretic inequalities, (2016). arXiv preprint arXiv:1610.03990"},{"key":"316_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/ijoc.9.1.73","volume":"9","author":"J Gondzio","year":"1997","unstructured":"Gondzio, J.: Presolve analysis of linear programs prior to applying an interior point method. INFORMS J. Comput. 9, 73\u201391 (1997)","journal-title":"INFORMS J. Comput."},{"key":"316_CR23","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10107-003-0487-2","volume":"100","author":"N Gould","year":"2004","unstructured":"Gould, N., Toint, P.L.: Preprocessing for quadratic programming. Math. Program. 100, 95\u2013132 (2004)","journal-title":"Math. Program."},{"key":"316_CR24","unstructured":"Gurobi Optimization, LLC. Gurobi optimizer reference manual, (2023)"},{"key":"316_CR25","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF01100238","volume":"3","author":"ASE Hamed","year":"1993","unstructured":"Hamed, A.S.E., McCormick, G.P.: Calculation of bounds on variables satisfying nonlinear inequality constraints. J. Global Optim. 3, 25\u201347 (1993)","journal-title":"J. Global Optim."},{"key":"316_CR26","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"DS Hochbaum","year":"1994","unstructured":"Hochbaum, D.S., Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23, 1179\u20131192 (1994)","journal-title":"SIAM J. Comput."},{"key":"316_CR27","unstructured":"Huang, X.: Preprocessing and postprocessing in linear optimization. Technical report, McMaster University, (2004)"},{"key":"316_CR28","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01535523","volume":"6","author":"T Huynh","year":"1992","unstructured":"Huynh, T., Lassez, C., Lassez, J.: Practical issues on the projection of polyhedral sets. Ann. Math. Artif. Intell. 6, 295\u2013315 (1992)","journal-title":"Ann. Math. Artif. Intell."},{"key":"316_CR29","unstructured":"IBM. CPLEX Optimizer, (2016). http:\/\/www-01.ibm.com\/software\/integration\/optimization\/cplex-optimizer\/"},{"key":"316_CR30","unstructured":"ILOG. ILOG CPLEX Optimization Studio 22.1.1 - User\u2019s Manual for CPLEX. IBM Corporation, https:\/\/www.ibm.com\/docs\/en\/icos\/22.1.1?topic=optimizers-users-manual-cplex, (2022)"},{"key":"316_CR31","unstructured":"Imbert, J.L.: Fourier\u2019s elimination: Which to Choose? In Principles and Practice of Constraint Programming, PPCP 1993, Newport, Rhode Island, pages 117\u2013129, (1993)"},{"key":"316_CR32","doi-asserted-by":"crossref","unstructured":"Jing, R., Moreno-Maza, M., Talaashrafi, D.: Complexity estimates for Fourier-Motzkin elimination. In Computer Algebra in Scientific Computing: 22nd International Workshop, CASC 2020, Linz, Austria, September 14\u201318, 2020, Proceedings 22, pages 282\u2013306. Springer, (2020)","DOI":"10.1007\/978-3-030-60026-6_16"},{"key":"316_CR33","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF03398538","volume":"35","author":"P Kanniappan","year":"1998","unstructured":"Kanniappan, P., Thangavel, K.: Modified Fourier\u2019s method of solving linear programming problems. Opsearch 35, 45\u201356 (1998)","journal-title":"Opsearch"},{"key":"316_CR34","doi-asserted-by":"crossref","unstructured":"Kohler, D.A.: Projections of convex polyhedral sets. Technical report, Operations research center, California university of Berkeley, (1967)","DOI":"10.21236\/AD0659301"},{"key":"316_CR35","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF00245296","volume":"9","author":"J Lassez","year":"1992","unstructured":"Lassez, J., Maher, M.J.: On Fourier\u2019s algorithm for linear arithmetic constraints. J. Autom. Reason. 9, 373\u2013379 (1992)","journal-title":"J. Autom. Reason."},{"key":"316_CR36","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s00291-003-0130-x","volume":"25","author":"C M\u00e9sz\u00e1ros","year":"2003","unstructured":"M\u00e9sz\u00e1ros, C., Suhl, U.H.: Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum 25, 575\u2013595 (2003)","journal-title":"OR Spectrum"},{"key":"316_CR37","unstructured":"MESZAROSLIB. https:\/\/sparse.tamu.edu\/Meszaros"},{"key":"316_CR38","unstructured":"MITTELMANNLIB. http:\/\/plato.asu.edu\/ftp\/lptestset\/"},{"key":"316_CR39","unstructured":"Nelson, C.G.: An $$n^{logn}$$ algorithm for the two-variable-per-constraint linear programming satisfiability problem, (1978)"},{"key":"316_CR40","unstructured":"NETLIB. http:\/\/www.netlib.org\/lp\/data\/"},{"key":"316_CR41","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/s10601-016-9267-5","volume":"22","author":"Y Puranik","year":"2017","unstructured":"Puranik, Y., Sahinidis, N.V.: Domain reduction techniques for global NLP and MINLP optimization. Constraints 22, 338\u2013376 (2017)","journal-title":"Constraints"},{"key":"316_CR42","unstructured":"Schultz, R.: A note on preprocessing via Fourier-Motzkin elimination in two-stage stochastic programming. In Stochastic Programming Methods and Technical Applications: Proceedings of the 3rd GAMM\/IFIP-Workshop on \u201cStochastic Optimization: Numerical Methods and Technical Applications\u201d held at the Federal Armed Forces University Munich, Neubiberg\/M\u00fcnchen, Germany, June 17\u201320, 1996, pages 208\u2013222. Springer, (1998)"},{"key":"316_CR43","unstructured":"The Optimization Firm, LLC. MINLPrlpLib collection of LP test problems. https:\/\/minlp.com\/optimization-test-problems"},{"key":"316_CR44","doi-asserted-by":"crossref","unstructured":"Tomlin, J.A., Welch, J.S.: Formal optimization of some reduced linear programming problems. Mathematical Programming, 27:232\u2013240, (1983)","DOI":"10.1007\/BF02591947"},{"key":"316_CR45","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1080\/00029890.1986.11971923","volume":"93","author":"HP Williams","year":"1986","unstructured":"Williams, H.P.: Fourier\u2019s method of linear programming and its dual. Am. Math. Mon. 93, 681\u2013695 (1986)","journal-title":"Am. Math. Mon."},{"key":"316_CR46","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF00940732","volume":"63","author":"Y Ye","year":"1989","unstructured":"Ye, Y.: Eliminating columns in the simplex method for linear programming. J. Optim. Theory Appl. 63, 69\u201377 (1989)","journal-title":"J. Optim. Theory Appl."},{"key":"316_CR47","doi-asserted-by":"publisher","unstructured":"Zhang, Y., Sahinidis, N.V.: Solving continuous and discrete nonlinear programs with BARON. Computational Optimization and Applications, 92, 1123\u20131161 (2025). https:\/\/doi.org\/10.1007\/s10589-024-00633-0","DOI":"10.1007\/s10589-024-00633-0"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-026-00316-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-026-00316-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-026-00316-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T12:03:35Z","timestamp":1779797015000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-026-00316-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,10]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["316"],"URL":"https:\/\/doi.org\/10.1007\/s12532-026-00316-3","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,10]]},"assertion":[{"value":"20 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}