TSP Transformer

Feb, 2021

Description

PyTorch implementation of "The Transformer Network for the Traveling Salesman Problem"
Xavier Bresson and Thomas Laurent
ArXiv : https://arxiv.org/pdf/2103.03012.pdf
Talk : https://ipam.wistia.com/medias/0jrweluovs
Slides : https://t.co/ySxGiKtQL5

Installation

# Install conda
curl -o ~/miniconda.sh -O https://repo.continuum.io/miniconda/Miniconda3-latest-Linux-x86_64.sh 
chmod +x ~/miniconda.sh  # install conda  
./miniconda.sh  
source ~/.bashrc  

# GitHub repo
conda install git
git clone https://github.com/xbresson/TSP_Transformer.git # clone repo
cd TSP_Transformer
conda env create -f environment_gpu.yml # install python environment (CUDA 10.1)
conda activate tsp_transformer # activate environment
jupyter notebook # start jupyter notebook

Results

1. Network Training (with RTX 2080 Ti 11GB)
   TSP50 (1 GPU) : Run notebook 'train_tsp_transformer_TSP50.ipynb'
   TSP100 (2 GPUs) : Run notebook 'train_tsp_transformer_TSP100.ipynb'
   
2. Network Testing
   TSP50 : Run notebook 'test_tsp_transformer_beamsearch_TSP50.ipynb'. Optimality gap: -0.004%.
   TSP100 : Run notebook 'test_tsp_transformer_beamsearch_TSP100.ipynb'. Optimality gap: 0.371%.
   
3. Visualization
   TSP50 : Run notebook 'visualization_TSP50.ipynb'
   TSP100 : Run notebook 'visualization_TSP100.ipynb'