Back to Search
Start Over
An Efficient Closed-Form Formula for Evaluating r-Flip Moves in Quadratic Unconstrained Binary Optimization
- 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