
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Solving Constrained Slot Placement Problems Using an Ising Machine and Its Evaluations
Sho KANAMARU Kazushi KAWAMURA Shu TANAKA Yoshinori TOMITA Nozomu TOGAWA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E104D
No.2
pp.226236 Publication Date: 2021/02/01 Publicized: 2020/11/09 Online ISSN: 17451361
DOI: 10.1587/transinf.2019EDP7254 Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: Ising machine, Ising model, slotplacement problem, quadratic assignment problem, quadratic unconstrained binary optimization,
Full Text: PDF>>
Summary:
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 slotplacement problem is one of the combinatorial optimization problems, regarded as a quadratic assignment problem, which relates to the optimal logicblock placement in a digital circuit as well as optimal delivery planning. Here, we propose a mapping to the Ising model for solving a slotplacement problem with additional constraints, called a constrained slotplacement 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 slotplacement 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 postprocessing 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.


