A Dynamical Systems Perspective on Discrete Optimization

arXiv2305.08536MaRDI QIDQ6436617FDOQ6436617

Authors: Tong Guanchun, Michael Muehlebach 

Publication date: 15 May 2023

Abstract: We discuss a dynamical systems perspective on discrete optimization. Departing from the fact that many combinatorial optimization problems can be reformulated as finding low energy spin configurations in corresponding Ising models, we derive a penalized rank-two relaxation of the Ising formulation. It turns out that the associated gradient flow dynamics exactly correspond to a type of hardware solvers termed oscillator-based Ising machines. We also analyze the advantage of adding angle penalties by leveraging random rounding techniques. Therefore, our work contributes to a rigorous understanding of oscillator-based Ising machines by drawing connections to the penalty method in constrained optimization and providing a rationale for the introduction of sub-harmonic injection locking. Furthermore, we characterize a class of coupling functions between oscillators, which ensures convergence to discrete solutions. This class of coupling functions avoids explicit penalty terms or rounding schemes, which are prevalent in other formulations.

This page was built for publication: A Dynamical Systems Perspective on Discrete Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436617)