acceptodds
Under review as a conference paper at ICLR 2027

Relaxation-Free Annealing for Quadratic Unconstrained Binary Optimization

Abstract

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.

Primary area:
optimization
Keywords:
combinatorial optimization, discrete optimization, learning-free solvers, quadratic unconstrained binary optimization (QUBO)

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yVipOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces an algorithm called iPAMM to solve QUBO problems. The proposed algorithm relies on adding a quadratic shift term analogous to self-feedback in soft-spin Ising models. The author provides in length some theoretical guarantee of fitness increase under specific conditions and numerical results comparing some other QUBO solvers.

Critical strengths
  • The method is quite simple and clear to understand.

  • The paper includes ablation studies and comparisons with several recent learning-based QUBO solvers.

Critical weaknesses

My main concerns are about novelty, practical relevance of the results and limits of empirical results.

  • iPAMM's dynamics seems very similar to a hard-threshold soft-spin Ising machine.
  • The theoretical guarantee only applies in a limited range for sufficiently large self-gain where spin flipping is already a very rare event. It is unclear how the theoretical guarantees actually describe the benefit of the overall algorithm.
  • A large part of the paper is dedicated to the limited scope theoretical analysis, leaving little space for required empirical results for such a work. Comparison to modern Ising machine algorithm is largely absent.
Questions for authors

Q1) Can you clarify the connection with soft-spin Ising models? In particular, the quadratic shift term resembles self-gain and hard thresholding replaces continuous saturation. How does this differ from existing gain-annealing approaches? See in particular:

https://www.nature.com/articles/s42005-021-00655-8

Q2) Can you provide a clear comparison with existing Ising machine algorithms including dSBM, CAC, and hyperspin machine? See:

https://doi.org/10.1103/PhysRevLett.122.040607 https://doi.org/10.1126/sciadv.abe7953 https://doi.org/10.1103/PhysRevLett.132.017301

Q3) How much does the theoretical monotonicity guarantee contribute to the overall optimization performance? How much fitness improves after the gain reaches the guaranteed regime?

Q4) Could the author include benchmarks on planted instances such as Wishart-planted and tile-planted, where instance difficulty with known ground-states can be tuned?

Q5) Could the author report computational time or time-to-solution for the GSET ? This would allow a more meaningful comparison against SOTA Ising machines.

Reviewer_19yCOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors introduce an algorithm for quadratic unconstrained binary optimization (QUBO). Their approach shifts the quadratic matrix to create a convex problem by subtracting a scaled identity from the diagonal. The new problem yields a separable lower bound, allowing every binary variable to be updated at once through simple matrix multiplication and thresholding.

The authors give a number of examples and show promising results.

Critical strengths

The paper to me looks more like an engineering effort than new science.

It uses a combination of well established techniques

  1. Diagonal shifting using x^2=x
  2. Minorization-maximization
  3. Parallel updates
  4. Restarts, perturbations and greedy refinement.

The engineering is good. The novelty not so much

Critical weaknesses

See above

Questions for authors

Can the authors justify the novelty of the paper or state why this is so much better than previous work.

Reviewer_ypKAOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes the iPAMM, which is a learning-free GPU heuristic for dense QUBO. The basic idea of this work is to shift the diagonal of the coefficient matrix, and then maximize a linear lower bound on the objective using one matrix-vector product. The solver gradually anneals this shift while running many starting points in parallel. It then repeatedly perturbs the best solutions found so far. Then it anneals them again, and refines them with greedy single-bit flips. On two benchmarks, this method reports average optimality gap of 0.04–0.16% in 0.4–5.4 s, which is better than the evaluated learning-based or relaxation-based solvers.

Critical strengths

The proposed method is simple, learning-free, and can be entirely run as batched matrix products on GPUs. It achieves the best results on four of the six dense benchmark families among all the methods evaluated. The appendices are thorough and honest. The experiments are relatively comprehensive, with seed variance, significance tests, ablations, failure cases, and weaker results on sparse Max-Cut all reported.

Critical weaknesses
  1. Two strong results from the main learning-based baseline method are not included. The benchmarks, metrics, and greedy baseline for this paper are taken from the VCM paper [34]. However, Table 1 in [34] reports Gurobi with a 1s time limit achieving 0.034, 0.070, 0.108, 0.091, 0.122 and 0.145% across the six instance families. This is better than iPAMM on three of the six families and gives a lower average across all 31 instances (0.080% vs 0.097%). That same table also reports VCM + greedy refinement with a 400-model ensemble, which achieves 0.012–0.057%. This is also better than the longer-run iPAMM variant on every family. Therefore, the claim that iPAMM beats every learned and hybrid solver might not be convincing enough.

  2. Some strong classical QUBO heuristics are not compared. Although the paper cites tabu-search, memetic and simulated-annealing methods [44, 50, 51, 56, 57], the experiments did not test them. Iterated tabu search (Palubeckis, 2006) or path relinking (Wang et al., 2012) should also be compared with equal running time. Some GPU-based solvers with the same batched arithmetic are also missing. For example, the Adaptive Bulk Search (Yasudo et al., 2020) and the simulated bifurcation (Goto et al., 2019; 2021).

  3. The proposed theories are mostly known, and also do not justify the results reported. Convexifying a binary quadratic by shifting its diagonal can be traced back to Hammer and Rubin (1970). Also, a tangent-plane surrogate from a spectral shift, maximized in closed form over a discrete or unimodular set, is a standard MM construction (Song, Babu and Palomar, 2015; also in [36]). Proposition 3.3 repeats the convergence results for symmetric threshold networks [42, 43], and it only holds when µ is fixed. The shift changes at every ramp step, so the claim in the Abstract that the annealing path decreases a Lyapunov energy is not proved.

  4. The B2500 ablation results appear to be inconsistent. Table S1 reports a 0.780% optimality gap for MM. It starts from the all-ones vector with a fixed shift μ^\hat\mu. However, Fig. S7a reports 20–25% for ρ=0\rho=0, which is described to be under the same fixed-shift setting. Algorithm S1 includes the all-ones start and returns the best result across starts. So with the same shift and iteration budget, the gap cannot be larger. In addition, Table S1 also reports 1.017% for PAMM with 32 total starts, but Fig. S7b shows about 0.78% with one start and 0.58% with 32.

  5. The learning-based baseline might not be fairly evaluated. VCM is trained on one fifth of the published training dataset size. The reproduced VCM50-BGF and VCM100-BGF are worse than the numbers in the original publication [34] on every family by up to 50%: VCM100-BGF is 0.268 vs 0.203 on P3000. The raw VCM10 is 0.944 vs 0.368 on B2500.

  6. The scope of the proposed method is relatively narrow. All main problem sets are dense random-like matrices. Also, the generated G sets use the better of the authors' own PAMM-GF and BGF as the reference. On the sparse Gset, iPAMM underperforms MFA on every instance except G14. iPAMM only reaches 96.2–99.4% of the best-known cut, and loses to greedy BGF on G50. There are no structured QUBO instances evaluated, such as MAP inference, QAP or QPLIB.

Questions for authors

How does iPAMM compare with Gurobi, tuned tabu search, simulated annealing and simulated bifurcation at the same time budgets on the B and P sets?

How does MFA perform when it is given iPAMM's budget and is given restarts?

Please check the consistencies between Table S1 with Fig. S7.

How much of the final improvement comes from the admissible phase, ramp, and the hardening phase?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.