Research map / Optimization / Optimizers
Regularized Langevin Dynamics for Combinatorial Optimization
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 Regularized Langevin Dynamics (RLD), a discrete Langevin sampler that fixes the expected Hamming step size, and builds an SA solver (RLSA) and a neural solver (RLNN) that match or beat prior SA/NN solvers on MIS, MCl and MCut with much lower runtime.
Problem
Combinatorial optimization (MIS, maximum clique, maximum cut) is NP-hard, and discrete Langevin-based samplers get stuck in local optima because gradients at discrete local optima point to infeasible regions and the step shrinks as temperature decreases.
Approach
Regularize the expected Hamming distance between the proposed and current solution to a constant d (via the d-th largest element of the energy-drop vector), so each step flips a controlled number of coordinates; this is used both inside simulated annealing (RLSA) and as an unsupervised loss for a GCN sampler (RLNN).
Key results
- RLSA achieves MIS size 19.97 on RB-[200-300] in 35s versus iSCO's 19.29 in 2.71m, and 44.10 on ER-[700-800] in 20s versus 42.18 for iSCO.
- RLSA reports the best MCut result on BA-[800-1200] (2955.81 vs 2947.53 for DiffUCO) and best MCl on RB-[800-1200] (40.53 vs 40.35 for iSCO).
- RLNN with regularization improves MIS RB-[200-300] from 18.64 to 19.52 and MCl RB-[200-300] from 16.62 to 18.13 over the unregularized variant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RLSA instead of iSCO | MIS RB-[200--300] · MIS RB-[200--300] | set size: 19.29 -> 19.97 | Helped |
| Use RLSA instead of DiffUCO | MIS RB-[800--1200] · MIS RB-[800--1200] | set size: 38.87 -> 40.19 | Helped |
| Use RLSA instead of iSCO | MIS ER-[700--800] · MIS ER-[700--800] | set size: 42.18 -> 44.10 | Helped |
| Use RLSA instead of iSCO | MIS ER-[9000--11000] · MIS ER-[9000--11000] | set size: 365.37 -> 375.31 | Helped |
| Use RLSA instead of iSCO | MCl RB-[200--300] · MCl RB-[200--300] | clique size: 18.96 -> 18.97 | Helped |
| Use RLSA instead of iSCO | MCl RB-[800--1200] · MCl RB-[800--1200] | clique size: 40.35 -> 40.53 | Helped |
| Use RLSA instead of iSCO | MCut BA-[200--300] · MCut BA-[200--300] | cut size: 728.24 -> 733.54 | Helped |
| Use RLSA instead of DiffUCO | MCut BA-[800--1200] · MCut BA-[800--1200] | cut size: 2947.53 -> 2955.81 | Helped |
| Add regularization during RLNN training (ablation) | RLNN on MIS RB-[200--300] · MIS RB-[200--300] | set size: 18.64 -> 19.52 | Helped |
| Add regularization during RLNN training (ablation) | RLNN on MIS ER-[700--800] · MIS ER-[700--800] | set size: 37.73 -> 43.34 | Helped |
| Add regularization during RLNN training (ablation) | RLNN on MCl RB-[200--300] · MCl RB-[200--300] | clique size: 16.62 -> 18.13 | Helped |
| Add regularization during RLNN training (ablation) | RLNN on MCut BA-[200--300] · MCut BA-[200--300] | cut size: 730.20 -> 729.00 | Hurt |
Surprising findings
- Standard discrete Langevin with step sizes down to 0.001 ends at suboptimal solutions on MIS, while the regularized version converges in under 100 steps.
- Regularization gives little or no gain for RLNN on MCut, which the authors attribute to MCut being unconstrained and less prone to local optima.
Limitations
- Only binary variables are considered, so generality to categorical, integer or mixed-integer CO problems is unclear.
- No theoretical analysis of RLD is given; the justification is intuitive.
- RLNN uses only the unsupervised EGN-style loss and an unchanged GCN architecture, and results are below RLSA.
Experimental setup
Datasets: RB graphs (200-300, 800-1200 nodes) ER graphs (700-800, 9000-11000 nodes) BA graphs (200-300, 800-1200 nodes)
Benchmarks: RB-[200-300] MIS RB-[800-1200] MIS ER-[700-800] MIS ER-[9000-11000] MIS RB MCl BA MCut
Metrics: solution size total runtime primal gap
Baselines: Gurobi KaMIS PPO INTEL DGL DIMES DIFUSCO LTFT DiffUCO iSCO EGN MFA
Builds on: discrete Langevin sampler iSCO Erdős Goes Neural DiffUCO normalized gradient descent
Closest papers by meaning
- Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems (ICLR 2024 · similarity 0.87)
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling (ICLR 2025 · similarity 0.87)
- Efficient Combinatorial Optimization via Heat Diffusion (NeurIPS 2024 · similarity 0.87)
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.87)
- Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization (NeurIPS 2024 · similarity 0.86)
- Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics (ICLR 2025 · similarity 0.86)
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.