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

Kentaro Ohno, Tatsuhiko Shirai, Nozomu Togawa

TL;DR

Ising machines, a promising new computing paradigm for optimization, struggle with problems that have complex constraints. This paper introduces a simple yet effective two-stage post-processing method that significantly improves Ising machines' ability to solve the Quadratic Knapsack Problem (QKP), a notoriously difficult optimization task. This work is a crucial step towards making Ising machines practical for real-world problems with constraints.

What Problem Does This Paper Address?

Combinatorial optimization problems, like the knapsack problem, are fundamental to many industries and scientific fields. These problems involve finding the best solution from a vast number of possibilities, which is often computationally intractable for traditional computers. Ising machines, inspired by statistical mechanics, offer a new approach by searching for the "ground state" of an Ising model, which can be mapped to optimization problems.

While Ising machines have shown promise for problems like "max-cut," they falter when dealing with additional constraints. This is because these constraints are typically incorporated as penalty terms in the Ising model. To ensure a solution is "feasible" (i.e., satisfies the constraints), a large penalty coefficient is needed. However, a large penalty can degrade the quality of the objective function, creating a difficult trade-off. Existing benchmarks show Ising machines are not competitive with other heuristic solvers on constrained problems like the Quadratic Knapsack Problem (QKP). The core challenge is that Ising machines don't reliably output feasible solutions, and tuning the penalty to achieve feasibility often sacrifices solution quality.

Methods

The authors propose a straightforward yet powerful two-stage post-processing technique to overcome the limitations of Ising machines when tackling the QKP. This method is applied after the Ising machine has generated a candidate solution.

  1. Repair Procedure: This step takes an potentially infeasible solution from the Ising machine and transforms it into a feasible one. It does this by greedily removing items from the knapsack until the capacity constraint is met. The key insight here is that by using a "repair" step, the penalty coefficient ($\lambda$) can be set to smaller values, mitigating the trade-off between feasibility and objective quality.
  2. Improvement Procedure: Once a feasible solution is obtained, this step further refines it to improve the objective value. It employs a greedy strategy based on "efficiency" metrics to add or swap items in the knapsack, aiming for a local optimum.

This post-processing approach is designed to work synergistically with the global search capabilities of Ising machines. The authors also explore various encoding methods for the QKP's inequality constraint into the QUBO (Quadratic Unconstrained Binary Optimization) format, which is what Ising machines typically solve.

Datasets

The paper uses two main sets of QKP instances for evaluation:

  • Medium-sized instances: A dataset of 100 instances generated in a previous study, with sizes ranging from n=100 to n=300. These instances have known optimal solutions and have been used in prior Ising machine benchmarks.
  • Large-sized instances: A dataset of QKP instances with sizes ranging from n=1000 to n=2000, generated using a similar protocol. For these, exact optimal solutions are not known, and the authors use the best-known solutions from prior work for evaluation.

Key Insights and Ideas

  • Post-processing is a game-changer: The most significant insight is that a simple, greedy post-processing step can dramatically improve the performance of Ising machines on constrained optimization problems, even when using standard algorithms. This suggests that the focus on complex encoding methods might be less critical than previously thought.
  • Decoupling feasibility and quality: By introducing a repair step, the penalty coefficient can be tuned for objective quality rather than solely for feasibility. This breaks the problematic trade-off that has plagued previous attempts.
  • Robustness to encoding: The proposed method makes the Ising machine's performance much less sensitive to the choice of how the inequality constraint is encoded into the QUBO problem. This simplifies practical application.
  • Synergy between global and local search: The Ising machine provides the global search, while the post-processing offers efficient local search. This combination is more effective than either approach alone.

Key Results

  • Significant performance boost: The proposed method, when applied to simulated annealing (SA) and a state-of-the-art Ising machine (Amplify Annealing Engine - AE), dramatically improved solving performance on QKP instances.
  • High optimality: For medium-sized instances, the combined approach (SA-RI) achieved optimal solutions on 82% of instances and a small optimality gap on the rest, significantly outperforming previous Ising machine benchmarks.
  • Competitive with heuristics: For large-scale QKP instances, AE with post-processing achieved best-known solutions on 77.5% of instances and demonstrated performance comparable to specialized heuristic solvers and even commercial solvers like Gurobi.
  • Negligible computational overhead: The post-processing steps added only a small computational cost (milliseconds) compared to the overall annealing time (seconds), making it practically efficient.
  • Encoding independence: The performance of the proposed method was largely insensitive to the choice of encoding method for the inequality constraint, a stark contrast to previous studies.

Limitations and Future Work

  • Undisclosed AE specifics: The authors note that some differences in AE-RI's performance compared to SA-RI across encoding methods might be due to the proprietary nature of the AE's internal workings.
  • Extension to other problems: The authors believe their approach, which combines Ising machines with greedy post-processing, can be extended to other optimization problems with similar constraint structures, such as the max k-cut problem.
  • Benchmarking framework: Establishing a more robust benchmarking framework that accounts for computational time is suggested for future work.
  • Further investigation of SA behavior: The paper points to the need for further investigation into why the post-processed outputs are surprisingly similar across different encoding methods.

Summary updated

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.
BibTeX
@article{ohno2024toward,
  author = {Kentaro Ohno and Tatsuhiko Shirai and Nozomu Togawa},
  title = {{Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem}},
  journal = {IEEE Access},
  year = {2024},
  doi = {10.1109/access.2024.3425711},
}
Figure