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.
| Original language | English |
|---|---|
| Pages (from-to) | 1526-1535 |
| Number of pages | 10 |
| Journal | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |
| Volume | E104A |
| Issue number | 11 |
| DOIs | |
| Publication status | Published - 2021 Nov |
Keywords
- Ising machine
- Ising model
- knapsack problem
- visualization
ASJC Scopus subject areas
- Signal Processing
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering
- Applied Mathematics