{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:47:19Z","timestamp":1787388439457,"version":"build-2736575974"},"reference-count":55,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100006360","name":"Bundesministerium f\u00fcr Wirtschaft und Energie","doi-asserted-by":"crossref","award":["03ET1549D"],"award-info":[{"award-number":["03ET1549D"]}],"id":[{"id":"10.13039\/501100006360","id-type":"DOI","asserted-by":"crossref"}]},{"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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well-known McCormick relaxation for a product of two variables $x$ and $y$ over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of $xy$ can be much tighter when computed over a strict, nonrectangular subset of the box. In order to exploit this in practice, we propose computing valid linear inequalities for the projection of the feasible region onto the $x$-$y$-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and-bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for $x$, $y$, and $xy$ over the available projections. Our computational evaluations using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly.<\/jats:p>","DOI":"10.1137\/19m1249825","type":"journal-article","created":{"date-parts":[[2020,5,11]],"date-time":"2020-05-11T14:45:32Z","timestamp":1589208332000},"page":"1339-1365","source":"Crossref","is-referenced-by-count":7,"title":["Using Two-Dimensional Projections for Stronger Separation and Propagation of Bilinear Terms"],"prefix":"10.1137","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4463-2873","authenticated-orcid":true,"given":"Benjamin","family":"M\u00fcller","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7892-3951","authenticated-orcid":true,"given":"Felipe","family":"Serrano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0391-5903","authenticated-orcid":true,"given":"Ambros","family":"Gleixner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,5,11]]},"reference":[{"key":"atypb1","unstructured":"T. Achterberg,\n                      Constraint Integer Programming\n                      , Ph.D. thesis, Technische Universit\u00e4t Berlin, 2007,https:\/\/doi.org\/10.14279\/depositonce-1634, URNnbn:de:kobv:83-opus-16117."},{"key":"atypb2","first-page":"449","author":"Achterberg T.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.2.273"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358194"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-008-9372-0"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0602-3"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-005-3969-1"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581273"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00340-7"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0462-2"},{"key":"atypb12","unstructured":"P. Belotti, S. Cafieri, J. Lee, and L. Liberti,\n                      On Feasibility Based Bounds Tightening\n                      , Tech. Report 3325, Optimization Online, 2012,http:\/\/www.optimization-online.org\/DB_HTML\/2012\/01\/3325.html."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1080\/10556780903087124"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.2.193.10561"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb18","unstructured":"COIN-OR,\n                      Ipopt, Interior Point Optimizer\n                      ,http:\/\/www.coin-or.org\/Ipopt, 2018."},{"key":"atypb19","unstructured":"COIN-OR,\n                      CppAD, a Package for Differentiation of p\u0327p algorithms\n                      ,http:\/\/www.coin-or.org\/CppAD(accessed December 2019)."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008282830093"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-016-0450-4"},{"key":"atypb22","first-page":"355","author":"Gleixner A.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb23","first-page":"233","volume":"3","author":"Grossmann I. E.","year":"2002","journal-title":"Optim. Eng."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009898604624"},{"key":"atypb25","unstructured":"G. Hendel,\n                      Empirical Analysis of Solving Phases in Mixed Integer Programming\n                      , Master's thesis, Technische Universit\u00e4t Berlin, 2014, URNnbn:de:0297-zib-54270."},{"key":"atypb26","first-page":"10","volume":"020017","author":"Hijazi H.","year":"2019","journal-title":"AIP Conference Proceedings"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.12.001"},{"key":"atypb28","unstructured":"ILOG Inc.\n                      CPLEX: High-Performance Software for Mathematical Programming and Optimization\n                      ,http:\/\/www.ilog.com\/products\/cplex\/(accessed December 2019)."},{"key":"atypb29","first-page":"217","author":"Karush W.","year":"2013","journal-title":"Basel"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-011-0025-9"},{"key":"atypb31","first-page":"247","author":"Kuhn H. W.","year":"2014","journal-title":"Springer Basel"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90006-X"},{"key":"atypb33","first-page":"119","author":"Lemar\u00e9chal C.","year":"2001","journal-title":"Boston"},{"key":"atypb34","first-page":"263","author":"Liberti L.","year":"2011","journal-title":"New York"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0582-7"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-018-0626-1"},{"key":"atypb37","first-page":"1","author":"Lodi A.","year":"2013","journal-title":"INFORMS"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.936019"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580665"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1002\/aic.10717"},{"key":"atypb41","first-page":"1","volume":"22","author":"Miller A. J.","year":"2011","journal-title":"SIAG\/OPT Views and News"},{"key":"atypb43","unstructured":"B. M\u00fcller, F. Serrano, and A. Gleixner,\n                      Using Two-Dimensional Projections for Stronger Separation and Propagation of Bilinear Terms\n                      , ZIB-Report 19-15, Zuse Institute Berlin, Berlin, 2019."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/0801021"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/BF01100205"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-016-9267-5"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/BF01106605"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(94)00097-2"},{"key":"atypb49","unstructured":"N. V. Sahinidis,\n                      \n                        BARON17.8.9:Global Optimization of Mixed-Integer Nonlinear Programs,\n                        User's Manual\n                      \n                      , 2017; available at \u016dlhttp:\/\/www.minlp.com\/baron."},{"key":"atypb51","unstructured":"T. Serra,\n                      Essays on Postoptimality, Lift-and-Project, and Scheduling\n                      , Ph.D. thesis, Tepper School of Business, Carnegie Mellon, Pittsburgh, PA, 2018,https:\/\/doi.org\/10.1184\/R1\/6716444.v1."},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"H. D. Sherali and W. P. Adams,\n                      A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems\n                      , Nonconvex Optim. Appl. 31, Kluwer, Dordrecht, 1999,https:\/\/doi.org\/10.1007\/978-1-4757-4388-3.","DOI":"10.1007\/978-1-4757-4388-3"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013819515732"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/S0098-1354(97)00146-4"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0846"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"atypb57","unstructured":"S. Vigerske,\n                      Decomposition in Multistage Stochastic Programming and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming\n                      , Ph.D. thesis, Mathematisch-Naturwissenschaftliche Fakult\u00e4t II, Humboldt-Universit\u00e4t zu Berlin, 2013, URNnbn:de:kobv:11-100208240."},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2017.1335312"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0559-y"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008312714792"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1249825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:21:34Z","timestamp":1787340094000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1249825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M1249825"],"URL":"https:\/\/doi.org\/10.1137\/19m1249825","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}