コンテンツメニュー

Constructing the neighborhood structure of VNS based on binomial distribution for solving QUBO problems

Algorithms Volume 15 Issue 6 Page 192-
published_at 2022-06-02
2022-6-2-20-11algorithms-15-00192.pdf
938 KB
Title
Constructing the neighborhood structure of VNS based on binomial distribution for solving QUBO problems
Abstract
The quadratic unconstrained binary optimization (QUBO) problem is categorized as an NP-hard combinatorial optimization problem. The variable neighborhood search (VNS) algorithm is one of the leading algorithms used to solve QUBO problems. As neighborhood structure change is the central concept in the VNS algorithm, the design of the neighborhood structure is crucial. This paper presents a modified VNS algorithm called "B-VNS", which can be used to solve QUBO problems. A binomial trial was used to construct the neighborhood structure, and this was used with the aim of reducing computation time. The B-VNS and VNS algorithms were tested on standard QUBO problems from Glover and Beasley, on standard max-cut problems from Helmberg-Rendl, and on those proposed by Burer, Monteiro, and Zhang. Finally, Mann-Whitney tests were conducted using α = 0.05, to statistically compare the performance of the two algorithms. It was shown that the B-VNS and VNS algorithms are able to provide good solutions, but the B-VNS algorithm runs substantially faster. Furthermore, the B-VNS algorithm performed the best in all of the max-cut problems, regardless of problem size, and it performed the best in QUBO problems, with sizes less than 500. The results suggest that the use of binomial distribution, to construct the neighborhood structure, has the potential for further development.
Creators Pambudi Dhidhi
Creators Kawamura Masaki
Affiliate Master Yamaguchi University
[kakenhi]15501 grid.268397.1
Source Identifiers [EISSN] 1999-4893
Creator Keywords
QUBO max-cut VNS neighborhood binomial
Languages eng
Resource Type journal article
Publishers Multidisciplinary Digital Publishing Institute
Date Issued 2022-06-02
Rights
Creative Commons Attribution 4.0 International(https://creativecommons.org/licenses/by/4.0/deed.en)
File Version Version of Record
Access Rights open access
Relations
[isIdenticalTo] https://doi.org/10.3390/a15060192
Funding Refs
Japan Society for the Promotion of Science [crossref_funder]https://doi.org/10.13039/501100001691
Award High-resistance information hiding method applied associative memory models 20K11973