{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T13:06:39Z","timestamp":1780923999382,"version":"3.54.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:00:00Z","timestamp":1618876800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:00:00Z","timestamp":1618876800000},"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":["J Glob Optim"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative formulations. Our first formulation is based on casting a standard quadratic program as a linear program with complementarity constraints. We then employ binary variables to linearize the complementarity constraints. For the second formulation, we first derive an overestimating function of the objective function and establish its tightness at any global minimizer. We then linearize the overestimating function using binary variables and obtain our second formulation. For both formulations, we propose a set of valid inequalities. Our extensive computational results illustrate that the proposed mixed integer linear programming reformulations significantly outperform other global solution approaches. On larger instances, we usually observe improvements of several orders of magnitude.<\/jats:p>","DOI":"10.1007\/s10898-021-01017-y","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T05:03:11Z","timestamp":1618894991000},"page":"293-321","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations"],"prefix":"10.1007","volume":"81","author":[{"given":"Jacek","family":"Gondzio","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4141-3189","authenticated-orcid":false,"given":"E. Alper","family":"Y\u0131ld\u0131r\u0131m","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,4,20]]},"reference":[{"issue":"2","key":"1017_CR1","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10898-004-4312-0","volume":"33","author":"KM Anstreicher","year":"2005","unstructured":"Anstreicher, K.M., Burer, S.: DC versus copositive bounds for standard QP. J. Global Optim. 33(2), 299\u2013312 (2005)","journal-title":"J. Global Optim."},{"issue":"4\u20135","key":"1017_CR2","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":"4","key":"1017_CR3","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1023\/A:1008369322970","volume":"13","author":"IM Bomze","year":"1998","unstructured":"Bomze, I.M.: On standard quadratic optimization problems. J. Global Optim. 13(4), 369\u2013387 (1998)","journal-title":"J. Global Optim."},{"issue":"1\u20134","key":"1017_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1023\/A:1013886408463","volume":"22","author":"IM Bomze","year":"2002","unstructured":"Bomze, I.M.: Branch-and-bound approaches to standard quadratic optimization problems. J. Global Optim. 22(1\u20134), 17\u201337 (2002)","journal-title":"J. Global Optim."},{"issue":"3","key":"1017_CR5","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/S00361445003756","volume":"44","author":"IM Bomze","year":"2002","unstructured":"Bomze, I.M.: Regularity versus degeneracy in dynamics, games, and optimization: A unified approach to different aspects. SIAM Rev. 44(3), 394\u2013414 (2002)","journal-title":"SIAM Rev."},{"issue":"2","key":"1017_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/A:1020209017701","volume":"24","author":"IM Bomze","year":"2002","unstructured":"Bomze, I.M., De Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24(2), 163\u2013185 (2002)","journal-title":"J. Global Optim."},{"issue":"4","key":"1017_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1023\/A:1026583532263","volume":"18","author":"IM Bomze","year":"2000","unstructured":"Bomze, I.M., D\u00fcr, M., De Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Global Optim. 18(4), 301\u2013320 (2000)","journal-title":"J. Global Optim."},{"issue":"1","key":"1017_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s10107-007-0138-0","volume":"115","author":"IM Bomze","year":"2008","unstructured":"Bomze, I.M., Locatelli, M., Tardella, F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115(1), 31 (2008)","journal-title":"Math. Program."},{"issue":"2","key":"1017_CR9","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1287\/moor.2017.0877","volume":"43","author":"IM Bomze","year":"2018","unstructured":"Bomze, I.M., Schachinger, W., Ullrich, R.: The complexity of simple models - A study of worst and typical hard cases for the standard quadratic optimization problem. Math. Oper. Res. 43(2), 651\u2013674 (2018)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1017_CR10","doi-asserted-by":"publisher","first-page":"1076","DOI":"10.1137\/16M107428X","volume":"29","author":"P Bonami","year":"2019","unstructured":"Bonami, P., Lodi, A., Schweiger, J., Tramontani, A.: Solving standard quadratic programming by cutting planes. SIAM J. Optim. 29(2), 1076\u20131105 (2019)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1017_CR11","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/070711815","volume":"20","author":"S Bundfuss","year":"2009","unstructured":"Bundfuss, S., D\u00fcr, M.: An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1), 30\u201353 (2009)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1017_CR12","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10107-006-0080-6","volume":"113","author":"S Burer","year":"2008","unstructured":"Burer, S., Vandenbussche, D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113(2), 259\u2013282 (2008)","journal-title":"Math. Program."},{"issue":"1","key":"1017_CR13","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."},{"issue":"2","key":"1017_CR14","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s10589-013-9594-z","volume":"57","author":"PJC Dickinson","year":"2014","unstructured":"Dickinson, P.J.C., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57(2), 403\u2013415 (2014)","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"1017_CR15","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."},{"key":"1017_CR16","doi-asserted-by":"crossref","unstructured":"Giannessi, F., Tomasin, E.: Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: IFIP Technical Conference on Optimization Techniques, pp. 437\u2013449. Springer (1973)","DOI":"10.1007\/3-540-06583-0_43"},{"issue":"3","key":"1017_CR17","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1287\/moor.22.3.754","volume":"22","author":"LE Gibbons","year":"1997","unstructured":"Gibbons, L.E., Hearn, D.W., Pardalos, P.M., Ramana, M.V.: Continuous characterizations of the maximum clique problem. Math. Oper. Res. 22(3), 754\u2013768 (1997)","journal-title":"Math. Oper. Res."},{"key":"1017_CR18","unstructured":"Gurobi Optimization, LLC: Gurobi optimizer reference manual (2018). http:\/\/www.gurobi.com"},{"issue":"1","key":"1017_CR19","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/07068463x","volume":"19","author":"J Hu","year":"2008","unstructured":"Hu, J., Mitchell, J., Pang, J., Bennett, K., Kunapuli, G.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19(1), 445\u2013471 (2008)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1017_CR20","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10107-010-0426-y","volume":"133","author":"J Hu","year":"2012","unstructured":"Hu, J., Mitchell, J.E., Pang, J.S.: An LPCC approach to nonconvex quadratic programs. Math. Program. 133(1), 243\u2013277 (2012)","journal-title":"Math. Program."},{"key":"1017_CR21","volume-title":"Resource Allocation Problems: Algorithmic Approaches","author":"T Ibaraki","year":"1988","unstructured":"Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, MA, USA (1988)"},{"key":"1017_CR22","unstructured":"IBM: IBM ILOG CPLEX Optimization Studio (2018). https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio"},{"issue":"1","key":"1017_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10107-015-0874-5","volume":"156","author":"S Kim","year":"2016","unstructured":"Kim, S., Kojima, M., Toh, K.C.: A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Program. 156(1), 161\u2013187 (2016)","journal-title":"Math. Program."},{"issue":"3","key":"1017_CR24","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1017\/S0305004100035635","volume":"57","author":"JFC Kingman","year":"1961","unstructured":"Kingman, J.F.C.: A mathematical problem in population genetics. Math. Proc. Cambridge Philos. Soc. 57(3), 574\u2013582 (1961)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"issue":"1","key":"1017_CR25","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1080\/10556788.2017.1341504","volume":"34","author":"G Liuzzi","year":"2019","unstructured":"Liuzzi, G., Locatelli, M., Piccialli, V.: A new branch-and-bound algorithm for standard quadratic programming problems. Optim. Methods Softw. 34(1), 79\u201397 (2019)","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"1017_CR26","first-page":"77","volume":"7","author":"H Markowitz","year":"1952","unstructured":"Markowitz, H.: Portfolio selection. The J. Finance 7(1), 77\u201391 (1952)","journal-title":"The J. Finance"},{"issue":"4","key":"1017_CR27","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"TS Motzkin","year":"1965","unstructured":"Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Canad. J. Math 17(4), 533\u2013540 (1965)","journal-title":"Canad. J. Math"},{"issue":"4","key":"1017_CR28","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1023\/A:1008315627883","volume":"14","author":"I Nowak","year":"1999","unstructured":"Nowak, I.: A new semidefinite programming bound for indefinite quadratic forms over a simplex. J. Global Optim. 14(4), 357\u2013364 (1999)","journal-title":"J. Global Optim."},{"issue":"13","key":"1017_CR29","doi-asserted-by":"publisher","first-page":"2439","DOI":"10.1016\/j.dam.2007.09.020","volume":"156","author":"A Scozzari","year":"2008","unstructured":"Scozzari, A., Tardella, F.: A clique algorithm for standard quadratic programming. Discret. Appl. Math. 156(13), 2439\u20132448 (2008)","journal-title":"Discret. Appl. Math."},{"key":"1017_CR30","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-005-0581-8","volume":"103","author":"M Tawarmalani","year":"2005","unstructured":"Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225\u2013249 (2005)","journal-title":"Math. Program."},{"issue":"1","key":"1017_CR31","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1287\/ijoc.2018.0883","volume":"32","author":"W Xia","year":"2020","unstructured":"Xia, W., Vera, J., Zuluaga, L.F.: Globally solving nonconvex quadratic programs via linear integer programming techniques. Informs J. Comput. 32(1), 40\u201356 (2020)","journal-title":"Informs J. Comput."},{"issue":"2","key":"1017_CR32","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s12532-018-0149-2","volume":"11","author":"B Yu","year":"2019","unstructured":"Yu, B., Mitchell, J.E., Pang, J.S.: Solving linear programs with complementarity constraints using branch-and-cut. Math. Program. Comput. 11(2), 267\u2013310 (2019)","journal-title":"Math. Program. Comput."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01017-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01017-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01017-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,9]],"date-time":"2021-09-09T07:14:59Z","timestamp":1631171699000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01017-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,20]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["1017"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01017-y","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,20]]},"assertion":[{"value":"22 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}