Relaxation-Free Annealing for Quadratic Unconstrained Binary Optimization

A large part of combinatorial optimization can be written as quadratic unconstrained binary optimization (QUBO), the maximization of a quadratic function over binary vectors, which is also the form in which Ising machines and quantum annealers accept a problem. At the sizes met in practice, QUBO is solved approximately, and neural models trained to predict good assignments increasingly take the place of classical search rules. We reassess the advantage reported for these models by granting a classical method the same arithmetic, and we do so with a solver that involves no learning at all. Shifting the diagonal of the coefficient matrix below its smallest eigenvalue renders the quadratic part convex on the binary cube, so its tangent plane is an exact separable minorant, maximized in closed form by thresholding. We obtain an iteration that costs a single matrix-vector product, stays inside the discrete feasible set, needs no relaxation (in the sense of losing tightness), and never decreases the objective. We then lower the shift towards the smallest eigenvalue along a schedule and embed the iteration in batched perturb-anneal-harden cycles over an archive of the best solutions found so far, and we call this solver i. We characterize its fixed points, expose a trade-off between the curvature shift and the stationarity it guarantees, prove that the resulting path decreases a Lyapunov energy, and show the spin parameterization is canonical for this scheme. On dense benchmarks, i outperforms every learned, hybrid, relaxation-based and sampling-based solver we evaluate, and it also runs faster than the samplers among them.