Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem

Abstract

Combinatorial optimization has wide applications from industry to natural science. Ising machines bring an emerging computing paradigm for efficiently solving a combinatorial optimization problem by searching a ground state of a given Ising model. Current cutting-edge Ising machines achieve fast sampling of near-optimal solutions of the max-cut problem. However, for problems with additional constraint conditions, their advantages have been hardly shown due to difficulties in handling the constraints. In this work, we focus on benchmarks of Ising machines on the quadratic knapsack problem (QKP). To bring out their practical performance, we propose fast two-stage post-processing for Ising machines, which makes handling the constraint easier. Simulation based on simulated annealing shows that the proposed method substantially improves the solving performance of Ising machines and the improvement is robust to a choice of encoding of the constraint condition. Through evaluation using an Ising machine called Amplify Annealing Engine, the proposed method is shown to dramatically improve its solving performance on the QKP. These results are a crucial step toward showing advantages of Ising machines on practical problems involving various constraint conditions.

26 pages

References in corpus (6)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
• Quantum versus Classical Annealing of Ising Spin Glasses
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases

Cited by in corpus (5)

• Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems
• Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems
• Self-Adaptive Ising Machines for Constrained Optimization
• Performance of the Extended Ising Machine for the Quadratic Knapsack Problem
• Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing