Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization

Abstract

Physics-inspired computing paradigms are receiving renewed attention to enhance efficiency in compute-intensive tasks such as artificial intelligence and optimization. Similar to Hopfield neural networks, oscillatory neural networks (ONNs) minimize an Ising energy function that embeds the solutions of hard combinatorial optimization problems. Despite their success in solving unconstrained optimization problems, Ising machines still face challenges with constrained problems as they can become trapped in infeasible local minima. In this paper, we introduce a Lagrange ONN (LagONN) designed to escape infeasible states based on the theory of Lagrange multipliers. Unlike existing oscillatory Ising machines, LagONN employs additional Lagrange oscillators to guide the system towards feasible states in an augmented energy landscape, settling only when constraints are met. Taking the maximum satisfiability problem with three literals as a use case (Max-3-SAT), we harness LagONN's constraint satisfaction mechanism to find optimal solutions for random SATlib instances with up to 200 variables and 860 clauses, which provides a deterministic alternative to simulated annealing for coupled oscillators. We benchmark LagONN with SAT solvers and further discuss the potential of Lagrange oscillators to address other constraints, such as phase copying, which is useful in oscillatory Ising machines with limited connectivity.

References in corpus (17)

• Ising formulations of many NP problems
• Defining and detecting quantum speedup
• Stochastic p-bits for Invertible Logic
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Quantum Optimization of Fully-Connected Spin Glasses
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
• CMOS + stochastic nanomagnets: heterogeneous computers for probabilistic inference and learning
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• Evaluating spintronics-compatible implementations of Ising machines
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Solving Boolean satisfiability problems with resistive content addressable memories
• On computational capabilities of Ising machines based on nonlinear oscillators,
• Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling
• Scalable Connectivity for Ising Machines: Dense to Sparse
• Self-Adaptive Ising Machines for Constrained Optimization