Self-Adaptive Ising Machines for Constrained Optimization
This addresses a bottleneck in physics-inspired computing for constrained optimization, offering a significant speed-up for domain-specific applications.
The paper tackled the challenge of solving constrained optimization problems with Ising machines by proposing a self-adaptive method that iteratively shapes the energy landscape using Lagrange relaxation, avoiding prior penalty tuning. For a quadratic knapsack problem with 300 variables, it found better solutions than state-of-the-art IMs like Fujitsu's Digital Annealer and required 7,500x fewer samples.
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.