Regularized Langevin Dynamics for Combinatorial Optimization

This is the official repo for Regularized Langevin Dynamics for Combinatorial Optimization, ICML 2025. In this repo, we implement two combinatorial optimization solvers based on the proposed regularization Langevin Dynamics (RLD). The first one is a simulated annealing approach, RLSA; and the other one is a neural approach, RLNN. If you have any question, please contact us at: shengyuf@cs.cmu.edu.

Setup

Our code framework is built upon accelerate. You can install all dependencies via the following command:

conda env create -f environment.yml
conda activate RLD4CO

Data Generation

We provide the following random graph generators in the data folder:

• Erdős–Rényi (ER): ER-[700-800] (train/val/test: 1000/100/128), ER-[9000-11000] (test: 16)
• Revised Model B (RB): RB-[200-300] (train/val/test: 1000/100/500), RB-[800-1200] (train/val/test: 1000/100/500)
• Barabási–Albert (BA): BA-[200-300] (train/val/test: 1000/100/500), BA-[800-1200] (train/val/test: 1000/100/500)

For example usage:

cd data

python er_generator.py \
  --num-graphs 1000 \
  --min-n 700 --max-n 800 \
  --seed 0 \
  --save-dir ./ER_small_train \
  --processes 10

Note that no training data is generated for ER-[9000-11000], you should directly test your solver trained/tuned on ER-[700-800] on ER-[9000-11000]!

For fair comparison, you can also download out test data here. The ER test graphs are directly from the repo of DIMES. The RB and BA graphs are generated by ourselves, using the code from DIffUCO. We include 1000 instances per problem (2 groups of 500-size test sets) and report the average performance on these two groups in our paper.

For all the scripts under the scripts folder, remember to specify DATADIR as your actual path to the problem instances.

RLSA

RLSA is a simulated annealing approach. We include all the evaluation commands in scripts/eval_rlsa.sh.

Some key parameters:

• --mixed_precision - data precision (no for floa32 and fp16 for float16, use fp16 to accelerate the inference)
• --num_processes - max parallel processes for multi-GPU running (set it as 1 when evaluating the time)
• --num_t - number of sampling steps
• --num_k - number of independent runs
• --num_d - regularization distance
• --tau0 - initial temperature
• --beta - penalty coefficient

RLNN

RLNN is a neural approach used to verify the effectiveness of RLD on black-box optimization, where we pretend to not know the explicit gradient formulat of the target problem, and use neural network to approximate it.

We provide two training losses: erdoes and reinforce. Erdoes corresponds to the results in our paper, which is an unsupervised learning method (see Erdoes Goes Neural), where we still utilize a differentiable loss to train the neural network. It is comparable to other sampling and unsupervised learning baselines. We include all the training commands in scripts/train_rlnn_erdoes.sh.

REINFORCE is a fully black-box optimization method, using reinforcement learning to estimate the gradient of a loss orale, i.e., the oracle returns the loss given an binary vector. We did not report the results in our paper since it uses way much less prior knowledge compared to other baselines. But our experimental results have shown that our method remains effective on this extremely hard black-box optimization. We include all the training commands in scripts/train_rlnn_reinforce.sh.

Beyond the parameters shared with RLSA, here are some other key parameters

• --num_tp - number of sampling steps for training sample generation
• --num_kp - number of independent runs for training sample generation
• --num_h - number of hidden dimension
• --num_l - number of GNN layers
• --lambda - regularization coefficient
• --loss - training loss, either erdoes or reinforce

You can find all our training logs at logs_train.

The inference script is at scripts/eval_rlnn.sh, you should specify LOSS as the target loss. We provide all the checkpoints here.

Citation

@inproceedings{feng2025regularizedlangevindynamicscombinatorial,
  title={Regularized Langevin Dynamics for Combinatorial Optimization}, 
  author={Shengyu Feng and Yiming Yang},
  booktitle={International conference on machine learning},
  year={2025},
  organization={PMLR}
}