A reinforcement learning based solver for combinatorial problems
CombOpt Zero is a general-purpose solver based on AlphaGo Zero for combinatorial problems on graphs. Paper: Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
You can try MinimumVertexCover, MaximumIndependentSet, FeedbackVertexSet, MaxCut and MaximumClique, by running the code in this repository.
Install Docker and just run docker/install.sh
, docker/train.sh
and docker/eval.sh
!
docker/config.sh
and {problem}/config.sh
for other settingsdocker/train.sh
may yield some errors, possibly due to the file system of Docker. Please refer to FAQs.If you just want to try on docker, please ignore this section.
Download LibTorch from https://pytorch.org/
Download version 1.3.0
. Newer version may cause errors. If you use Linux, download Pre-cxx11 ABI
version.
Build library
Please also refer to docker/install.sh
if you have some problem.
$ cd max-clique/lib
$ mkdir build
$ cd build
$ cmake -DCMAKE_PREFIX_PATH=/path/to/libtorch ..
$ make
{problem}/config.sh
.
Then,$ cd max-clique
# create two scripts for training and evalution, named t_sample.sh and e_sample.sh, based on config.sh
$ echo sample | python script_generator.py
{problem}/results/{configuration}/
.$ cd max-clique
$ ./t_sample.sh
$ cd max-clique
$ ./e_sample.sh
All the test graphs used in our experiments are in test_graphs/
. Some of them are collected from Dimacs Vertex Cover instances and http://networkrepository.com/.
Please cite our paper if you use our code in your work:
@article{Xu/Abe/2020,
title={Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero},
author={Zijian Xu and Kenshin Abe and Issei Sato and Masashi Sugiyama},
journal={arXiv preprint arXiv:1905.11623},
year={2020}
}