Codes for AAAI22 paper "Learning to Solve Travelling Salesman Problem with Hardness-Adaptive Curriculum"

Paper

For more details, please see our paper Learning to Solve Travelling Salesman Problem with Hardness-Adaptive Curriculum which has been accepted at AAAI 2022. If this code is useful for your work, please cite our paper:

@inproceedings{zhang2022learning,
  title={Learning to Solve Travelling Salesman Problem with Hardness-Adaptive Curriculum},
  author={Zeyang Zhang and Ziwei Zhang and Xin Wang and Wenwu Zhu},
  booktitle={Proceedings of the AAAI Conference on Artificial Intelligence},
  year={2022}
}

Dependencies

Require python>=3.8

Install other packages

pip install torch matplotlib scipy tqdm tensorboard sklearn jupyter jupyterlab pandas gurobipy seaborn tensorboardX

And follow https://github.com/wouterkool/attention-learn-to-route to install Gurobi Solver. In short, it can be installed by conda:

conda config --add channels http://conda.anaconda.org/gurobi
conda install gurobi

Or manually: Find and download the package in https://anaconda.org/Gurobi/gurobi/files?page=0, then use conda install.

Usage

1. generate data This step generates necessary TSP Instances for experiments.

python src/generate_data.py --problem tsp --graph_sizes 50 --name val_mg --seed 2222 --dataset_size 10000 --generate_type mg
python src/generate_data.py --problem tsp --graph_sizes 50 --name train --seed 1111 --dataset_size 10000 --generate_type random -f 
python preprocess.py

2. preliminary study This step shows the optimality gaps of TSP instances generated from gaussian mixture generator as $c_{\text{dist}}$ increases

python preliminary.py

3. Hardness-adaptive generator This step shows the optimality gaps of TSP instances generated from hardness-adaptive generator as $\eta$ increases

python hag.py

4. Hardness-adaptive Curriculum This step shows the optimality gaps with or without hardness-adaptive curriculum. In this case, training data and testing data is from uniform and gaussian mixture respectively. Replace 'X' with GPU device id.

CUDA_VISIBLE_DEVICES=X python main.py --train_type uniform --iters 15
CUDA_VISIBLE_DEVICES=X python main.py --train_type hardness-adaptive --iters 15

5. showcase This step shows some cases of instances generated by hardness-adaptive generator.

python showcase.py

Acknowledgements

This repo is modified mainly based on the code https://github.com/wouterkool/attention-learn-to-route.