TY - GEN
T1 - A multiple coefficients trial method to solve combinatorial optimization problems for simulated-annealing-based ising machines
AU - Takehara, Kota
AU - Oku, Daisuke
AU - Matsuda, Yoshiki
AU - Tanaka, Shu
AU - Togawa, Nozomu
N1 - Funding Information:
This article is based on results obtained from a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO).
Publisher Copyright:
© 2019 IEEE.
PY - 2019/9
Y1 - 2019/9
N2 - When solving a combinatorial optimization problem with Ising machines, we have to formulate it onto an energy function of Ising model. Here, how to determine the penalty coefficients in the energy function is a great concern if it includes constraint terms. In this paper, we focus on a traveling salesman problem (TSP, in short), one of the combinatorial optimization problems with equality constraints. Firstly, we investigate the relationship between the penalty coefficient and the accuracy of solutions in a TSP. Based on it, we propose a method to obtain a TSP quasi-optimum solution, which is called multiple coefficients trial method. In our proposed method, we use an Ising machine to solve a TSP by changing a penalty coefficient every trial, the TSP solutions can converge very fast in total. Compared to naive methods using simulated-annealing-based Ising machines, we confirmed that our proposed method can reduce the total number of annealing iterations to 1/10 to 1/1000 to obtain a quasi-optimum solution in 32-city TSPs.
AB - When solving a combinatorial optimization problem with Ising machines, we have to formulate it onto an energy function of Ising model. Here, how to determine the penalty coefficients in the energy function is a great concern if it includes constraint terms. In this paper, we focus on a traveling salesman problem (TSP, in short), one of the combinatorial optimization problems with equality constraints. Firstly, we investigate the relationship between the penalty coefficient and the accuracy of solutions in a TSP. Based on it, we propose a method to obtain a TSP quasi-optimum solution, which is called multiple coefficients trial method. In our proposed method, we use an Ising machine to solve a TSP by changing a penalty coefficient every trial, the TSP solutions can converge very fast in total. Compared to naive methods using simulated-annealing-based Ising machines, we confirmed that our proposed method can reduce the total number of annealing iterations to 1/10 to 1/1000 to obtain a quasi-optimum solution in 32-city TSPs.
KW - Combinatorial optimization problem
KW - Ising machine
KW - Penalty coefficient
KW - Quadratic Unconstrained Binary Optimization
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=85078940876&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078940876&partnerID=8YFLogxK
U2 - 10.1109/ICCE-Berlin47944.2019.8966167
DO - 10.1109/ICCE-Berlin47944.2019.8966167
M3 - Conference contribution
AN - SCOPUS:85078940876
T3 - IEEE International Conference on Consumer Electronics - Berlin, ICCE-Berlin
SP - 64
EP - 69
BT - Proceedings - 2019 IEEE 9th International Conference on Consumer Electronics, ICCE-Berlin 2019
A2 - Velikic, Gordan
A2 - Gross, Christian
PB - IEEE Computer Society
T2 - 9th IEEE International Conference on Consumer Electronics, ICCE-Berlin 2019
Y2 - 8 September 2019 through 11 September 2019
ER -