{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:35Z","timestamp":1740122435173,"version":"3.37.3"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,9]],"date-time":"2022-05-09T00:00:00Z","timestamp":1652054400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,9]],"date-time":"2022-05-09T00:00:00Z","timestamp":1652054400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018755","name":"Universit\u00e4t Trier","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018755","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chv\u00e1tal\u2013Gomory closure of the Boolean Quadric Polytope are <jats:italic>A<\/jats:italic>-odd cycle inequalities. We obtain a compact extended relaxation of <jats:italic>all<\/jats:italic><jats:italic>A<\/jats:italic>-odd cycle inequalities, which allows to optimize over the Chv\u00e1tal\u2013Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163\u2013177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333\u2013382, 2018), which arise from separating <jats:italic>A<\/jats:italic>-odd cycle inequalities heuristically.<\/jats:p>","DOI":"10.1007\/s10898-022-01157-9","type":"journal-article","created":{"date-parts":[[2022,5,9]],"date-time":"2022-05-09T04:02:26Z","timestamp":1652068946000},"page":"591-606","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints"],"prefix":"10.1007","volume":"84","author":[{"given":"Sven de","family":"Vries","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9756-6603","authenticated-orcid":false,"given":"Bernd","family":"Perscheid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,9]]},"reference":[{"key":"1157_CR1","volume-title":"Network Flows: Theory, Applications and Algorithms","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Applications and Algorithms. Prentice-Hall, Upper Saddle River (1993)"},{"issue":"2","key":"1157_CR2","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F Barahona","year":"1986","unstructured":"Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. 36(2), 157\u2013173 (1986)","journal-title":"Math. Program."},{"issue":"3","key":"1157_CR3","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.: Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Math. Program. Comput. 10(3), 333\u2013382 (2018)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"1157_CR4","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1137\/0405014","volume":"5","author":"E Boros","year":"1992","unstructured":"Boros, E., Crama, Y., Hammer, P.L.: Chv\u00e1tal cuts and odd cycle inequalities in quadratic 0\u20131 optimization. SIAM J. Discrete Math. 5(2), 163\u2013177 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1157_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-010-0010-8","volume":"2","author":"S Burer","year":"2010","unstructured":"Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2(1), 1\u201319 (2010)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"1157_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10589-007-9137-6","volume":"43","author":"S Burer","year":"2009","unstructured":"Burer, S., Vandenbussche, D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2), 181\u2013195 (2009)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1157_CR7","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02592196","volume":"74","author":"A Caprara","year":"1996","unstructured":"Caprara, A., Fischetti, M.: $$\\{$$0, 1\/2$$\\}$$-Chv\u00e1tal\u2013Gomory cuts. Math. Program. 74(3), 221\u2013235 (1996)","journal-title":"Math. Program."},{"issue":"2","key":"1157_CR8","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00453-008-9218-7","volume":"55","author":"AM Koster","year":"2009","unstructured":"Koster, A.M., Zymolka, A., Kutschka, M.: Algorithms to separate $$\\{$$0, 1\/2$$\\}$$-Chv\u00e1tal\u2013Gomory cuts. Algorithmica 55(2), 375\u2013391 (2009)","journal-title":"Algorithmica"},{"issue":"1","key":"1157_CR9","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."},{"key":"1157_CR10","unstructured":"Perscheid, B.: New concise extended formulations for circular structures in optimization problems. Ph.D. thesis, Trier University (2020)"},{"issue":"3","key":"1157_CR11","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/s10107-004-0550-7","volume":"102","author":"D Vandenbussche","year":"2005","unstructured":"Vandenbussche, D., Nemhauser, G.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3), 559\u2013575 (2005)","journal-title":"Math. Program."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01157-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-022-01157-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01157-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T06:11:59Z","timestamp":1666246319000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-022-01157-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,9]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1157"],"URL":"https:\/\/doi.org\/10.1007\/s10898-022-01157-9","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2022,5,9]]},"assertion":[{"value":"15 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}