mlsanityData to 7 Oct 2026

Reheated Gradient-based Discrete Sampling for Combinatorial Optimization

arXiv 2503.04047 ↗First posted 6 Mar 2025stat.ML cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which we term ''wandering in contours''. This behavior refers to sampling new different solutions that share very similar objective values for a long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation. Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 22 of its 51 references that are in the map. First posted on arXiv 6 Mar 2025.

Builds on

22 of 51 references.

References · 22

  1. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  2. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  3. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  4. 2019Cyclical Stochastic Gradient MCMC for Bayesian Deep Learningcited by 203
  5. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  6. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  7. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  8. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  9. 2021Oops I Took A Gradient: Scalable Sampling for Discrete Distributionscited by 92
  10. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  11. 2020Learning What to Defer for Maximum Independent Setscited by 53
  12. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
10 more
  1. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  2. 2022A Langevin-like Sampler for Discrete Distributionscited by 42
  3. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 36
  4. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  5. 2022Discrete Langevin Sampler via Wasserstein Gradient Flowcited by 23
  6. 2020Data-Dependence of Plateau Phenomenon in Learning with Neural Network --- Statistical Mechanical Analysiscited by 22
  7. 2019GAP: Generalizable Approximate Graph Partitioning Frameworkcited by 18
  8. 2022Optimal Scaling for Locally Balanced Proposals in Discrete Spacescited by 9
  9. 2024Gradient-based Discrete Sampling with Automatic Cyclical Schedulingcited by 9
  10. 2023Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximationcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 3.

6 papers.

  1. 2025Sampling from Energy distributions with Target Concrete Score Identitycited by 2
  2. 2025Entropy-Guided Sampling of Flat Modes in Discrete Spacescited by 1
  3. 2025On the Dataless Training of Neural Networkscited by 0
  4. 2026Solving Integer Linear Programming with Parallel Temperingcited by 0
  5. 2026Fine-Tuning Low-Bit Models with Gradient in Quantized Code Spacecited by 0
  6. 2026Compute Time Scaling with Recursive Models for Combinatorial Optimizationcited by 0