{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T12:03:36Z","timestamp":1773144216415,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"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. Program."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study linear programming relaxations of nonconvex quadratic programs given by the reformulation\u2013linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. Using these properties, we present a complete description of the set of instances that admit an exact RLT relaxation. We then give a thorough discussion of how our results can be converted into simple algorithmic procedures to construct instances of quadratic programs with exact, inexact, or unbounded RLT relaxations.<\/jats:p>","DOI":"10.1007\/s10107-024-02070-7","type":"journal-article","created":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T13:02:21Z","timestamp":1709730141000},"page":"397-433","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations"],"prefix":"10.1007","volume":"209","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,3,6]]},"reference":[{"issue":"2","key":"2070_CR1","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.M., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H.D., Sahinidis, N.V., Vigerske, S., Wiegele, A.: QPLIB: A library of quadratic programming instances. Math. Program. Comput. 11(2), 237\u2013265 (2019). https:\/\/doi.org\/10.1007\/s12532-018-0147-4","journal-title":"Math. Program. Comput."},{"key":"2070_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-40065-5","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006). https:\/\/doi.org\/10.1007\/978-0-387-40065-5","edition":"2"},{"issue":"4","key":"2070_CR3","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":"2070_CR4","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."},{"key":"2070_CR5","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-1-4757-4388-3","volume-title":"A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems","author":"HD Sherali","year":"1999","unstructured":"Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, pp. 297\u2013367. Springer, Boston (1999). https:\/\/doi.org\/10.1007\/978-1-4757-4388-3"},{"issue":"4","key":"2070_CR6","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF00122429","volume":"2","author":"HD Sherali","year":"1992","unstructured":"Sherali, H.D., Alameddine, A.: A new reformulation-linearization technique for bilinear programming problems. J. Glob. Optim. 2(4), 379\u2013410 (1992). https:\/\/doi.org\/10.1007\/BF00122429","journal-title":"J. Glob. Optim."},{"issue":"1","key":"2070_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01100203","volume":"7","author":"HD Sherali","year":"1995","unstructured":"Sherali, H.D., Tun\u00e7bilek, C.H.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim. 7(1), 1\u201331 (1995). https:\/\/doi.org\/10.1007\/BF01100203","journal-title":"J. Glob. Optim."},{"key":"2070_CR8","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\u20134","key":"2070_CR9","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1023\/A:1013819515732","volume":"22","author":"HD Sherali","year":"2002","unstructured":"Sherali, H.D., Fraticelli, B.M.P.: Enhancing RLT relaxations via a new class of semidefinite cuts. J. Glob. Optim. 22(1\u20134), 233\u2013261 (2002). https:\/\/doi.org\/10.1023\/A:1013819515732","journal-title":"J. Glob. Optim."},{"issue":"2","key":"2070_CR10","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":"2","key":"2070_CR11","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s10107-008-0223-z","volume":"120","author":"S Burer","year":"2009","unstructured":"Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479\u2013495 (2009). https:\/\/doi.org\/10.1007\/s10107-008-0223-z","journal-title":"Math. Program."},{"issue":"1","key":"2070_CR12","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."},{"issue":"1","key":"2070_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s10107-011-0462-2","volume":"129","author":"X Bao","year":"2011","unstructured":"Bao, X., Sahinidis, N.V., Tawarmalani, M.: Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math. Program. 129(1), 129\u2013157 (2011). https:\/\/doi.org\/10.1007\/s10107-011-0462-2","journal-title":"Math. Program."},{"issue":"2","key":"2070_CR14","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."},{"issue":"3","key":"2070_CR15","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1137\/140987997","volume":"25","author":"IM Bomze","year":"2015","unstructured":"Bomze, I.M.: Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems. SIAM J. Optim. 25(3), 1249\u20131275 (2015). https:\/\/doi.org\/10.1137\/140987997","journal-title":"SIAM J. Optim."},{"key":"2070_CR16","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s101079900106","volume":"87","author":"C Audet","year":"2000","unstructured":"Audet, C., Hansen, P., Jaumard, B., Savard, G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Program. 87, 131\u2013152 (2000). https:\/\/doi.org\/10.1007\/s101079900106","journal-title":"Math. Program."},{"issue":"2","key":"2070_CR17","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(2), 225\u2013249 (2005). https:\/\/doi.org\/10.1007\/s10107-005-0581-8","journal-title":"Math. Program."},{"key":"2070_CR18","unstructured":"Qiu, Y., Y\u0131ld\u0131r\u0131m, E.A.: On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints. Technical report, School of Mathematics, The University of Edinburgh, Edinburgh, United Kingdom (2023). arxiv:2303.06761"},{"key":"2070_CR19","volume-title":"Theory of Linear and Integer Programming. Wiley-Interscience series in discrete mathematics and optimization","author":"A Schrijver","year":"1999","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, New York (1999)"},{"issue":"4","key":"2070_CR20","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. Glob. Optim. 13(4), 369\u2013387 (1998). https:\/\/doi.org\/10.1023\/A:1008369322970","journal-title":"J. Glob. Optim."},{"issue":"1","key":"2070_CR21","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":"4","key":"2070_CR22","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. Glob. Optim. 18(4), 301\u2013320 (2000). https:\/\/doi.org\/10.1023\/A:1026583532263","journal-title":"J. Glob. Optim."},{"issue":"4","key":"2070_CR23","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E de Klerk","year":"2002","unstructured":"de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002). https:\/\/doi.org\/10.1137\/S1052623401383248","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"2070_CR24","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956). https:\/\/doi.org\/10.1002\/nav.3800030109","journal-title":"Naval Res. Logist. Q."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02070-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02070-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02070-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T16:51:52Z","timestamp":1736959912000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02070-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,6]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["2070"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02070-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,6]]},"assertion":[{"value":"24 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 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"}}]}}