{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T01:58:41Z","timestamp":1773107921357,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,27]],"date-time":"2025-12-27T00:00:00Z","timestamp":1766793600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,27]],"date-time":"2025-12-27T00:00:00Z","timestamp":1766793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JP21H04599"],"award-info":[{"award-number":["JP21H04599"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Tabu Search is a promising approach for solving quadratic unconstrained binary optimization (QUBO) problems. A key parameter in Tabu Search is tabu tenure, which governs the balance between intensification and diversification in the search process. In this work, we aim to develop a systematic method for determining the effective tabu tenure tailored to each QUBO instance, thereby enhancing overall solver performance. To achieve this, we focus on the statistics obtained during the search, which we term \u201ctrajectory metrics.\u201d We consolidate existing trajectory metrics from the literature with newly proposed ones and analyze their responses to variations in tabu tenure using three criteria: suitability for tuning, noise robustness, and classification potential. Based on this analysis, we introduce a method for determining the effective tabu tenure and evaluate its performance across several problem instances. Experimental results demonstrate that the proposed approach improves solving performance compared to a well-known standard Tabu Search-based method.<\/jats:p>","DOI":"10.1007\/s10732-025-09576-z","type":"journal-article","created":{"date-parts":[[2025,12,27]],"date-time":"2025-12-27T14:19:19Z","timestamp":1766845159000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Automated Tabu Tenure Tuning by Trajectory Metrics for Quadratic Unconstrained Binary Optimization"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8117-9752","authenticated-orcid":false,"given":"Masahiko","family":"Sugimura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4696-2881","authenticated-orcid":false,"given":"Keiichiro","family":"Yamamura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4979-5276","authenticated-orcid":false,"given":"Hiroki","family":"Ishikura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9873-5176","authenticated-orcid":false,"given":"Akihiro","family":"Yoshida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3588-0196","authenticated-orcid":false,"given":"Ken","family":"Kawano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5777-7756","authenticated-orcid":false,"given":"Matthieu","family":"Parizy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8549-641X","authenticated-orcid":false,"given":"Katsuki","family":"Fujisawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,27]]},"reference":[{"key":"9576_CR1","unstructured":"Beasley, J.E.: Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical report, Working Paper, The Management School, Imperial College, London, England (1998)"},{"key":"9576_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10732-007-9009-3","volume":"13","author":"E Boros","year":"2007","unstructured":"Boros, E., Hammer, P.L., Tavares, G.: Local search heuristics for quadratic unconstrained binary optimization (qubo). J. Heuristics 13, 99\u2013132 (2007)","journal-title":"J. Heuristics"},{"key":"9576_CR3","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1023\/A:1008293323270","volume":"10","author":"RE Burkard","year":"1997","unstructured":"Burkard, R.E., Karisch, S.E., Rendl, F.: Qaplib-a quadratic assignment problem library. J. Global Optim. 10, 391\u2013403 (1997)","journal-title":"J. Global Optim."},{"issue":"1","key":"9576_CR4","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0377-2217(94)90125-2","volume":"78","author":"A Billionnet","year":"1994","unstructured":"Billionnet, A., Sutter, A.: Minimization of a quadratic pseudo-boolean function. Eur. J. Oper. Res. 78(1), 106\u2013115 (1994)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"9576_CR5","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1287\/ijoc.6.2.126","volume":"6","author":"R Battiti","year":"1994","unstructured":"Battiti, R., Tecchiolli, G.: The reactive tabu search. ORSA J. Comput. 6(2), 126\u2013140 (1994)","journal-title":"ORSA J. Comput."},{"key":"9576_CR6","doi-asserted-by":"crossref","unstructured":"Birattari, M., Yuan, Z., Balaprakash, P., St\u00fctzle, T.: F-race and iterated f-race: An overview. Exp. Methods Anal. Optim. Alg. 311\u2013336 (2010)","DOI":"10.1007\/978-3-642-02538-9_13"},{"key":"9576_CR7","unstructured":"DIMACS: Graph coloring instances, standard format. URL https:\/\/mat.tepper.cmu.edu\/COLOR\/instances.html (2010)"},{"key":"9576_CR8","doi-asserted-by":"crossref","unstructured":"Devarenne, I., Mabed, H., Caminada, A.: Adaptive tabu tenure computation in local search. In: Evolutionary Computation in Combinatorial Optimization: 8th European Conference (EvoCOP), pp. 1\u201312 (2008). Springer","DOI":"10.1007\/978-3-540-78604-7_1"},{"key":"9576_CR9","doi-asserted-by":"crossref","unstructured":"Duque, J., M\u00fanera, D.A., D\u00edaz, D., Abreu, S.: Solving qap with auto-parameterization in parallel hybrid metaheuristics. In: International Conference on Optimization and Learning, pp. 294\u2013309 (2021). Springer","DOI":"10.1007\/978-3-030-85672-4_22"},{"key":"9576_CR10","doi-asserted-by":"crossref","unstructured":"Debevere, P., Sugimura, M., Parizy, M.: Quadratic unconstrained binary optimization for the automotive paint shop problem. IEEE Access (2023)","DOI":"10.1109\/ACCESS.2023.3313102"},{"key":"9576_CR11","volume-title":"Signal Detection Theory and ROC Analysis","author":"JP Egan","year":"1975","unstructured":"Egan, J.P.: Signal Detection Theory and ROC Analysis. Academic Press Inc., Cambridge (1975)"},{"issue":"2","key":"9576_CR12","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1287\/ijoc.11.2.198","volume":"11","author":"C Fleurent","year":"1999","unstructured":"Fleurent, C., Glover, F.: Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. Informs J. Comput. 11(2), 198\u2013204 (1999)","journal-title":"Informs J. Comput."},{"key":"9576_CR13","doi-asserted-by":"crossref","unstructured":"Francesca, G., Pellegrini, P., St\u00fctzle, T., Birattari, M.: Off-line and on-line tuning: a study on operator selection for a memetic algorithm applied to the qap. In: Evolutionary Computation in Combinatorial Optimization: 11th European Conference (EvoCOP), pp. 203\u2013214 (2011). Springer","DOI":"10.1007\/978-3-642-20364-0_18"},{"issue":"2","key":"9576_CR14","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.cie.2010.11.014","volume":"60","author":"N Fescioglu-Unver","year":"2011","unstructured":"Fescioglu-Unver, N., Kokar, M.M.: Self controlling tabu search algorithm for the quadratic assignment problem. Comput. Ind. Eng. 60(2), 310\u2013319 (2011)","journal-title":"Comput. Ind. Eng."},{"key":"9576_CR15","doi-asserted-by":"crossref","unstructured":"Garc\u00eda, M.D., Ayodele, M., Moraglio, A.: Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer. In: The Genetic and Evolutionary Computation Conference (GECCO), pp. 184\u2013187 (2022)","DOI":"10.1145\/3520304.3528925"},{"issue":"3","key":"9576_CR16","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1287\/mnsc.44.3.336","volume":"44","author":"F Glover","year":"1998","unstructured":"Glover, F., Kochenberger, G.A., Alidaee, B.: Adaptive memory tabu search for binary quadratic programs. Manage. Sci. 44(3), 336\u2013345 (1998)","journal-title":"Manage. Sci."},{"issue":"4","key":"9576_CR17","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10288-019-00424-y","volume":"17","author":"F Glover","year":"2019","unstructured":"Glover, F., Kochenberger, G., Du, Y.: Quantum bridge analytics i: a tutorial on formulating and using qubo models. 4OR 17(4), 335\u2013371 (2019)","journal-title":"4OR"},{"key":"9576_CR18","first-page":"3261","volume":"21","author":"F Glover","year":"2013","unstructured":"Glover, F., Laguna, M.: Tabu search: effective strategies for hard problems in analytics and computational science. Handbook Comb. Optim. 21, 3261\u20133362 (2013)","journal-title":"Handbook Comb. Optim."},{"key":"9576_CR19","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10288-009-0115-y","volume":"8","author":"F Glover","year":"2010","unstructured":"Glover, F., L\u00fc, Z., Hao, J.-K.: Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR 8, 239\u2013253 (2010)","journal-title":"4OR"},{"issue":"5","key":"9576_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F Glover","year":"1986","unstructured":"Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533\u2013549 (1986)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"9576_CR21","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover, F.: Tabu search\u2013part i. ORSA J. Comput. 1(3), 190\u2013206 (1989)","journal-title":"ORSA J. Comput."},{"issue":"1","key":"9576_CR22","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1287\/ijoc.2.1.4","volume":"2","author":"F Glover","year":"1990","unstructured":"Glover, F.: Tabu search\u2013part ii. ORSA J. Comput. 2(1), 4\u201332 (1990)","journal-title":"ORSA J. Comput."},{"issue":"3","key":"9576_CR23","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s10732-016-9312-y","volume":"22","author":"F Glover","year":"2016","unstructured":"Glover, F.: Multi-wave algorithms for metaheuristic optimization. J. Heuristics 22(3), 331\u2013358 (2016)","journal-title":"J. Heuristics"},{"issue":"3","key":"9576_CR24","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0360-8352(00)00043-7","volume":"38","author":"M Hasan","year":"2000","unstructured":"Hasan, M., Alkhamis, T., Ali, J.: A comparison between simulated annealing, genetic algorithm and tabu search methods for the unconstrained quadratic pseudo-boolean function. Comput. Ind. Eng. 38(3), 323\u2013340 (2000)","journal-title":"Comput. Ind. Eng."},{"key":"9576_CR25","doi-asserted-by":"crossref","unstructured":"Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Learning and Intelligent Optimization: 5th International Conference, pp. 507\u2013523 (2011). Springer","DOI":"10.1007\/978-3-642-25566-3_40"},{"key":"9576_CR26","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1613\/jair.2861","volume":"36","author":"F Hutter","year":"2009","unstructured":"Hutter, F., Hoos, H.H., Leyton-Brown, K., St\u00fctzle, T.: Paramils: an automatic algorithm configuration framework. J. Artif. Intell. Res. 36, 267\u2013306 (2009)","journal-title":"J. Artif. Intell. Res."},{"key":"9576_CR27","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s10589-005-3062-3","volume":"33","author":"H-X Huang","year":"2006","unstructured":"Huang, H.-X., Pardalos, P.M., Prokopyev, O.A.: Lower bound improvement and forcing rule for quadratic binary programming. Comput. Optim. Appl. 33, 187\u2013208 (2006)","journal-title":"Comput. Optim. Appl."},{"key":"9576_CR28","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01580072","volume":"82","author":"C Helmberg","year":"1998","unstructured":"Helmberg, C., Rendl, F.: Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes. Math. Program. 82, 291\u2013315 (1998)","journal-title":"Math. Program."},{"issue":"7346","key":"9576_CR29","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson, M.W., Amin, M.H., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Johansson, J., Bunyk, P., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194\u2013198 (2011)","journal-title":"Nature"},{"key":"9576_CR30","volume-title":"Valuation of Network Effects in Software Markets: A Complex Networks Approach","author":"A Kemper","year":"2009","unstructured":"Kemper, A.: Valuation of Network Effects in Software Markets: A Complex Networks Approach. Physica Heidelberg, Heidelberg (2009)"},{"issue":"2","key":"9576_CR31","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s00291-003-0153-3","volume":"26","author":"GA Kochenberger","year":"2004","unstructured":"Kochenberger, G.A., Glover, F., Alidaee, B., Rego, C.: A unified modeling and solution framework for combinatorial optimization problems. OR Spectrum 26(2), 237\u2013250 (2004)","journal-title":"OR Spectrum"},{"issue":"3","key":"9576_CR32","doi-asserted-by":"publisher","first-page":"1254","DOI":"10.1016\/j.ejor.2010.06.039","volume":"207","author":"Z L\u00fc","year":"2010","unstructured":"L\u00fc, Z., Glover, F., Hao, J.-K.: A hybrid metaheuristic approach to solving the ubqp problem. Eur. J. Oper. Res. 207(3), 1254\u20131262 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"9576_CR33","doi-asserted-by":"publisher","first-page":"74887","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many np problems. Front. Phys. 2, 74887 (2014)","journal-title":"Front. Phys."},{"key":"9576_CR34","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10589-005-4562-x","volume":"30","author":"A Misevi\u010dius","year":"2005","unstructured":"Misevi\u010dius, A.: A tabu search algorithm for the quadratic assignment problem. Comput. Optim. Appl. 30, 95\u2013111 (2005)","journal-title":"Comput. Optim. Appl."},{"key":"9576_CR35","unstructured":"Misevi\u010dius, A., Ostreika, A.: Defining tabu tenure for the quadratic assignment problem. Inf. Technol. Contr. 36(4), (2007)"},{"key":"9576_CR36","unstructured":"Nakayama, H., Koyama, J., Yoneoka, N., Miyazawa, T.: Description: Third generation digital annealer technology. Preprint at https:\/\/www.fujitsu.com\/jp\/documents\/digitalannealer\/researcharticles\/DA_WP_EN_20210922.pdf (2021)"},{"key":"9576_CR37","doi-asserted-by":"crossref","unstructured":"Parizy, M., Kakuko, N., Togawa, N.: Fast hyperparameter tuning for ising machines. In: 2023 IEEE International Conference on Consumer Electronics (ICCE), pp. 1\u20136 (2023). IEEE","DOI":"10.1109\/ICCE56470.2023.10043382"},{"key":"9576_CR38","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.asoc.2017.11.014","volume":"63","author":"A Said","year":"2018","unstructured":"Said, A., Abbasi, R.A., Maqbool, O., Daud, A., Aljohani, N.R.: Cc-ga: A clustering coefficient based genetic algorithm for detecting communities in social networks. Appl. Soft Comput. 63, 59\u201370 (2018)","journal-title":"Appl. Soft Comput."},{"key":"9576_CR39","doi-asserted-by":"crossref","unstructured":"Sugimura, M., Parizy, M.: A3tum: Automated tabu tenure tuning by unique move for quadratic unconstrained binary optimization. In: The Genetic and Evolutionary Computation Conference (GECCO), pp. 1963\u20131971 (2024)","DOI":"10.1145\/3638530.3664111"},{"issue":"4\u20135","key":"9576_CR40","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/S0167-8191(05)80147-4","volume":"17","author":"\u00c9 Taillard","year":"1991","unstructured":"Taillard, \u00c9.: Robust taboo search for the quadratic assignment problem. Parallel Comput. 17(4\u20135), 443\u2013455 (1991)","journal-title":"Parallel Comput."},{"key":"9576_CR41","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.physa.2013.09.010","volume":"394","author":"BM Tabak","year":"2014","unstructured":"Tabak, B.M., Takami, M., Rocha, J.M., Cajueiro, D.O., Souza, S.R.: Directed clustering coefficient as a measure of systemic risk in complex banking networks. Phys. A 394, 211\u2013216 (2014)","journal-title":"Phys. A"},{"key":"9576_CR42","unstructured":"Wiegele, A.: Biq Mac Library\u2014A collection of Max-Cut and quadratic 0-1 programming instances of medium size. URL https:\/\/biqmac.aau.at\/biqmaclib.html (2007)"},{"issue":"3","key":"9576_CR43","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.ejor.2012.07.012","volume":"223","author":"Y Wang","year":"2012","unstructured":"Wang, Y., L\u00fc, Z., Glover, F., Hao, J.-K.: Path relinking for unconstrained binary quadratic programming. Eur. J. Oper. Res. 223(3), 595\u2013604 (2012)","journal-title":"Eur. J. Oper. Res."},{"key":"9576_CR44","unstructured":"Ye, Y.: Gset max-cut problem set. URL https:\/\/web.stanford.edu\/~yyye\/yyye\/Gset\/ (2003)"},{"key":"9576_CR45","unstructured":"Yamamura, K., Sato, H., Tateiwa, N., Hata, N., Mitsutake, T., Oe, I., Ishikura, H., Fujisawa, K.: Diversified adversarial attacks based on conjugate gradient method. In: Forty-Second International Conference on Machine Learning (ICML), pp. 24872\u201324894 (2022). PMLR"},{"key":"9576_CR46","doi-asserted-by":"crossref","unstructured":"Yoshimura, C., Yamaoka, M., Aoki, H., Mizuno, H.: Spatial computing architecture using randomness of memory cell stability under voltage control. In: 2013 European Conference on Circuit Theory and Design (ECCTD), pp. 1\u20134 (2013). IEEE","DOI":"10.1109\/ECCTD.2013.6662276"},{"key":"9576_CR47","doi-asserted-by":"crossref","unstructured":"Yamaoka, M., Yoshimura, C., Hayashi, M., Okuyama, T., Aoki, H., Mizuno, H.: 24.3 20k-spin ising chip for combinational optimization problem with cmos annealing. In: 2015 IEEE International Solid-State Circuits Conference (ISSCC) Digest of Technical Papers, pp. 1\u20133 (2015). IEEE","DOI":"10.1109\/ISSCC.2015.7063111"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-025-09576-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-025-09576-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-025-09576-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T14:21:50Z","timestamp":1773066110000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-025-09576-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,27]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["9576"],"URL":"https:\/\/doi.org\/10.1007\/s10732-025-09576-z","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,27]]},"assertion":[{"value":"5 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2025","order":4,"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 competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"4"}}