RLD4CO

KO | EN

gitlite — search

#react #ai #llm #go #golang #machine-learning #deep-learning #docker #nodejs #kubernetes #awesome-list #ios #openai #open-source

(★ 9)

[ICML2025] Regularized Langevin Dynamics for Combinatorial Optimization

RLD4CO 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Regularized Langevin Dynamics for Combinatorial Optimization

This is the official repo for [Regularized Langevin Dynamics for Combinatorial Optimization](https://arxiv.org/pdf/2502.00277), 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](https://huggingface.co/docs/accelerate/en/index). 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](https://huggingface.co/datasets/shengyuf/RLD4CO). The ER test graphs are directly from the repo of [DIMES](https://github.com/DIMESTeam/DIMES). The RB and BA graphs are generated by ourselves, using the code from [DIffUCO](https://github.com/ml-jku/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](https://arxiv.org/abs/2006.10643)), 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](https://huggingface.co/shengyuf/RLNN).

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

RLD4CO

RLD4CO 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

RLD4CO

RLD4CO 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README