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
Vues en texte intégral
96
Le problème du sac à dos quadratique binaire (QKP) vise à optimiser une fonction de coût quadratique au sein d'un seul sac à dos. Ses applications et sa difficulté le rendent attrayant pour divers domaines industriels. Dans cet article, nous présentons une stratégie efficace pour résoudre le problème en le modélisant comme un modèle de spin d'Ising en utilisant une machine d'Ising pour rechercher son état fondamental qui se traduit par la solution optimale du problème. Deuxièmement, afin de faciliter la recherche, nous proposons une nouvelle technique pour visualiser le paysage de la recherche et démontrer à quel point il est difficile de résoudre QKP sur une machine d'Ising. Enfin, nous proposons deux algorithmes d’amélioration de solutions logicielles pour résoudre efficacement QKP sur une machine d’Ising.
Matthieu PARIZY
the company 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.
Copier
Matthieu PARIZY, Nozomu TOGAWA, "Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 11, pp. 1526-1535, November 2021, doi: 10.1587/transfun.2020KEP0007.
Abstract: The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020KEP0007/_p
Copier
@ARTICLE{e104-a_11_1526,
author={Matthieu PARIZY, Nozomu TOGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine},
year={2021},
volume={E104-A},
number={11},
pages={1526-1535},
abstract={The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.},
keywords={},
doi={10.1587/transfun.2020KEP0007},
ISSN={1745-1337},
month={November},}
Copier
TY - JOUR
TI - Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1526
EP - 1535
AU - Matthieu PARIZY
AU - Nozomu TOGAWA
PY - 2021
DO - 10.1587/transfun.2020KEP0007
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2021
AB - The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.
ER -