{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:04:19Z","timestamp":1750219459597,"version":"3.41.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T00:00:00Z","timestamp":1731283200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T00:00:00Z","timestamp":1731283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"NRF","award":["2021-R1A2C1003810"],"award-info":[{"award-number":["2021-R1A2C1003810"]}]},{"name":"German Federal Ministry of Education and Research","award":["0BMBF grant numbers: 5M14ZAM","0BMBF grant numbers: 05M20ZBM"],"award-info":[{"award-number":["0BMBF grant numbers: 5M14ZAM","0BMBF grant numbers: 05M20ZBM"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s11590-024-02157-2","type":"journal-article","created":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T02:09:09Z","timestamp":1731290949000},"page":"1075-1097","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An exceptionally difficult binary quadratic optimization problem with symmetry: a challenge for the largest unsolved QAP instance Tai256c"],"prefix":"10.1007","volume":"19","author":[{"given":"Koichi","family":"Fujii","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sunyoung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masakazu","family":"Kojima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans D.","family":"Mittelmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuji","family":"Shinano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,11]]},"reference":[{"key":"2157_CR1","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s101070100255","volume":"91","author":"K Anstreicher","year":"2002","unstructured":"Anstreicher, K., Brixius, N., Goux, J.-P., Linderoth, J.: Solving large quadratic assignment problems on computational grids. Math. Program. 91, 563\u2013588 (2002)","journal-title":"Math. Program."},{"key":"2157_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":"1","key":"2157_CR3","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. Pacific J. Optim. 14(1), 161\u2013192 (2018)","journal-title":"Pacific J. Optim."},{"issue":"3","key":"2157_CR4","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":"2157_CR5","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"2157_CR6","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2021.2022146","author":"D Brosch","year":"2022","unstructured":"Brosch, D., de Klerk, E.: Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software. Optim. Methods Softw. (2022). https:\/\/doi.org\/10.1080\/10556788.2021.2022146","journal-title":"Optim. Methods Softw."},{"key":"2157_CR7","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1023\/A:1008293323270","volume":"10","author":"RE Burkard","year":"1997","unstructured":"Burkard, R.E., \u00c7ela, E., Karisch, S.E., Rendl, F.: QAPLIB \u2013 a quadratic assignment problem library. J. Global Optim. 10, 391\u2013403 (1997)","journal-title":"J. Global Optim."},{"key":"2157_CR8","unstructured":"Burkard, R.E., \u00c7ela, E., Karisch, S.E., Rendl, F., Anjos, M., Hahn, P.: QAPLIB - A Quadratic Assignment Problem Library - Problem instances and solutions, https:\/\/datashare.ed.ac.uk\/handle\/10283\/4390, (2022)"},{"key":"2157_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1023\/A:1008696503659","volume":"8","author":"J Clausen","year":"1997","unstructured":"Clausen, J., Perregaard, M.: Solving large quadratic assignment problems in parallel. Comput. Optim. Appl. 8, 111\u2013127 (1997)","journal-title":"Comput. Optim. Appl."},{"key":"2157_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0377-2217(90)90301-Q","volume":"46","author":"DT Connolly","year":"1990","unstructured":"Connolly, D.T.: An improved annealing scheme for the QAP. Eur. J. Oper. Res. 46, 93\u2013100 (1990)","journal-title":"Eur. J. Oper. Res."},{"key":"2157_CR11","unstructured":"IBM Corporation. 2024. ILOG CPLEX Optimization Studio User\u2019s Manual: https:\/\/www.ibm.com\/docs\/es\/icos\/22.1.0"},{"key":"2157_CR12","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-008-0246-5","volume":"122","author":"E de Klerk","year":"2010","unstructured":"de Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. 122, 225\u2013246 (2010)","journal-title":"Math. Program."},{"key":"2157_CR13","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s10107-010-0411-5","volume":"133","author":"E de Klerk","year":"2012","unstructured":"de Klerk, E., Sotirov, R.: Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Program. 133, 75\u201391 (2012)","journal-title":"Math. Program."},{"key":"2157_CR14","doi-asserted-by":"crossref","unstructured":"Fischetti, M., Monaci, M., Salvagnin, D.: Three ideas for the quadratic assignment problem. Oper. Res., 60(4):Published Online:1 Aug 2012, (2012)","DOI":"10.1287\/opre.1120.1073"},{"key":"2157_CR15","unstructured":"Gambardella, L.\u00a0M., Taillard, E.\u00a0D., Dorigo, M.: Ant colonies for the QAP. Technical report idsia-4-97, IDSIA, Lugano, Switzerland, (1997)"},{"key":"2157_CR16","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"PC Gilmore","year":"1962","unstructured":"Gilmore, P.C.: Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J. Appl. Math. 10, 305\u2013313 (1962)","journal-title":"SIAM J. Appl. Math."},{"key":"2157_CR17","unstructured":"Goncalves, A.\u00a0D., Pessoa, A.\u00a0A., de\u00a0A. Drummond, L.\u00a0M., Bentes, C., Farias, R.: Solving the quadratic assignment problem on heterogeneous environment (CPUs and GPUs) with the application of level 2 reformulation and linearization technique. Technical Report arXiv:1510.02065v1, (2015)"},{"key":"2157_CR18","unstructured":"LLC Gurobi\u00a0Optimization. (2024). Gurobi Optimizer Reference Manual: https:\/\/www.gurobi.com"},{"issue":"4","key":"2157_CR19","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s10898-018-0676-4","volume":"72","author":"N Ito","year":"2018","unstructured":"Ito, N., Kim, S., Kojima, M., Takeda, A., Toh, K.C.: Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems. J. Global Optim. 72(4), 619\u2013653 (2018)","journal-title":"J. Global Optim."},{"issue":"1","key":"2157_CR20","first-page":"75","volume":"8","author":"S Ji","year":"2012","unstructured":"Ji, S., Zheng, X., Sun, X.: An improved convex 0\u20131 quadratic program reformulation for quadratic knapsack problems. Pacific J. Optim. 8(1), 75\u201387 (2012)","journal-title":"Pacific J. Optim."},{"key":"2157_CR21","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":"2157_CR22","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1080\/10556788.2020.1782906","volume":"36","author":"S Kim","year":"2021","unstructured":"Kim, S., Kojima, M., Toh, K.C.: A Newton-bracketing method for a simple conic optimization problem. Optim. Methods Softw. 36, 371\u2013388 (2021)","journal-title":"Optim. Methods Softw."},{"key":"2157_CR23","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"19","author":"EL Lawler","year":"1963","unstructured":"Lawler, E.L.: The quadratic assignment problem. Management Sci. 19, 586\u2013590 (1963)","journal-title":"Management Sci."},{"key":"2157_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-002-0358-2","volume":"94","author":"F Margot","year":"2002","unstructured":"Margot, F.: Pruning by isomorphism in branch-and-cut. Math. Program. 94, 71\u201390 (2002)","journal-title":"Math. Program."},{"key":"2157_CR25","unstructured":"McKay, B.D.: Nauty users guide (version 2:4). Dept. Comp. Sci., Australian National University, Technical report (2010)"},{"key":"2157_CR26","unstructured":"Mittelmann, H.: Benchmarks for optimization software. http:\/\/plato.asu.edu\/bench.html, 2012. Accessed: Nov (2023)"},{"key":"2157_CR27","unstructured":"Mittelmann, H.: Improved QAPLIB lower bounds using BBCPOP and Newton-Bracket, https:\/\/plato.asu.edu\/ftp\/qaplib_bounds.html, December (2023)"},{"key":"2157_CR28","unstructured":"Mittelmann, H.: Nonconvex QUBO-QPLIB benchmark, https:\/\/plato.asu.edu\/ftp\/qubo.html, September (2023)"},{"key":"2157_CR29","doi-asserted-by":"crossref","unstructured":"Nakano, K., Takafuji, D., Ito, Y., Yazane, T., Yano, S., an, J., Katsuki, R., Mori, R.: Diverse adaptive bulk search: a framework for solving qubo problems on multiple gpus. In: Proceedings of 2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 314\u2013325, May, (2023)","DOI":"10.1109\/IPDPSW59300.2023.00060"},{"key":"2157_CR30","unstructured":"Nissofolk, O., P\u00f6rn, R., Westerlund, T.: Testing a non-diagonal convex reformulation technique for 0-1 quadratic programs. Presentation at ESXAP 26, Slides, https:\/\/blogs.abo.fi\/ose\/files\/2017\/02\/Westerlund-ESCAPE26.pdf, June (2016)"},{"key":"2157_CR31","doi-asserted-by":"crossref","unstructured":"Nissofolk, O., P\u00f6rn, R., Westerlund, T.: Testing the non-diagonal quadratic convex reformulation technique. In: Proceedings of the 26th European Symposium on Computer Aided Process Engineering-ESCAPE 26, pp. 331\u2013336. Elsevier, June (2016)","DOI":"10.1016\/B978-0-444-63428-3.50060-6"},{"key":"2157_CR32","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s10107-009-0273-x","volume":"126","author":"J Ostrowski","year":"2011","unstructured":"Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 126, 147\u2013178 (2011)","journal-title":"Math. Program."},{"key":"2157_CR33","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S1052623494273393","volume":"7","author":"PM Pardalos","year":"1997","unstructured":"Pardalos, P.M., Ramakrishnan, K.G., Resende, M.G.C., Li, Y.: Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem. SIAM J. Optim. 7, 281\u2013294 (1997)","journal-title":"SIAM J. Optim."},{"key":"2157_CR34","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10107-019-01372-5","volume":"181","author":"FN Permenter","year":"2020","unstructured":"Permenter, F.N., Parrilo, P.A.: Dimension reduction for semidefinite programs via Jordan algebras. Math. Program. 181, 51\u201384 (2020)","journal-title":"Math. Program."},{"key":"2157_CR35","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s12532-018-0140-y","volume":"11","author":"ME Pfetsch","year":"2019","unstructured":"Pfetsch, M.E., T, R.: A computational comparison of symmetry handling methods for mixed integer programs. Math. Program. Comput. 11, 37\u201393 (2019)","journal-title":"Math. Program. Comput."},{"key":"2157_CR36","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."},{"key":"2157_CR37","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0166-218X(87)90022-9","volume":"18","author":"C Roucairol","year":"1987","unstructured":"Roucairol, C.: A parallel branch and bound algorithm for the quadratic assignment problem. Discret. Appl. Math. 18, 211\u2013255 (1987)","journal-title":"Discret. Appl. Math."},{"key":"2157_CR38","volume-title":"A reformulation-linearization technique for solving discrete and continuous nonconvex problems","author":"HD Sherali","year":"2013","unstructured":"Sherali, H.D., Adams, W.P.: A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Springer Science & Business Media, Berlin (2013)"},{"key":"2157_CR39","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1287\/ijoc.2.1.33","volume":"2","author":"J Skorin-Kapov","year":"1990","unstructured":"Skorin-Kapov, J.: Tabu search applied to the quadratic assignment problem. ORSA J. Comput. 2, 33\u201345 (1990)","journal-title":"ORSA J. Comput."},{"key":"2157_CR40","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/S0167-8191(05)80147-4","volume":"17","author":"E Tailard","year":"1991","unstructured":"Tailard, E.: Robust taboo search for the quadratic assignment problem. Parallel Comput. 17, 443\u2013455 (1991)","journal-title":"Parallel Comput."},{"key":"2157_CR41","unstructured":"Wiegele, A.: Biq mac library. http:\/\/www.biqmac.uni-klu.ac.at\/biqmaclib.html, (2007)"},{"key":"2157_CR42","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":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02157-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-024-02157-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02157-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T10:08:12Z","timestamp":1750154892000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-024-02157-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,11]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2157"],"URL":"https:\/\/doi.org\/10.1007\/s11590-024-02157-2","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2024,11,11]]},"assertion":[{"value":"18 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 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 have no conflict of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}