Self-Adaptive Ising Machines for Constrained Optimization

Corentin DelacourarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces a "Self-Adaptive Ising Machine" (SAIM) that tackles a major hurdle in using Ising Machines (IMs) for real-world problems: handling constraints. By dynamically adjusting the IM's energy landscape using Lagrange multipliers, SAIM avoids the need for manual, often difficult, tuning of penalty parameters, leading to significantly improved accuracy and efficiency on challenging optimization tasks like knapsack problems.

What Problem Does This Paper Address?

Ising Machines (IMs) are promising hardware architectures for solving complex optimization problems by mapping them onto the interactions of "spins." While they excel at unconstrained problems (like finding maximum cuts in graphs), incorporating constraints has been a significant challenge. The standard approach, the "penalty method," involves adding a penalty term to the IM's energy function that increases when constraints are violated. However, this method requires carefully tuning a penalty parameter (P) to be large enough to enforce feasibility without making the energy landscape too rugged, which can trap the IM in suboptimal solutions. Finding this optimal P is difficult, time-consuming, and problem-specific, hindering the practical application of IMs to many real-world scenarios with constraints.

Methods

The core innovation is the Self-Adaptive Ising Machine (SAIM) algorithm. Instead of relying on a fixed, manually tuned penalty parameter, SAIM employs a Lagrange relaxation of constraints. This means the constraints are incorporated into the IM's objective function not as a squared penalty, but as a linear term weighted by Lagrange multipliers ($\lambda$).

The SAIM algorithm works iteratively:

  1. Minimization: The IM attempts to minimize a modified energy function that includes the objective function and the linearly weighted constraints. This is performed using a probabilistic-bit (p-bit) IM emulation.
  2. Lagrange Multiplier Update: After each minimization step, the Lagrange multipliers ($\lambda$) are updated to "push" the system towards satisfying the constraints. This update is based on the current state of the system and aims to maximize a "lower bound" of the original problem.
  3. Energy Landscape Shaping: This iterative process of minimization and multiplier update effectively "shapes" the IM's energy landscape over time, guiding it towards feasible and optimal solutions without requiring prior knowledge of the optimal penalty strength.

The authors use a probabilistic-bit (p-bit) IM emulated in software as a proof-of-concept. This p-bit model is known for its scalability and compatibility with various hardware implementations.

Datasets

The paper uses established benchmark problems for evaluation:

  • Quadratic Knapsack Problems (QKP): These are Ising problems with a single linear constraint. The authors use instances from existing literature [26] with varying densities (d) and numbers of variables (N).
  • Multidimensional Knapsack Problems (MKP): These are integer linear programs with multiple constraints. The authors use instances with varying numbers of items (N) and constraints (M) from existing literature [14, 28].

No new datasets were introduced.

Key Insights and Ideas

  • Lagrange Relaxation as a Constraint-Handling Game-Changer: The most significant insight is that using Lagrange multipliers, rather than fixed quadratic penalties, allows the IM to learn how to satisfy constraints dynamically. This shifts the burden from the user to the algorithm itself.
  • Self-Adaptation is Key: The iterative shaping of the energy landscape through $\lambda$ updates is crucial. It allows the IM to adapt to the problem's specific constraint structure, which is far more effective than a static penalty.
  • Reduced Parameter Sensitivity: SAIM significantly reduces the need for manual parameter tuning, a major bottleneck for applying traditional penalty methods. This makes IMs more accessible and practical.
  • Efficiency Gains: The adaptive nature of SAIM leads to substantial speedups and reduced sample requirements compared to existing methods, even those using specialized hardware.

Key Results

  • QKP Performance: For QKP with 300 variables, SAIM achieved an average accuracy of 99.2%, significantly outperforming state-of-the-art methods like Fujitsu's Digital Annealer (PT-DA) which achieved 83.3% on average.
  • Sample Efficiency: SAIM required up to 7,500x fewer samples than PT-DA and 100x fewer samples than another "best SA" method for QKP, demonstrating remarkable efficiency.
  • MKP Performance: For MKP, SAIM achieved an average accuracy of 99.7%, comparable to a state-of-the-art genetic algorithm (GA) [28], despite not explicitly leveraging problem structure.
  • Feasibility: While SAIM generally improves accuracy, the feasibility rate for MKP was lower (5.1%) compared to QKP (around 50%), suggesting that handling multiple, complex constraints remains a challenge, though the algorithm still finds good solutions.

Limitations and Future Work

  • Feasibility in MKP: The paper notes that the feasibility rate for MKP was lower than for QKP. The authors suggest that increasing initial penalty parameters or artificially reducing knapsack capacities could improve feasibility.
  • Initial Parameter Choice: While SAIM is less sensitive to parameters than the penalty method, the initial penalty parameter ($P$) still requires some setting, though the paper provides a heuristic ($P = \alpha dN$).
  • Hardware Implementation: The current work is a software emulation of a p-bit IM. Future work would involve implementing SAIM on actual hardware to fully realize its potential speedups.
  • Broader Problem Classes: Exploring SAIM's effectiveness on a wider range of constrained optimization problems beyond knapsack variants would be valuable.
  • Heuristic Nature: The paper acknowledges that the pseudo-gradient method used for updating $\lambda$ is heuristic, meaning it doesn't guarantee convergence to the absolute optimum in all cases, but it is practical for IMs.

Summary updated

Abstract

Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.
BibTeX
@misc{delacour2025self,
  author = {Corentin Delacour},
  title = {{Self-Adaptive Ising Machines for Constrained Optimization}},
  year = {2025},
  eprint = {2501.04971},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.04971},
}
Figure