mlsanityData to 14 Oct 2026

Regularized Langevin Dynamics for Combinatorial Optimization

arXiv 2502.00277 ↗First posted 1 Feb 2025cs.LG stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

This work proposes a simple yet effective sampling framework for combinatorial optimization (CO). Our method builds on discrete Langevin dynamics (LD), an efficient gradient-guided generative paradigm. However, we observe that directly applying LD often leads to limited exploration. To overcome this limitation, we propose the Regularized Langevin Dynamics (RLD), which enforces an expected distance between the sampled and current solutions, effectively avoiding local minima. We develop two CO solvers on top of RLD, one based on simulated annealing (SA), and the other one based on neural network (NN). Empirical results on three classic CO problems demonstrate that both of our methods can achieve comparable or better performance against the previous state-of-the-art (SOTA) SA- and NN-based solvers. In particular, our SA algorithm reduces the runtime of the previous SOTA SA method by up to 80%, while achieving equal or superior performance. In summary, RLD offers a promising framework for enhancing both traditional heuristics and NN models to solve CO problems. Our code is available at https://github.com/Shengyu-Feng/RLD4CO.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 33 of its 73 references that are in the map. First posted on arXiv 1 Feb 2025.

Builds on

33 of 73 references.

References · 33

  1. 2020Denoising Diffusion Probabilistic Modelscited by 21,076
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2020Denoising Diffusion Implicit Modelscited by 9,781
  4. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  5. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  6. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,101
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  8. 2021Structured Denoising Diffusion Models in Discrete State-Spacescited by 1,719
  9. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  10. 2020Improved Techniques for Training Score-Based Generative Modelscited by 1,043
  11. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  12. 2018Attention, Learn to Solve Routing Problems!cited by 656
21 more
  1. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  2. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  3. 2022Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioningcited by 373
  4. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  5. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  6. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  7. 2013Ising formulations of many NP problemscited by 207
  8. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  9. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  10. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  11. 2021Oops I Took A Gradient: Scalable Sampling for Discrete Distributionscited by 92
  12. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 59
  13. 2020Learning What to Defer for Maximum Independent Setscited by 54
  14. 2022A Langevin-like Sampler for Discrete Distributionscited by 44
  15. 2021MLGO: a Machine Learning Guided Compiler Optimizations Frameworkcited by 40
  16. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 37
  17. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  18. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 20
  19. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 11
  20. 2024SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branchcited by 9
  21. 2022Finding Near-Optimal Weight Independent Sets at Scalecited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 8.

10 papers.

  1. 2026AutoSOTA: An End-to-End Automated Research System for State-of-the-Art AI Model Discoverycited by 23
  2. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimizationcited by 11
  3. 2026Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matchingcited by 2
  4. 2025SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programscited by 1
  5. 2026BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Designcited by 1
  6. 2026Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuningcited by 0
  7. 2026Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimizationcited by 0
  8. 2026Solving Integer Linear Programming with Parallel Temperingcited by 0
  9. 2026When Do Learned Diffusion Proposals Help Constraint Solving? A Controlled Study on Continuous Algebraic Systemscited by 0
  10. 2026Compute Time Scaling with Recursive Models for Combinatorial Optimizationcited by 0