{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T03:11:08Z","timestamp":1771470668146,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T00:00:00Z","timestamp":1706572800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T00:00:00Z","timestamp":1706572800000},"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":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In this paper, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products of the form <jats:inline-formula><jats:alternatives><jats:tex-math>$$z=xy$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>z<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mi>y<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, called <jats:italic>hybrid separable<\/jats:italic> (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called <jats:italic>sawtooth relaxation<\/jats:italic>, based on Beach (Beach in J Glob Optim 84:869\u2013912, 2022). We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the MIP relaxation <jats:italic>normalized multiparametric disaggregation technique<\/jats:italic> (NMDT) (Castro in J Glob Optim 64:765\u2013784, 2015) and present a computational study which also includes the MIP relaxations from this work and compares them with a state-of-the-art of MIQCQP solvers.<\/jats:p>","DOI":"10.1007\/s10589-023-00543-7","type":"journal-article","created":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T08:02:59Z","timestamp":1706601779000},"page":"835-891","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: Part I"],"prefix":"10.1007","volume":"87","author":[{"given":"Benjamin","family":"Beach","sequence":"first","affiliation":[]},{"given":"Robert","family":"Burlacu","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"B\u00e4rmann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5002-2919","authenticated-orcid":false,"given":"Lukas","family":"Hager","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Hildebrand","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,30]]},"reference":[{"issue":"9","key":"543_CR1","doi-asserted-by":"publisher","first-page":"1137","DOI":"10.1016\/S0098-1354(98)00027-1","volume":"22","author":"CS Adjiman","year":"1998","unstructured":"Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, $$\\alpha $$bb, for general twice-differentiable constrained NLPs\u2014i. theoretical advances. Comput. Chem. Eng. 22(9), 1137\u20131158 (1998)","journal-title":"Comput. Chem. Eng."},{"issue":"2","key":"543_CR2","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1287\/ijoc.2023.1270","volume":"35","author":"K-M Aigner","year":"2023","unstructured":"Aigner, K.-M., Burlacu, R., Liers, F., Martin, A.: Solving ac optimal power flow with discrete decisions to global optimality. INFORMS J. Comput. 35(2), 458\u2013474 (2023)","journal-title":"INFORMS J. Comput."},{"issue":"4","key":"543_CR3","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01099647","volume":"7","author":"IP Androulakis","year":"1995","unstructured":"Androulakis, I.P., Maranas, C.D., Floudas, C.A.: $$\\alpha $$bb: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7(4), 337\u2013363 (1995)","journal-title":"J. Glob. Optim."},{"key":"543_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/0-387-32942-0","volume-title":"Handbook on Modelling for Discrete Optimization","author":"GM Appa","year":"2006","unstructured":"Appa, G.M., Pitsoulis, L., Williams, H.P.: Handbook on Modelling for Discrete Optimization, vol. 88. Springer Science & Business Media, Berlin (2006)"},{"issue":"4","key":"543_CR5","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/s10898-022-01243-y","volume":"85","author":"A B\u00e4rmann","year":"2023","unstructured":"B\u00e4rmann, A., Burlacu, R., Hager, L., Kleinert, T.: On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed-integer programming formulations. J. Glob. Optim. 85(4), 789\u2013819 (2023)","journal-title":"J. Glob. Optim."},{"key":"543_CR6","doi-asserted-by":"publisher","first-page":"106839","DOI":"10.1016\/j.compchemeng.2020.106839","volume":"141","author":"B Beach","year":"2020","unstructured":"Beach, B., Hildebrand, R., Ellis, K., Lebreton, B.: An approximate method for the optimization of long-horizon tank blending and scheduling operations. Comput. Chem. Eng. 141, 106839 (2020)","journal-title":"Comput. Chem. Eng."},{"issue":"4","key":"543_CR7","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1007\/s10898-022-01184-6","volume":"84","author":"B Beach","year":"2022","unstructured":"Beach, B., Hildebrand, R., Huchette, J.: Compact mixed-integer programming formulations in quadratic optimization. J. Glob. Optim. 84(4), 869\u2013912 (2022)","journal-title":"J. Glob. Optim."},{"issue":"4\u20135","key":"543_CR8","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1080\/10556780903087124","volume":"24","author":"P Belotti","year":"2009","unstructured":"Belotti, P., Lee, J., Liberti, L., Margot, F., W\u00e4chter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4\u20135), 597\u2013634 (2009)","journal-title":"Optim. Methods Softw."},{"issue":"1\u20132","key":"543_CR9","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10107-010-0381-7","volume":"131","author":"A Billionnet","year":"2012","unstructured":"Billionnet, A., Elloumi, S., Lambert, A.: Extending the QCR method to general mixed-integer programs. Math. Program. 131(1\u20132), 381\u2013401 (2012)","journal-title":"Math. Program."},{"key":"543_CR10","doi-asserted-by":"crossref","unstructured":"B\u00e4rmann, A., Martin, A., Schneider, O.: The bipartite Boolean quadric polytope with multiple-choice constraints, 2022. Available at: arXiv:2009.11674","DOI":"10.1137\/22M147579X"},{"issue":"1","key":"543_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1080\/10556788.2018.1556661","volume":"35","author":"R Burlacu","year":"2020","unstructured":"Burlacu, R., Gei\u00dfler, B., Schewe, L.: Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes. Optim. Methods Softw. 35(1), 37\u201364 (2020)","journal-title":"Optim. Methods Softw."},{"issue":"4","key":"543_CR12","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s10898-018-0612-7","volume":"71","author":"PAC Castillo","year":"2018","unstructured":"Castillo, P.A.C., Castro, P.M., Mahalec, V.: Global optimization of MIQCPs with dynamic piecewise relaxations. J. Glob. Optim. 71(4), 691\u2013716 (2018)","journal-title":"J. Glob. Optim."},{"issue":"4","key":"543_CR13","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1007\/s10898-015-0342-z","volume":"64","author":"PM Castro","year":"2015","unstructured":"Castro, P.M.: Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems. J. Glob. Optim. 64(4), 765\u2013784 (2015)","journal-title":"J. Glob. Optim."},{"key":"543_CR14","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/j.compchemeng.2014.03.025","volume":"72","author":"PM Castro","year":"2015","unstructured":"Castro, P.M.: Tightening piecewise McCormick relaxations for bilinear problems. Comput. Chem. Eng. 72, 300\u2013311 (2015)","journal-title":"Comput. Chem. Eng."},{"key":"543_CR15","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.compchemeng.2016.06.016","volume":"93","author":"PM Castro","year":"2016","unstructured":"Castro, P.M.: Source-based discrete and continuous-time formulations for the crude oil pooling problem. Comput. Chem. Eng. 93, 382\u2013401 (2016)","journal-title":"Comput. Chem. Eng."},{"key":"543_CR16","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s11081-021-09603-5","volume":"23","author":"PM Castro","year":"2022","unstructured":"Castro, P.M., Liao, Q., Liang, Y.: Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems. Optim. Eng. 23, 717\u2013747 (2022)","journal-title":"Optim. Eng."},{"issue":"1","key":"543_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s12532-011-0033-9","volume":"4","author":"J Chen","year":"2012","unstructured":"Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4(1), 33\u201352 (2012)","journal-title":"Math. Program. Comput."},{"key":"543_CR18","unstructured":"Coffrin, C., Gordon, D., Scott, P.: NESTA, the NICTA energy system test case archive. arXiv preprint arXiv:1411.0359 (2014)"},{"key":"543_CR19","unstructured":"Correa-Posada, C.M., S\u00e1nchez-Mart\u00edn, P.: Gas network optimization: a comparison of piecewise linear models. Optimization Online (2014)"},{"issue":"2","key":"543_CR20","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(2), 201\u2013213 (2002)","journal-title":"Math. Program."},{"issue":"3","key":"543_CR21","doi-asserted-by":"publisher","first-page":"1962","DOI":"10.1137\/140960657","volume":"26","author":"H Dong","year":"2016","unstructured":"Dong, H.: Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM J. Optim. 26(3), 1962\u20131985 (2016)","journal-title":"SIAM J. Optim."},{"key":"543_CR22","unstructured":"Dong, H., Luo, Y.: Compact disjunctive approximations to nonconvex quadratically constrained programs. arXiv preprint: arXiv:1811.08122 (2018)"},{"issue":"3","key":"543_CR23","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1016\/j.compchemeng.2010.04.010","volume":"35","author":"DC Faria","year":"2011","unstructured":"Faria, D.C., Bagajewicz, M.J.: Novel bound contraction procedure for global optimization of bilinear MINLP problems with applications to water management problems. Comput. Chem. Eng. 35(3), 446\u2013455 (2011)","journal-title":"Comput. Chem. Eng."},{"issue":"2","key":"543_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s12532-018-0147-4","volume":"11","author":"F Furini","year":"2019","unstructured":"Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., et al.: Qplib: a library of quadratic programming instances. Math. Program. Comput. 11(2), 237\u2013265 (2019)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"543_CR25","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s12532-018-0147-4","volume":"11","author":"F Furini","year":"2019","unstructured":"Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., Sahinidis, N.V., Vigerske, S., Wiegele, A.: QPLIB: a library of quadratic programming instances. Math. Program. Comput. 11(2), 237\u2013265 (2019)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"543_CR26","doi-asserted-by":"publisher","first-page":"1213","DOI":"10.1007\/s11590-013-0676-8","volume":"8","author":"L Galli","year":"2014","unstructured":"Galli, L., Letchford, A.N.: A compact variant of the QCR method for quadratically constrained quadratic 0\u20131 programs. Optim. Lett. 8(4), 1213\u20131224 (2014)","journal-title":"Optim. Lett."},{"key":"543_CR27","doi-asserted-by":"crossref","unstructured":"Gei\u00dfler, B., Martin, A., Morsi, A., Schewe, L.: Using piecewise linear functions for solving MINLPs. In: Mixed Integer Nonlinear Programming, pp. 287\u2013314. Springer (2012)","DOI":"10.1007\/978-1-4614-1927-3_10"},{"key":"543_CR28","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2022)"},{"key":"543_CR29","unstructured":"Huchette, J.A.: Advanced mixed-integer programming formulations: methodology, computation, and application. PhD thesis, Massachusetts Institute of Technology (2018)"},{"issue":"4","key":"543_CR30","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1205\/026387603765173691","volume":"81","author":"M Joly","year":"2003","unstructured":"Joly, M., Pinto, J.M.: Mixed-integer programming techniques for the scheduling of fuel oil and asphalt production. Chem. Eng. Res. Des. 81(4), 427\u2013447 (2003)","journal-title":"Chem. Eng. Res. Des."},{"key":"543_CR31","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.compchemeng.2013.01.016","volume":"53","author":"SP Kolodziej","year":"2013","unstructured":"Kolodziej, S.P., Grossmann, I.E., Furman, K.C., Sawaya, N.W.: A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Comput. Chem. Eng. 53, 122\u2013142 (2013)","journal-title":"Comput. Chem. Eng."},{"key":"543_CR32","unstructured":"Kutzer, K.: Using piecewise linear approximation techniques to handle bilinear constraints. PhD thesis, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (2020)"},{"issue":"2","key":"543_CR33","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s10107-005-0582-7","volume":"103","author":"J Linderoth","year":"2005","unstructured":"Linderoth, J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 103(2), 251\u2013282 (2005)","journal-title":"Math. Program."},{"issue":"1","key":"543_CR34","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I\u2014convex underestimating problems. Math. Program. 10(1), 147\u2013175 (1976)","journal-title":"Math. Program."},{"issue":"1","key":"543_CR35","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10107-012-0555-6","volume":"136","author":"R Misener","year":"2012","unstructured":"Misener, R., Floudas, C.A.: Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Program. 136(1), 155\u2013182 (2012)","journal-title":"Math. Program."},{"key":"543_CR36","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/s10898-018-00734-1","volume":"74","author":"H Nagarajan","year":"2019","unstructured":"Nagarajan, H., Mowen, L., Wang, S., Bent, R., Sundar, K.: An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs. J. Global Optim. 74, 639\u2013675 (2019)","journal-title":"J. Global Optim."},{"issue":"1","key":"543_CR37","first-page":"105","volume":"26","author":"E Phan-huy-Hao","year":"1982","unstructured":"Phan-huy-Hao, E.: Quadratically constrained quadratic programming: some applications and a method for solution. Z. Oper. Res. 26(1), 105\u2013119 (1982)","journal-title":"Z. Oper. Res."},{"issue":"1","key":"543_CR38","doi-asserted-by":"publisher","first-page":"e12","DOI":"10.5334\/jors.81","volume":"4","author":"AS Siqueira","year":"2016","unstructured":"Siqueira, A.S., da Silva, R.C., Santos, L.-R.: Perprof-py: a python package for performance profile of mathematical optimization software. J. Open Res. Softw. 4(1), e12\u2013e12 (2016)","journal-title":"J. Open Res. Softw."},{"key":"543_CR39","unstructured":"Telgarsky, M.: Representation benefits of deep feedforward networks. arXiv:1509.08101 (2015)"},{"issue":"2","key":"543_CR40","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1287\/opre.1090.0721","volume":"58","author":"JP Vielma","year":"2010","unstructured":"Vielma, J.P., Ahmed, S., Nemhauser, G.: Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions. Oper. Res. 58(2), 303\u2013315 (2010)","journal-title":"Oper. Res."},{"key":"543_CR41","unstructured":"Wachter, A.: An interior point algorithm for large-scale nonlinear optimization with applications in process engineering. PhD thesis, Carnegie Mellon University (2002)"},{"key":"543_CR42","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.neunet.2017.07.002","volume":"94","author":"D Yarotsky","year":"2017","unstructured":"Yarotsky, D.: Error bounds for approximations with deep ReLU networks. Neural Netw. 94, 103\u2013114 (2017)","journal-title":"Neural Netw."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00543-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00543-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00543-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,13]],"date-time":"2024-04-13T12:07:02Z","timestamp":1713010022000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00543-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,30]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["543"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00543-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,30]]},"assertion":[{"value":"3 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}