Research map / Image generation / Fast diffusion sampling
Efficient Combinatorial Optimization via Heat Diffusion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Heat diffusion optimization (HeO), a gradient-based solver for pseudo-Boolean and combinatorial problems that minimizes heat-diffused (Gaussian-smoothed, erf-closed-form) versions of the objective, which share its global optima.
Problem
Combinatorial optimization is hard because discrete search only accesses a small local neighborhood per iteration, so solvers get trapped in local minima; the goal is a solver with a wider effective receptive field for global optima.
Approach
Treat the objective as an initial temperature field and evolve it under the heat equation; the heat-diffused functions keep the same global minima (backward uniqueness), so gradient descent on them propagates distant information to the solver. For multilinear objectives the diffused function has a closed form via erf, giving a one-sample gradient estimator with projection onto [0,1]^n.
Key results
- On Biq Mac max-cut, HeO has the lowest average relative loss among 7 methods and is among the bottom-2 worst least often.
- On minimum vertex cover over seven large real-world graphs, HeO finds smaller covers than FastVC on all seven (e.g., socfb-B-anon 312531 vs 338724).
- HeO outperforms the 3-order OIM and 2-order OIM on 3-SAT instances with 175-250 variables, finding more fully satisfying assignments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use HeO instead of FastVC | minimum vertex cover · tech-RL-caida | vertex cover size: 78306 -> 77372 (17) | Helped |
| use HeO instead of FastVC | minimum vertex cover · soc-youtube | vertex cover size: 149458 -> 148875 (25) | Helped |
| use HeO instead of FastVC | minimum vertex cover · inf-roadNet-PA | vertex cover size: 588306 -> 587401 (104) | Helped |
| use HeO instead of FastVC | minimum vertex cover · inf-roadNet-CA | vertex cover size: 1063352 -> 1061339 (32) | Helped |
| use HeO instead of FastVC | minimum vertex cover · socfb-B-anon | vertex cover size: 338724 -> 312531 (194) | Helped |
| use HeO instead of FastVC | minimum vertex cover · socfb-A-anon | vertex cover size: 421123 -> 387730 (355) | Helped |
| use HeO instead of FastVC | minimum vertex cover · socfb-uci-uni | vertex cover size: 869457 -> 867863 (36) | Helped |
| use HeO rather than MCGE with momentum | toy neural-network optimization · Toy example | target function energy | Helped |
| use HeO rather than QUBO solvers | max-cut · Biq Mac Library | average relative loss | Helped |
| use HeO rather than OIM solvers | 3-SAT · SATLIB, 175-250 variables | probability of satisfying all clauses | Helped |
| use HeO rather than MCGE with momentum | ternary neural-network training · Ternary optimization | weight value accuracy | Helped |
| use HeO rather than Lasso and L0.5 regression | linear-regression variable selection · 400-dimensional linear regressions | test MSE | Helped |
Surprising findings
- Non-monotonic tau schedules (random perturbations) leave HeO's performance largely unchanged while other adiabatic/bifurcation methods degrade sharply.
- Directly adding higher-order terms to the 3-SAT objective has no effect because indicator products are idempotent, so the authors instead raise the clause product terms to a power in the gradient.
Limitations
- No theoretical guarantee of convergence to the global minimum for non-convex combinatorial problems.
- Inefficient for integer linear programming and routing problems because integer variables are hard to encode with Bernoulli distributions.
- Theory covers only multilinear objectives; for general cases the approximation is used without guarantees.
Experimental setup
Datasets: Biq Mac Library max-cut instances SATLIB 3-SAT instances real-world graphs from Network Repository (tech-RL-caida, soc-youtube, inf-roadNet-PA/CA, socfb graphs) synthetic linear regression and ternary perceptron data
Benchmarks: Biq Mac max-cut SATLIB 3-SAT real-world minimum vertex cover graphs synthetic ternary perceptron training 400-dim variable selection
Metrics: relative loss bottom-2 count percent constraints satisfied probability of satisfying all clauses vertex cover size MSE variable selection accuracy
Baselines: LQA aSB bSB dSB CIM SIM-CIM simulated annealing Hopfield neural network MCGE FastVC Lasso L0.5 regression
Builds on: Monte Carlo gradient estimation Gaussian continuation evolution strategy simulated bifurcation denoising diffusion models
Closest papers by meaning
- Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization (NeurIPS 2025 · similarity 0.88)
- Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization (NeurIPS 2024 · similarity 0.88)
- A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization (ICML 2024 · similarity 0.87)
- Regularized Langevin Dynamics for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems (ICML 2024 · similarity 0.86)
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.