Back to Search Start Over

An Efficient Closed-Form Formula for Evaluating r-Flip Moves in Quadratic Unconstrained Binary Optimization

Authors :
Bahram Alidaee
Haibo Wang
Lutfu S. Sua
Source :
Algorithms, Vol 16, Iss 12, p 557 (2023)
Publication Year :
2023
Publisher :
MDPI AG, 2023.

Abstract

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 “flips” 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.

Details

Language :
English
ISSN :
19994893
Volume :
16
Issue :
12
Database :
Directory of Open Access Journals
Journal :
Algorithms
Publication Type :
Academic Journal
Accession number :
edsdoj.313d26896c864fe496da80ebbe00b21e
Document Type :
article
Full Text :
https://doi.org/10.3390/a16120557