TY - GEN
T1 - QUBO Matrix Distorting Method for Consumer Applications
AU - Yoshimura, Tomokazu
AU - Shirai, Tatsuhiko
AU - Tawada, Masashi
AU - Togawa, Nozomu
N1 - Funding Information:
ACKNOWLEDGMENTS This work was supported in part by JST CREST Grant Number JPMJCR19K4, Japan.
Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - We propose a Quadratic Unconstrained Binary Optimization (QUBO) matrix distorting method to solve combinatorial optimization problems, which are very often seen in consumer applications, with high speed and high accuracy. Combinatorial optimization problems are formulated as the problems of finding the ground state of the energy function determined by the QUBO matrix. The proposed method consists of the local optimization and the distortion of the energy function by adding a constant to each QUBO matrix element with a certain probability. The probability is initially large, decreased during the method linearly, and zero at the end. The distortion process aims to make a local optimal solution to be no longer a local optimum and avoid staying in the local optimal solution with a probability. We apply the proposed method to the graph partitioning problem as a typical combinatorial optimization problem with many local optimal solutions and large energy barriers among them. We verify the effectiveness of the proposed method against the iterative improvement method and the simulated annealing.
AB - We propose a Quadratic Unconstrained Binary Optimization (QUBO) matrix distorting method to solve combinatorial optimization problems, which are very often seen in consumer applications, with high speed and high accuracy. Combinatorial optimization problems are formulated as the problems of finding the ground state of the energy function determined by the QUBO matrix. The proposed method consists of the local optimization and the distortion of the energy function by adding a constant to each QUBO matrix element with a certain probability. The probability is initially large, decreased during the method linearly, and zero at the end. The distortion process aims to make a local optimal solution to be no longer a local optimum and avoid staying in the local optimal solution with a probability. We apply the proposed method to the graph partitioning problem as a typical combinatorial optimization problem with many local optimal solutions and large energy barriers among them. We verify the effectiveness of the proposed method against the iterative improvement method and the simulated annealing.
KW - global optimization
KW - graph partitioning problem
KW - Ising model
KW - iterative improvement
KW - local optimal solution
KW - QUBO
KW - simulated annealing
UR - http://www.scopus.com/inward/record.url?scp=85127078751&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85127078751&partnerID=8YFLogxK
U2 - 10.1109/ICCE53296.2022.9730763
DO - 10.1109/ICCE53296.2022.9730763
M3 - Conference contribution
AN - SCOPUS:85127078751
T3 - Digest of Technical Papers - IEEE International Conference on Consumer Electronics
BT - 2022 IEEE International Conference on Consumer Electronics, ICCE 2022
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2022 IEEE International Conference on Consumer Electronics, ICCE 2022
Y2 - 7 January 2022 through 9 January 2022
ER -