{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T08:15:26Z","timestamp":1770538526129,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T00:00:00Z","timestamp":1529280000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T00:00:00Z","timestamp":1529280000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP17J07365"],"award-info":[{"award-number":["JP17J07365"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF 2014-R1A2A1A11049618"],"award-info":[{"award-number":["NRF 2014-R1A2A1A11049618"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF 2017-R1A2B2005119"],"award-info":[{"award-number":["NRF 2017-R1A2B2005119"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"crossref","award":["Grant-in-Aid for Scientific Research (A) 26242027"],"award-info":[{"award-number":["Grant-in-Aid for Scientific Research (A) 26242027"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"crossref","award":["the Core Research of Evolutionary Science and Technology (CREST) research project"],"award-info":[{"award-number":["the Core Research of Evolutionary Science and Technology (CREST) research project"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Grant-in-Aid for Scientific Research","award":["15K00031"],"award-info":[{"award-number":["15K00031"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s10898-018-0676-4","type":"journal-article","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T04:00:00Z","timestamp":1529294400000},"page":"619-653","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems"],"prefix":"10.1007","volume":"72","author":[{"given":"N.","family":"Ito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Kojima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Takeda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.-C.","family":"Toh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,18]]},"reference":[{"issue":"1","key":"676_CR1","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02614432","volume":"77","author":"F Alizadeh","year":"1997","unstructured":"Alizadeh, F., Pierre, J., Haeberly, A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77(1), 111\u2013128 (1997)","journal-title":"Math. Program."},{"key":"676_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895479898340299","volume":"22","author":"K Anstreicher","year":"2000","unstructured":"Anstreicher, K., Wolkowicz, H.: On Lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22, 41\u201355 (2000)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"676_CR3","doi-asserted-by":"publisher","first-page":"2320","DOI":"10.1137\/120890636","volume":"23","author":"N Arima","year":"2013","unstructured":"Arima, N., Kim, S., Kojima, M.: A quadratically constrained quadratic optimization model for completely positive cone programming. SIAM J. Optim. 23(4), 2320\u20132340 (2013)","journal-title":"SIAM J. Optim."},{"key":"676_CR4","first-page":"437","volume":"10","author":"N Arima","year":"2014","unstructured":"Arima, N., Kim, S., Kojima, M.: Simplified copositive and Lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables. Pac. J. Optim. 10, 437\u2013451 (2014)","journal-title":"Pac. J. Optim."},{"key":"676_CR5","first-page":"161","volume":"14","author":"N Arima","year":"2018","unstructured":"Arima, N., Kim, S., Kojima, M., Toh, K.C.: Lagrangian-conic relaxations, Part I: a unified framework and its applications to quadratic optimization problems. Pac. J. Optim. 14, 161\u2013192 (2018)","journal-title":"Pac. J. Optim."},{"issue":"3","key":"676_CR6","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10589-016-9879-0","volume":"66","author":"N Arima","year":"2017","unstructured":"Arima, N., Kim, S., Kojima, M., Toh, K.C.: A robust Lagrangian-DNN method for a class of quadratic optimization problems. Comput. Optim. Appl. 66(3), 453\u2013479 (2017)","journal-title":"Comput. Optim. Appl."},{"key":"676_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-017-1109-8","volume":"166","author":"IM Bomze","year":"2017","unstructured":"Bomze, I.M., Cheng, J., Dickinson, P.J.C., Lisser, A.: A fresh CP look at mixed-binary QPs: new formulations and relaxations. Math. Program. 166, 159\u2013184 (2017)","journal-title":"Math. Program."},{"key":"676_CR8","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., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301\u2013320 (2000)","journal-title":"J. Glob. Optim."},{"key":"676_CR9","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. Glob. Optim. 24, 163\u2013185 (2002)","journal-title":"J. Glob. Optim."},{"key":"676_CR10","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 non-convex quadratic programs. Math. Program. 120, 479\u2013495 (2009)","journal-title":"Math. Program."},{"key":"676_CR11","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, 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"key":"676_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1017\/S0305004100036185","volume":"58","author":"PH Diananda","year":"1962","unstructured":"Diananda, P.H.: On non-negative forms in real variables some or all of which are non-negative. Proc. Camb. Philos. Soc. 58, 17\u201325 (1962)","journal-title":"Proc. Camb. Philos. Soc."},{"key":"676_CR13","unstructured":"Hahn, P., Anjos, M.: QAPLIB\u2014a quadratic assignment problem library. \n                    http:\/\/www.seas.upenn.edu\/qaplib"},{"key":"676_CR14","unstructured":"Ito, N., Kim, S., Kojima, M., Takeda, A., Toh, K.C.: Numerical results on QAPs. \n                    https:\/\/napinoco.github.io\/papers\/IKKTT2017a_full_table.pdf\n                    \n                   (2017)"},{"key":"676_CR15","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.disopt.2016.08.001","volume":"24","author":"S Kim","year":"2017","unstructured":"Kim, S., Kojima, M.: Binary quadratic optimization problems that are difficult to solve by conic relaxations. Discrete Optim. 24, 170\u2013183 (2017)","journal-title":"Discrete Optim."},{"key":"676_CR16","unstructured":"Kim, S., Kojima, M., Toh, K.C.: Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints. Research report B-483, Tokyo Institute of Technology, Department of Mathematical and Computing Sciences, Oh-Okayama, Meguro-ku, Tokyo 152-8552 (2016)"},{"key":"676_CR17","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, 161\u2013187 (2016)","journal-title":"Math. Program."},{"key":"676_CR18","first-page":"129","volume":"80","author":"M Kojima","year":"1998","unstructured":"Kojima, M., Shida, M., Shindoh, S.: Local convergence of predictor-corrector infeasible-interior-point method for sdps and sdlcps. Math. Program. 80, 129\u2013160 (1998)","journal-title":"Math. Program."},{"key":"676_CR19","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and non-linear programming. Math. Program. 39, 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"676_CR20","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/BF01100205","volume":"7","author":"S Poljak","year":"1995","unstructured":"Poljak, S., Rendl, F., Wolkowicz, H.: A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Glob.Optim. 7, 51\u201373 (1995)","journal-title":"J. Glob.Optim."},{"key":"676_CR21","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/050637467","volume":"18","author":"J Povh","year":"2007","unstructured":"Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18, 223\u2013241 (2007)","journal-title":"SIAM J. Optim."},{"key":"676_CR22","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.disopt.2009.01.002","volume":"6","author":"J Povh","year":"2009","unstructured":"Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6, 231\u2013241 (2009)","journal-title":"Discrete Optim."},{"issue":"2\u20133","key":"676_CR23","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s10107-006-0038-8","volume":"109","author":"F Rendl","year":"2007","unstructured":"Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. Ser. B 109(2\u20133), 505\u2013524 (2007)","journal-title":"Math. Program. Ser. B"},{"key":"676_CR24","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BFb0121018","volume":"22","author":"SM Robinson","year":"1984","unstructured":"Robinson, S.M.: Local structure of feasible sets in nonlinear programming, part ii: nondegeneracy. Math. Program. Study 22, 217\u2013230 (1984)","journal-title":"Math. Program. Study"},{"key":"676_CR25","first-page":"1","volume":"25","author":"NZ Shor","year":"1987","unstructured":"Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1\u201311 (1987)","journal-title":"Sov. J. Comput. Syst. Sci."},{"key":"676_CR26","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"T\u00fct\u00fcnc\u00fc, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95, 189\u2013217 (2003)","journal-title":"Math. Program."},{"key":"676_CR27","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s12532-015-0082-6","volume":"7","author":"LQ Yang","year":"2015","unstructured":"Yang, L.Q., Sun, D.F., Toh, K.C.: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Prog. Comput. 7, 331\u2013366 (2015)","journal-title":"Math. Prog. Comput."},{"key":"676_CR28","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2, 71\u2013109 (1998)","journal-title":"J. Comb. Optim."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-018-0676-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-018-0676-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-018-0676-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T07:29:33Z","timestamp":1589700573000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-018-0676-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,18]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["676"],"URL":"https:\/\/doi.org\/10.1007\/s10898-018-0676-4","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,18]]},"assertion":[{"value":"10 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}