La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Open Access
Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine
Open Access
Analyse et accélération du problème quadratique du sac à dos sur une machine d'Ising

Matthieu PARIZY, Nozomu TOGAWA

  • Vues en texte intégral

    96

  • Citer
  • Free PDF (1.1MB)

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.11 pp.1526-1535
Date de publication
2021/11/01
Publicisé
2021/07/08
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2020KEP0007
Type de manuscrit
Special Section PAPER (Special Section on Circuits and Systems)
Catégories

Auteurs

Matthieu PARIZY
  the company FUJITSU LABORATORIES LTD.
Nozomu TOGAWA
  Waseda University

Mots-clés

Table des matières