Giving a Quasi-Initial Solution to Ising Machines by Controlling External Magnetic Field Coefficients

Soma KAWAKAMI; Kentaro OHNO; Dema BA; Satoshi YAGI; Junji TERAMOTO; Nozomu TOGAWA

doi:10.1587/transfun.2023KEP0004

IEICE TRANSACTIONS on Fundamentals

Giving a Quasi-Initial Solution to Ising Machines by Controlling External Magnetic Field Coefficients

Soma KAWAKAMI, Kentaro OHNO, Dema BA, Satoshi YAGI, Junji TERAMOTO, Nozomu TOGAWA

Full Text Views

0

Cite this

Summary :

Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. It is known that, when a good initial solution is given to an Ising machine, we can finally obtain a solution closer to the optimal solution. However, several Ising machines cannot directly accept an initial solution due to its computational nature. In this paper, we propose a method to give quasi-initial solutions into Ising machines that cannot directly accept them. The proposed method gives the positive or negative external magnetic field coefficients (magnetic field controlling term) based on the initial solutions and obtains a solution by using an Ising machine. Then, the magnetic field controlling term is re-calculated every time an Ising machine repeats the annealing process, and hence the solution is repeatedly improved on the basis of the previously obtained solution. The proposed method is applied to the capacitated vehicle routing problem with an additional constraint (constrained CVRP) and the max-cut problem. Experimental results show that the total path distance is reduced by 5.78% on average compared to the initial solution in the constrained CVRP and the sum of cut-edge weight is increased by 1.25% on average in the max-cut problem.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.1 pp.52-62

Publication Date: 2024/01/01

Publicized: 2023/08/16

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2023KEP0004

Type of Manuscript: Special Section PAPER (Special Section on Circuits and Systems)

Category

Authors

Soma KAWAKAMI
  Waseda University
Kentaro OHNO
  Nippon Telegraph and Telephone Corporation
Dema BA
  Nippon Telegraph and Telephone Corporation
Satoshi YAGI
  Nippon Telegraph and Telephone Corporation
Junji TERAMOTO
  Nippon Telegraph and Telephone Corporation
Nozomu TOGAWA
  Waseda University

Keyword

Ising machine, initial solution, constrained CVRP, max-cut problem

Cite this

Copy

Soma KAWAKAMI, Kentaro OHNO, Dema BA, Satoshi YAGI, Junji TERAMOTO, Nozomu TOGAWA, "Giving a Quasi-Initial Solution to Ising Machines by Controlling External Magnetic Field Coefficients" in IEICE TRANSACTIONS on Fundamentals, vol. E107-A, no. 1, pp. 52-62, January 2024, doi: 10.1587/transfun.2023KEP0004.
Abstract: Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. It is known that, when a good initial solution is given to an Ising machine, we can finally obtain a solution closer to the optimal solution. However, several Ising machines cannot directly accept an initial solution due to its computational nature. In this paper, we propose a method to give quasi-initial solutions into Ising machines that cannot directly accept them. The proposed method gives the positive or negative external magnetic field coefficients (magnetic field controlling term) based on the initial solutions and obtains a solution by using an Ising machine. Then, the magnetic field controlling term is re-calculated every time an Ising machine repeats the annealing process, and hence the solution is repeatedly improved on the basis of the previously obtained solution. The proposed method is applied to the capacitated vehicle routing problem with an additional constraint (constrained CVRP) and the max-cut problem. Experimental results show that the total path distance is reduced by 5.78% on average compared to the initial solution in the constrained CVRP and the sum of cut-edge weight is increased by 1.25% on average in the max-cut problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2023KEP0004/_p

Copy

@ARTICLE{e107-a_1_52,
author={Soma KAWAKAMI, Kentaro OHNO, Dema BA, Satoshi YAGI, Junji TERAMOTO, Nozomu TOGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Giving a Quasi-Initial Solution to Ising Machines by Controlling External Magnetic Field Coefficients},
year={2024},
volume={E107-A},
number={1},
pages={52-62},
abstract={Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. It is known that, when a good initial solution is given to an Ising machine, we can finally obtain a solution closer to the optimal solution. However, several Ising machines cannot directly accept an initial solution due to its computational nature. In this paper, we propose a method to give quasi-initial solutions into Ising machines that cannot directly accept them. The proposed method gives the positive or negative external magnetic field coefficients (magnetic field controlling term) based on the initial solutions and obtains a solution by using an Ising machine. Then, the magnetic field controlling term is re-calculated every time an Ising machine repeats the annealing process, and hence the solution is repeatedly improved on the basis of the previously obtained solution. The proposed method is applied to the capacitated vehicle routing problem with an additional constraint (constrained CVRP) and the max-cut problem. Experimental results show that the total path distance is reduced by 5.78% on average compared to the initial solution in the constrained CVRP and the sum of cut-edge weight is increased by 1.25% on average in the max-cut problem.},
keywords={},
doi={10.1587/transfun.2023KEP0004},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Giving a Quasi-Initial Solution to Ising Machines by Controlling External Magnetic Field Coefficients
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 52
EP - 62
AU - Soma KAWAKAMI
AU - Kentaro OHNO
AU - Dema BA
AU - Satoshi YAGI
AU - Junji TERAMOTO
AU - Nozomu TOGAWA
PY - 2024
DO - 10.1587/transfun.2023KEP0004
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E107-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2024
AB - Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. It is known that, when a good initial solution is given to an Ising machine, we can finally obtain a solution closer to the optimal solution. However, several Ising machines cannot directly accept an initial solution due to its computational nature. In this paper, we propose a method to give quasi-initial solutions into Ising machines that cannot directly accept them. The proposed method gives the positive or negative external magnetic field coefficients (magnetic field controlling term) based on the initial solutions and obtains a solution by using an Ising machine. Then, the magnetic field controlling term is re-calculated every time an Ising machine repeats the annealing process, and hence the solution is repeatedly improved on the basis of the previously obtained solution. The proposed method is applied to the capacitated vehicle routing problem with an additional constraint (constrained CVRP) and the max-cut problem. Experimental results show that the total path distance is reduced by 5.78% on average compared to the initial solution in the constrained CVRP and the sum of cut-edge weight is increased by 1.25% on average in the max-cut problem.
ER -

IEICE TRANSACTIONS on Fundamentals