Solving Constrained Slot Placement Problems Using an Ising Machine and Its Evaluations
Solving Constrained Slot Placement Problems Using an Ising Machine and Its Evaluations
复制标题
使用 Ising 机解决约束槽放置问题及其评估
DOI：
10.1587/transinf.2019edp7254
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
N. Togawa
中科院分区：
文献类型：
--
作者：
Sho Kanamaru;Kazushi Kawamura;Shu Tanaka;Yoshinori Tomita;N. Togawa
Ising机器已经引起了人们的注意，期望通过将问题映射到自然现象来高速获得各种组合优化问题的更好的解。插槽布局问题是组合优化问题中的一种，它是一个二次分配问题，涉及到数字电路中逻辑块的最优布局和最优交货计划。在这里，我们提出了一个映射到伊辛模型，用于解决一个插槽放置问题的附加约束，称为约束插槽放置问题，其中几个项目对必须放置在给定的距离内。由于Ising机的行为是随机的，我们将问题映射到使用惩罚方法的Ising模型，所获得的解并不总是满足槽位置约束，这与常规方法如常规模拟退火不同。为了解决这个问题，我们提出了一种解释方法，其中一个可行的解决方案是由后处理程序生成。我们测量了伊辛机的执行时间，并比较了模拟退火的执行时间，其中获得了几乎相同精度的解决方案。结果，我们发现伊辛机比我们实现的模拟退火更快。
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 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.
影响因子：
56.9
作者：
Inagaki, Takahiro;Haribara, Yoshitaka;Takesue, Hiroki
通讯作者：
Takesue, Hiroki