The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E104-D No.2 pp.226-236

- Publication Date
- 2021/02/01

- Publicized
- 2020/11/09

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2019EDP7254

- Type of Manuscript
- PAPER

- Category
- Fundamentals of Information Systems

Sho KANAMARU

Waseda University

Kazushi KAWAMURA

Waseda University

Shu TANAKA

Waseda University,Japan Science and Technology Agency

Yoshinori TOMITA

Fujitsu Laboratories Ltd.

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.

Copy

Sho KANAMARU, Kazushi KAWAMURA, Shu TANAKA, Yoshinori TOMITA, Nozomu TOGAWA, "Solving Constrained Slot Placement Problems Using an Ising Machine and Its Evaluations" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 2, pp. 226-236, February 2021, doi: 10.1587/transinf.2019EDP7254.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7254/_p

Copy

@ARTICLE{e104-d_2_226,

author={Sho KANAMARU, Kazushi KAWAMURA, Shu TANAKA, Yoshinori TOMITA, Nozomu TOGAWA, },

journal={IEICE TRANSACTIONS on Information},

title={Solving Constrained Slot Placement Problems Using an Ising Machine and Its Evaluations},

year={2021},

volume={E104-D},

number={2},

pages={226-236},

abstract={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.},

keywords={},

doi={10.1587/transinf.2019EDP7254},

ISSN={1745-1361},

month={February},}

Copy

TY - JOUR

TI - Solving Constrained Slot Placement Problems Using an Ising Machine and Its Evaluations

T2 - IEICE TRANSACTIONS on Information

SP - 226

EP - 236

AU - Sho KANAMARU

AU - Kazushi KAWAMURA

AU - Shu TANAKA

AU - Yoshinori TOMITA

AU - Nozomu TOGAWA

PY - 2021

DO - 10.1587/transinf.2019EDP7254

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E104-D

IS - 2

JA - IEICE TRANSACTIONS on Information

Y1 - February 2021

AB - 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.

ER -