Title: 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. The performance of Ising machines on such problems heavily depends on encoding methods of constraints into penalties, but the optimal choice is non-trivial. In this work, we focus on benchmarks of Ising machines on the quadratic knapsack problem (QKP). To bring out their practical performance, we propose to exploit the problem structure upon using Ising machines. Specifically, we apply fast two-stage post-processing to the outputs of Ising machines, which makes handling the constraint easier. Simulation on medium-sized test instances shows that the proposed method substantially improves the solving performance of Ising machines and the improvement is robust to a choice of the encoding methods. We evaluate an Ising machine called Amplify Annealing Engine with the proposed method and found that it achieves comparable results with existing heuristics.