Self-Adaptive Ising Machines for Constrained Optimization

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.

References in corpus (9)

• Ising formulations of many NP problems
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Stochastic p-bits for Invertible Logic
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Application of Quantum Annealing to Nurse Scheduling Problem
• Hardware-aware $insitu$ Boltzmann machine learning using stochastic magnetic tunnel junctions
• CMOS + stochastic nanomagnets: heterogeneous computers for probabilistic inference and learning
• Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem

Cited by in corpus (1)

• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization