# Local-Minima-Preserving Continuous Relaxation of Ising Problems

arXiv: https://arxiv.org/abs/2606.30333 · HTML: https://mlsanity.com/paper/2606.30333/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 47 references that are in the map.
- First posted on arXiv 29 Jun 2026.

## Builds on (most cited first, 11 of 11)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [First-order methods almost always avoid saddle points: the case of vanishing step-sizes](https://mlsanity.com/paper/1906.07772/) (2019)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [Free-Energy Machine for Combinatorial Optimization](https://mlsanity.com/paper/2412.09285/) (2024)
- [ON-OFF Neuromorphic ISING Machines using Fowler-Nordheim Annealers](https://mlsanity.com/paper/2406.05224/) (2024)
- [Differentiable Quadratic Optimization For The Maximum Independent Set Problem](https://mlsanity.com/paper/2406.19532/) (2024)
- [Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling](https://mlsanity.com/paper/2408.04744/) (2024)
- [Highly parallel algorithm for the Ising ground state searching problem](https://mlsanity.com/paper/1907.05124/) (2019)
- [Characterization of Locality in Spin States and Forced Moves for Optimizations](https://mlsanity.com/paper/2312.02544/) (2023)

## Abstract (arXiv)

The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landscape equivalence theorem: there exists a one-to-one correspondence between the local minima of the relaxation and the one-flip minima of the original Ising problem. This guarantee reduces the Ising problem to finding the local minima of a smooth function, allowing us to leverage gradient-based optimizers such as ADAM. We demonstrate that our method is scalable and it achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.