The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Ising 기계는 조합 최적화 문제의 최적 또는 준최적 솔루션을 효율적이고 효과적으로 찾을 수 있습니다. Ising 기계에 좋은 초기 솔루션이 제공되면 최종적으로 최적 솔루션에 가까운 솔루션을 얻을 수 있는 것으로 알려져 있습니다. 그러나 몇몇 Ising 머신은 계산 특성으로 인해 초기 솔루션을 직접 받아들일 수 없습니다. 본 논문에서는 이를 직접적으로 수용할 수 없는 Ising 머신에 준초기 솔루션을 제공하는 방법을 제안합니다. 제안된 방법은 양 또는 음의 외부 자기장 계수를 제공합니다(자기장 제어 용어)을 초기해를 바탕으로 Ising machine을 이용하여 해를 구한다. 그 다음, Ising 기계가 어닐링 과정을 반복할 때마다 자기장 제어 항이 다시 계산되므로, 이전에 얻은 해를 기반으로 해가 반복적으로 개선됩니다. 제안된 방법은 추가적인 제약(constrained CVRP)을 갖는 용량성 차량 경로 문제와 max-cut 문제에 적용된다. 실험 결과, 제한된 CVRP에서는 초기 솔루션에 비해 전체 경로 거리가 평균 5.78% 감소하고, Max-cut 문제에서는 절단 가장자리 무게의 합이 평균 1.25% 증가하는 것으로 나타났습니다.
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
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
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
부
@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},}
부
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 -