Local-Minima-Preserving Polynomial Relaxation of Ising Problems

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 local 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 scalable gradient-based optimizers such as ADAM. We demonstrate that our method achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.

Combinatorial optimization arises in many challenging problems across logistics, network design, finance, and physics. Many of these problems can be written as “Ising models,” where the goal is to find the best configuration among exponentially many possibilities. Existing approaches either rely on slow discrete search methods or use continuous approximations that are easier to optimize but may produce solutions that no longer correspond to meaningful answers to the original problem. In this work, we develop a new continuous optimization framework called MiP-CRIM (Minima-Preserving Continuous Relaxation of Ising Model). Our key idea is to redesign the optimization landscape so that the solutions of the continuous problem exactly match the locally optimal solutions of the original discrete problem. We prove this correspondence mathematically through a “landscape equivalence theorem”. This allows us to use scalable gradient-based optimization methods, such as ADAM, while still preserving the structure of the original combinatorial problem. We evaluate our method on several challenging benchmark problems, including spin-glass models, MAX-CUT, and number partitioning. Across these tasks, MiP-CRIM consistently finds better solutions, outperforming specialized physics-inspired solvers, quantum annealers, and classical optimization methods, while remaining computationally efficient on large-scale instances. Our results show that carefully designed continuous relaxations can combine the scalability of first-order optimization with rigorous guarantees about discrete solution quality.