著者
Sho KANAMARU Kazushi KAWAMURA Shu TANAKA Yoshinori TOMITA Nozomu TOGAWA
出版者
The Institute of Electronics, Information and Communication Engineers
雑誌
IEICE TRANSACTIONS on Information and Systems (ISSN:09168532)
巻号頁・発行日
vol.E104-D, no.2, pp.226-236, 2021-02-01
被引用文献数
4

Ising machines have attracted attention, which is expected to obtain better solutions of various combinatorial optimization problems at high speed by mapping the problems to natural phenomena. A slot-placement problem is one of the combinatorial optimization problems, regarded as a quadratic assignment problem, which relates to the optimal logic-block placement in a digital circuit as well as optimal delivery planning. Here, we propose a mapping to the Ising model for solving a slot-placement problem with additional constraints, called a constrained slot-placement problem, where several item pairs must be placed within a given distance. Since the behavior of Ising machines is stochastic and we map the problem to the Ising model which uses the penalty method, the obtained solution does not always satisfy the slot-placement constraint, which is different from the conventional methods such as the conventional simulated annealing. To resolve the problem, we propose an interpretation method in which a feasible solution is generated by post-processing procedures. We measured the execution time of an Ising machine and compared the execution time of the simulated annealing in which solutions with almost the same accuracy are obtained. As a result, we found that the Ising machine is faster than the simulated annealing that we implemented.

言及状況

外部データベース (DOI)

Twitter (1 users, 1 posts, 18 favorites)

大学院時代に書いた論文がIEICEの論文誌に掲載されました! イジングマシンを用いて組合せ最適化問題を高速かつ高精度に解く研究です! https://t.co/LR3QO6fpaY

収集済み URL リスト