cmach508 / 2020-gnn-mcts-tsp

GNN-MCTS-TSP

Implementation of "A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem" (https://ieeexplore.ieee.org/document/9109309)

1. Build

1. Get the source code, and install all the dependencies.

git clone --recursive https://github.com/snail-ju/GNN-MCTS-TSP.git

2. Build the pytorch with the instructions here,

conda install pytorch==1.2.0 torchvision==0.4.0 cudatoolkit=10.0 -c pytorch

3. Build the pytorch geometric with the instructions here, https://pytorch-geometric.readthedocs.io/en/latest/notes/installation.html

   When installing the pytorch geometric, please follow the instructions below,

pip install torch-scatter==1.3.1
pip install torch-sparse==0.4.0
pip install torch-cluster==1.4.4
pip install torch-spline-conv==1.1.0
pip install torch-geometric==1.3.2

4. Build other dependencies including tqdm and tensorboardX.

2. Experiments on synthetic data

Generate synthetic data

To generate the synthetic data for TSP, you can do with the instructions here:

1. Visit the website of the DIMACS Implementation Challenge (http://dimacs.rutgers.edu/archive/Challenges/TSP/download.html).
2. Download the instance generator in part “Benchmark Code and Instance Generation Codes” of the above website.
3. Execute the corresponding program to generate different types of instances. Note that the program will generate the data on the fly.

**We also provide codes in the “data-generator” director to generate instances, and the file format generated by codes is adapted to our program. Compile the code with the following instructions, **

cd data-generator
gcc portgen.c -o prorgen -lm
gcc portcgen.c -o prorgen -lm

Training SE-GNN on synthetic data

Please modify the corresponding options in the "segnn/config.json" file.

Navigate to the segnn folder and train the SE-GNN with the following instructions,

cd segnn
python train.py -c config.json

By default it will save all the model files in "saved/models/SE-GNN", the logs under "saved/log/SE-GNN".

Test the GNN-MCTS

Navigate to the gnn-mcts folder and run the evaluation script. Modify the script to change the parameters. Make sure the parameters are consistent with your training script.

cd gnn-mcts
./run.sh

The above script will load the 1000 test instances you generated before, and output the solution in some text files under the result folder.

Reproducing the results that reported in the paper

Here is the link to the dataset that was used in the paper:

https://www.dropbox.com/sh/4o0tc5aoamat7hy/AABzIz-bOgSLp9_da5GQmjKGa?dl=0

Reference

Please cite our work if you find our code/paper is useful to your work.

@ARTICLE{9109309,  
  author={Z. {Xing} and S. {Tu}},  
  journal={IEEE Access},   
  title={A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem},   
  year={2020},  
  volume={8},  
  number={},  
  pages={108418-108428},
}