{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T00:16:05Z","timestamp":1775607365928,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T00:00:00Z","timestamp":1717027200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T00:00:00Z","timestamp":1717027200000},"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":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the reformulation\u2013linearization technique (RLT) relaxation and the SDP-RLT relaxation obtained by combining the Shor relaxation with the RLT relaxation. Both relaxations yield lower bounds on the optimal value of a quadratic program with box constraints. We show that each component of each vertex of the RLT relaxation lies in the set <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\{0,\\frac{1}{2},1\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:mfrac>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present complete algebraic descriptions of the set of instances that admit exact RLT relaxations as well as those that admit exact SDP-RLT relaxations. We show that our descriptions can be converted into algorithms for efficiently constructing instances with (1) exact RLT relaxations, (2) inexact RLT relaxations, (3) exact SDP-RLT relaxations, and (4) exact SDP-RLT but inexact RLT relaxations. Our preliminary computational experiments illustrate that our algorithms are capable of generating computationally challenging instances for state-of-the-art solvers.<\/jats:p>","DOI":"10.1007\/s10898-024-01407-y","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T11:04:02Z","timestamp":1717067042000},"page":"293-322","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints"],"prefix":"10.1007","volume":"90","author":[{"given":"Yuzhou","family":"Qiu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4141-3189","authenticated-orcid":false,"given":"E. Alper","family":"Y\u0131ld\u0131r\u0131m","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"1407_CR1","doi-asserted-by":"publisher","unstructured":"Angelis, P.L.D., Pardalos, P.M., Toraldo, G.: Quadratic programming with box constraints. In: Developments in Global Optimization, pp. 73\u201393. Springer, New York, NY (1997). https:\/\/doi.org\/10.1007\/978-1-4757-2600-8_5","DOI":"10.1007\/978-1-4757-2600-8_5"},{"key":"1407_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0015-5","volume-title":"Introduction to Global Optimization. Nonconvex Optimization and Its Applications","author":"R Horst","year":"2000","unstructured":"Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Nonconvex Optimization and Its Applications, vol. 48. Springer, New York (2000)"},{"issue":"5","key":"1407_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0041-5553(80)90098-1","volume":"20","author":"MK Kozlov","year":"1980","unstructured":"Kozlov, M.K., Tarasov, S.P., Khachiyan, L.G.: The polynomial solvability of convex quadratic programming. USSR Comput. Math. Math. Phys. 20(5), 223\u2013228 (1980). https:\/\/doi.org\/10.1016\/0041-5553(80)90098-1","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"4","key":"1407_CR4","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S Sahni","year":"1974","unstructured":"Sahni, S.: Computationally related problems. SIAM J. Comput. 3(4), 262\u2013279 (1974). https:\/\/doi.org\/10.1137\/0203021","journal-title":"SIAM J. Comput."},{"key":"1407_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"PM Pardalos","year":"1991","unstructured":"Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15\u201322 (1991). https:\/\/doi.org\/10.1007\/BF00120662","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1407_CR6","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1007\/s10107-021-01714-2","volume":"195","author":"AA Ahmadi","year":"2022","unstructured":"Ahmadi, A.A., Zhang, J.: On the complexity of finding a local minimizer of a quadratic function over a polytope. Math. Program. 195(1), 783\u2013792 (2022). https:\/\/doi.org\/10.1007\/s10107-021-01714-2","journal-title":"Math. Program."},{"issue":"1","key":"1407_CR7","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. Convex underestimating problems. Math. Program. 10(1), 147\u2013175 (1976). https:\/\/doi.org\/10.1007\/BF01580665","journal-title":"Math. Program."},{"issue":"1","key":"1407_CR8","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF00121304","volume":"2","author":"HD Sherali","year":"1992","unstructured":"Sherali, H.D., Tun\u00e7bilek, C.H.: A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Glob. Optim. 2(1), 101\u2013112 (1992). https:\/\/doi.org\/10.1007\/BF00121304","journal-title":"J. Glob. Optim."},{"issue":"6","key":"1407_CR9","first-page":"1","volume":"25","author":"NZ Shor","year":"1987","unstructured":"Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25(6), 1\u201311 (1987)","journal-title":"Sov. J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"1407_CR10","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s10898-014-0166-2","volume":"59","author":"R Misener","year":"2014","unstructured":"Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous\/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2\u20133), 503\u2013526 (2014). https:\/\/doi.org\/10.1007\/s10898-014-0166-2","journal-title":"J. Glob. Optim."},{"key":"1407_CR11","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). https:\/\/doi.org\/10.1007\/s10107-005-0581-8","journal-title":"Math. Program."},{"key":"1407_CR12","unstructured":"IBM ILOG CPLEX Optimization Studio: User\u2019s Manual for CPLEX (2023). https:\/\/www.ibm.com\/docs\/en\/icos"},{"key":"1407_CR13","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2023). https:\/\/www.gurobi.com"},{"issue":"1","key":"1407_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10898-021-01066-3","volume":"82","author":"EA Y\u0131ld\u0131r\u0131m","year":"2022","unstructured":"Y\u0131ld\u0131r\u0131m, E.A.: An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs. J. Glob. Optim. 82(1), 1\u201320 (2022). https:\/\/doi.org\/10.1007\/s10898-021-01066-3","journal-title":"J. Glob. Optim."},{"key":"1407_CR15","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1023\/A:1008293029350","volume":"13","author":"Y Yajima","year":"1998","unstructured":"Yajima, Y., Fujie, T.: A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Glob. Optim. 13, 151\u2013170 (1998). https:\/\/doi.org\/10.1023\/A:1008293029350","journal-title":"J. Glob. Optim."},{"issue":"2","key":"1407_CR16","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/080729529","volume":"20","author":"S Burer","year":"2009","unstructured":"Burer, S., Letchford, A.N.: On nonconvex quadratic programming with box constraints. SIAM J. Optim. 20(2), 1073\u20131089 (2009). https:\/\/doi.org\/10.1137\/080729529","journal-title":"SIAM J. Optim."},{"key":"1407_CR17","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10898-008-9372-0","volume":"43","author":"KM Anstreicher","year":"2009","unstructured":"Anstreicher, K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43, 471\u2013484 (2009). https:\/\/doi.org\/10.1007\/s10898-008-9372-0","journal-title":"J. Glob. Optim."},{"issue":"1\u20132","key":"1407_CR18","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-010-0355-9","volume":"124","author":"KM Anstreicher","year":"2010","unstructured":"Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124(1\u20132), 33\u201343 (2010). https:\/\/doi.org\/10.1007\/s10107-010-0355-9","journal-title":"Math. Program."},{"key":"1407_CR19","doi-asserted-by":"publisher","unstructured":"Dong, H., Linderoth, J.T.: On valid inequalities for quadratic programming with continuous variables and binary indicators. In: Goemans, M.X., Correa, J.R. (eds.) Integer Programming and Combinatorial Optimization\u201416th International Conference, IPCO 2013, Valpara\u00edso, Chile, March 18\u201320, 2013. Proceedings. Lecture Notes in Computer Science, vol. 7801, pp. 169\u2013180. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36694-9_15","DOI":"10.1007\/978-3-642-36694-9_15"},{"issue":"3","key":"1407_CR20","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s12532-018-0133-x","volume":"10","author":"P Bonami","year":"2018","unstructured":"Bonami, P., G\u00fcnl\u00fck, O., Linderoth, J.T.: Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Math. Program. Comput. 10(3), 333\u2013382 (2018). https:\/\/doi.org\/10.1007\/s12532-018-0133-x","journal-title":"Math. Program. Comput."},{"issue":"1","key":"1407_CR21","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45(1), 139\u2013172 (1989). https:\/\/doi.org\/10.1007\/BF01589101","journal-title":"Math. Program."},{"issue":"4","key":"1407_CR22","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1287\/opre.17.4.680","volume":"17","author":"M Raghavachari","year":"1969","unstructured":"Raghavachari, M.: On connections between zero-one integer programming and concave programming under linear constraints. Oper. Res. 17(4), 680\u2013684 (1969). https:\/\/doi.org\/10.1287\/opre.17.4.680","journal-title":"Oper. Res."},{"issue":"2","key":"1407_CR23","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1025794313696","volume":"26","author":"S Kim","year":"2003","unstructured":"Kim, S., Kojima, M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26(2), 143\u2013154 (2003). https:\/\/doi.org\/10.1023\/A:1025794313696","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"1407_CR24","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1137\/130915261","volume":"24","author":"S Sojoudi","year":"2014","unstructured":"Sojoudi, S., Lavaei, J.: Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure. SIAM J. Optim. 24(4), 1746\u20131778 (2014). https:\/\/doi.org\/10.1137\/130915261","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1407_CR25","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s10107-013-0716-2","volume":"147","author":"V Jeyakumar","year":"2014","unstructured":"Jeyakumar, V., Li, G.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. 147(1\u20132), 171\u2013206 (2014). https:\/\/doi.org\/10.1007\/s10107-013-0716-2","journal-title":"Math. Program."},{"issue":"6","key":"1407_CR26","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s11590-016-1001-0","volume":"10","author":"M Locatelli","year":"2016","unstructured":"Locatelli, M.: Exactness conditions for an SDP relaxation of the extended trust region problem. Optim. Lett. 10(6), 1141\u20131151 (2016). https:\/\/doi.org\/10.1007\/s11590-016-1001-0","journal-title":"Optim. Lett."},{"issue":"3","key":"1407_CR27","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1137\/16M1065197","volume":"27","author":"N Ho-Nguyen","year":"2017","unstructured":"Ho-Nguyen, N., Kilin\u00e7-Karzan, F.: A second-order cone based approach for solving the trust-region subproblem and its variants. SIAM J. Optim. 27(3), 1485\u20131512 (2017). https:\/\/doi.org\/10.1137\/16M1065197","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1407_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-019-01367-2","volume":"181","author":"S Burer","year":"2020","unstructured":"Burer, S., Ye, Y.: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. Math. Program. 181(1), 1\u201317 (2020). https:\/\/doi.org\/10.1007\/s10107-019-01367-2","journal-title":"Math. Program."},{"issue":"1","key":"1407_CR29","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-020-01589-9","volume":"193","author":"AL Wang","year":"2022","unstructured":"Wang, A.L., Kilin\u00e7-Karzan, F.: On the tightness of SDP relaxations of QCQPs. Math. Program. 193(1), 33\u201373 (2022). https:\/\/doi.org\/10.1007\/s10107-020-01589-9","journal-title":"Math. Program."},{"key":"1407_CR30","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10898-021-01071-6","volume":"82","author":"G Azuma","year":"2022","unstructured":"Azuma, G., Fukuda, M., Kim, S., Yamashita, M.: Exact SDP relaxations of quadratically constrained quadratic programs with forest structures. J. Glob. Optim. 82, 243\u2013262 (2022). https:\/\/doi.org\/10.1007\/s10898-021-01071-6","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1407_CR31","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10898-015-0269-4","volume":"63","author":"G Sa\u011fol","year":"2015","unstructured":"Sa\u011fol, G., Y\u0131ld\u0131r\u0131m, E.A.: Analysis of copositive optimization based linear programming bounds on standard quadratic optimization. J. Glob. Optim. 63(1), 37\u201359 (2015). https:\/\/doi.org\/10.1007\/s10898-015-0269-4","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1407_CR32","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-020-01611-0","volume":"193","author":"YG G\u00f6kmen","year":"2022","unstructured":"G\u00f6kmen, Y.G., Y\u0131ld\u0131r\u0131m, E.A.: On standard quadratic programs with exact and inexact doubly nonnegative relaxations. Math. Program. 193(1), 365\u2013403 (2022). https:\/\/doi.org\/10.1007\/s10107-020-01611-0","journal-title":"Math. Program."},{"issue":"1","key":"1407_CR33","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF01584097","volume":"1","author":"A Majthay","year":"1971","unstructured":"Majthay, A.: Optimality conditions for quadratic programming. Math. Program. 1(1), 359\u2013365 (1971). https:\/\/doi.org\/10.1007\/BF01584097","journal-title":"Math. Program."},{"issue":"5","key":"1407_CR34","first-page":"625","volume":"3","author":"L Jiaquan","year":"1982","unstructured":"Jiaquan, L., Tiantai, S., Dingzhu, D.: On the necessary and sufficient condition of the local optimal solution of quadratic programming. Chin. Ann. Math. Ser. B 3(5), 625\u2013630 (1982)","journal-title":"Chin. Ann. Math. Ser. B"},{"issue":"1","key":"1407_CR35","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.P.: Semidefinite programming. SIAM Rev. 38(1), 49\u201395 (1996). https:\/\/doi.org\/10.1137\/1038003","journal-title":"SIAM Rev."},{"key":"1407_CR36","volume-title":"Convex Analysis. Princeton Landmarks in Mathematics and Physics","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton (1970)"},{"issue":"2","key":"1407_CR37","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/S10107-012-0602-3","volume":"136","author":"KM Anstreicher","year":"2012","unstructured":"Anstreicher, K.M.: On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136(2), 233\u2013251 (2012). https:\/\/doi.org\/10.1007\/S10107-012-0602-3","journal-title":"Math. Program."},{"key":"1407_CR38","unstructured":"Locatelli, M., Piccialli, V., Sudoso, A.M.: Fix and bound: an efficient approach for solving large-scale quadratic programming problems with box constraints (2022). arXiv:2211.08911"},{"issue":"1","key":"1407_CR39","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/141000671","volume":"59","author":"J Bezanson","year":"2017","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65\u201398 (2017). https:\/\/doi.org\/10.1137\/141000671","journal-title":"SIAM Rev."},{"key":"1407_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-023-00239-3","author":"M Lubin","year":"2023","unstructured":"Lubin, M., Dowson, O., Dias Garcia, J., Huchette, J., Legat, B., Vielma, J.P.: JuMP 1.0: recent improvements to a modeling language for mathematical optimization. Math. Program. Comput. (2023). https:\/\/doi.org\/10.1007\/s12532-023-00239-3","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-024-01407-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01407-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01407-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T05:03:25Z","timestamp":1726895005000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01407-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,30]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1407"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01407-y","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,30]]},"assertion":[{"value":"1 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 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":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}