# Regularized Langevin Dynamics for Combinatorial Optimization

arXiv: https://arxiv.org/abs/2502.00277 · HTML: https://mlsanity.com/paper/2502.00277/

## 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 (most cited first, 30 of 33)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning](https://mlsanity.com/paper/2208.04202/) (2022)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [MLGO: a Machine Learning Guided Compiler Optimizations Framework](https://mlsanity.com/paper/2101.04808/) (2021)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning](https://mlsanity.com/paper/2301.03116/) (2023)

## Built on by (most cited first, 10 of 10)

- [AutoSOTA: An End-to-End Automated Research System for State-of-the-Art AI Model Discovery](https://mlsanity.com/paper/2604.05550/) (2026)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching](https://mlsanity.com/paper/2605.30920/) (2026)
- [SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs](https://mlsanity.com/paper/2508.16171/) (2025)
- [BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design](https://mlsanity.com/paper/2604.12898/) (2026)
- [Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning](https://mlsanity.com/paper/2604.20109/) (2026)
- [Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization](https://mlsanity.com/paper/2605.25129/) (2026)
- [Solving Integer Linear Programming with Parallel Tempering](https://mlsanity.com/paper/2605.29366/) (2026)
- [When Do Learned Diffusion Proposals Help Constraint Solving? A Controlled Study on Continuous Algebraic Systems](https://mlsanity.com/paper/2607.27169/) (2026)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)

## 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.