{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T06:28:58Z","timestamp":1773037738675,"version":"3.50.1"},"reference-count":34,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T00:00:00Z","timestamp":1701734400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy \u201cflips\u201d r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.<\/jats:p>","DOI":"10.3390\/a16120557","type":"journal-article","created":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T11:27:06Z","timestamp":1701775626000},"page":"557","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Efficient Closed-Form Formula for Evaluating r-Flip Moves in Quadratic Unconstrained Binary Optimization"],"prefix":"10.3390","volume":"16","author":[{"given":"Bahram","family":"Alidaee","sequence":"first","affiliation":[{"name":"School of Business Administration, The University of Mississippi, University, Oxford, MS 38677, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8580-829X","authenticated-orcid":false,"given":"Haibo","family":"Wang","sequence":"additional","affiliation":[{"name":"A.R. S\u00e1nchez Jr. School of Business, Texas A&M International University, Laredo, TX 78041, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4395-865X","authenticated-orcid":false,"given":"Lutfu S.","family":"Sua","sequence":"additional","affiliation":[{"name":"Department of Management and Marketing, Southern University and A&M College, Baton Rouge, LA 70807, USA"}]}],"member":"1968","published-online":{"date-parts":[[2023,12,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0166-218X(98)00114-0","article-title":"Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization","volume":"90","author":"Boros","year":"1999","journal-title":"Discret. Appl. Math."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"97769","DOI":"10.1109\/ACCESS.2023.3313102","article-title":"Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem","volume":"11","author":"Debevre","year":"2023","journal-title":"IEEE Access"},{"key":"ref_3","first-page":"335","article-title":"Quantum Bridge Analytics I: A tutorial on formulating and using QUBO models","volume":"17","author":"Glover","year":"2019","journal-title":"Ann. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1287\/mnsc.44.3.336","article-title":"Adaptive Memory Tabu Search for Binary Quadratic Programs","volume":"44","author":"Glover","year":"1998","journal-title":"Manag. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s10288-009-0115-y","article-title":"Diversification-driven tabu search for unconstrained binary quadratic problems","volume":"8","author":"Glover","year":"2010","journal-title":"4OR"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1504\/IJMHEUR.2010.034201","article-title":"Fast two-flip move evaluations for binary unconstrained quadratic optimisation problems","volume":"1","author":"Glover","year":"2010","journal-title":"Int. J. Metaheuristics"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1007\/s10479-015-2076-1","article-title":"f-Flip strategies for unconstrained binary quadratic programming","volume":"238","author":"Glover","year":"2016","journal-title":"Ann. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","article-title":"The unconstrained binary quadratic programming problem: A survey","volume":"28","author":"Kochenberger","year":"2014","journal-title":"J. Comb. Optim."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Pardalos, P.M., Du, D.-Z., and Graham, R.L. (2013). Handbook of Combinatorial Optimization, Springer.","DOI":"10.1007\/978-1-4419-7997-1"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.ejor.2011.04.018","article-title":"Iterated greedy for the maximum diversity problem","volume":"214","author":"Lozano","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"93","DOI":"10.4018\/jamc.2010102605","article-title":"Theorems Supporting r-flip Search for Pseudo-Boolean Optimization","volume":"1","author":"Alidaee","year":"2010","journal-title":"Int. J. Appl. Metaheuristic Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"104774","DOI":"10.1016\/j.cor.2019.104774","article-title":"Closed-form formulas for evaluating r-flip moves to the unconstrained binary quadratic programming problem","volume":"113","author":"Anacleto","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"105297","DOI":"10.1016\/j.cor.2021.105297","article-title":"Fast r-flip move evaluations via closed-form formulae for Boolean quadraticprogramming problems with generalized upper bound constraints","volume":"132","author":"Anacleto","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1016\/j.ejor.2017.08.025","article-title":"Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems","volume":"265","author":"Glover","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1002\/net.21751","article-title":"Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis","volume":"70","author":"Lewis","year":"2017","journal-title":"Networks"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/S0167-6377(02)00165-7","article-title":"On local search for the generalized graph coloring problem","volume":"31","author":"Vredeveld","year":"2003","journal-title":"Oper. Res. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s10732-013-9227-9","article-title":"Introduction to special xQx issue","volume":"19","author":"Kochenberger","year":"2013","journal-title":"J. Heuristics"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","article-title":"A survey of very large-scale neighborhood search techniques","volume":"123","author":"Ahuja","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1287\/mnsc.1030.0193","article-title":"A Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem","volume":"50","author":"Ahuja","year":"2004","journal-title":"Manag. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1023\/A:1009873324187","article-title":"Analyses on the 2 and 3-Flip Neighborhoods for the MAX SAT","volume":"3","author":"Yagiura","year":"1999","journal-title":"J. Comb. Optim."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1023\/A:1011306011437","article-title":"Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT: Experimental Evaluation","volume":"7","author":"Yagiura","year":"2001","journal-title":"J. Heuristics"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1016\/j.ejor.2004.10.018","article-title":"A 3-flip neighborhood local search for the set covering problem","volume":"172","author":"Yagiura","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","unstructured":"Alidaee, B. (2004). Fan-and-Filter Neighborhood Strategy for 3-SAT Optimization, Hearin Center for Enterprise Science, The University of Mississippi, Hearin Center for Enterprise Science."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Glover, F. (1998). A Template for Scatter Search and Path Relinking, Springer.","DOI":"10.1007\/BFb0026589"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s10898-019-00773-2","article-title":"Variable neighborhood search for stochastic linear programming problem with quantile criterion","volume":"74","author":"Ivanov","year":"2019","journal-title":"J. Glob. Optim."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","article-title":"Variable neighborhood search","volume":"24","author":"Hansen","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.cie.2017.07.012","article-title":"Simple and fast novel diversification approach for the UBQP based on sequential improvement local search","volume":"111","author":"Alidaee","year":"2017","journal-title":"Comput. Ind. Eng."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1023\/B:ANOR.0000039522.58036.68","article-title":"Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem","volume":"131","author":"Palubeckis","year":"2004","journal-title":"Ann. Oper. Res."},{"key":"ref_29","unstructured":"Glen, S. (2023, November 10). Relative Standard Deviation: Definition & Formula. Available online: https:\/\/www.statisticshowto.com\/relative-standard-deviation\/."},{"key":"ref_30","unstructured":"Hart, W., Krasnogor, N., and Smith, J.E. (2004). An Evolutionary Approach for the Maximum Diversity Problem, Springer. Recent Advances in Memetic Algorithms."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"106324","DOI":"10.1016\/j.cor.2023.106324","article-title":"Fast 1-flip neighborhood evaluations for large-scale pseudo-Boolean optimization using posiform representation","volume":"159","author":"Liang","year":"2023","journal-title":"Comput. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1023\/A:1017912624016","article-title":"Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming","volume":"8","author":"Merz","year":"2002","journal-title":"J. Heuristics"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1007\/s10589-016-9844-y","article-title":"Building an iterative heuristic solver for a quantum annealer","volume":"65","author":"Rosenberg","year":"2016","journal-title":"Comput. Optim. Appl."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Alidaee, B., Wang, H., and Liu, W. (2022). New Results on Closed-Form Formulas for Evaluating r-flip Moves in Quadratic Unconstrained Binary Optimization, Texas A&M International University. Working Paper Series, WP 2021-002.","DOI":"10.20944\/preprints202311.1096.v1"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/12\/557\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:33:45Z","timestamp":1760132025000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/12\/557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,5]]},"references-count":34,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["a16120557"],"URL":"https:\/\/doi.org\/10.3390\/a16120557","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,5]]}}}