chaitjo/graph-convnet-tsp chaitjo/graph-convnet-tsp

  • This repository has been archived on 27/Feb/2024
  • Stars
    star
    292
  • Rank 142,152 (Top 3 %)
  • Language
    Python
  • License
    MIT License
  • Created over 5 years ago
  • Updated almost 3 years ago
Twitter logo Share LinkedIn logo Share Facebook logo Share
chaitjo/graph-convnet-tsp
github

chaitjo

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Code for the paper 'An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem' (INFORMS Annual Meeting Session 2019)

An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

๐Ÿš€ Update: If you are interested in this work, you may be interested in our latest paper and up-to-date codebase bringing together several architectures and learning paradigms for learning-driven TSP solvers under one pipeline.

This repository contains code for the paper "An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem" by Chaitanya K. Joshi, Thomas Laurent and Xavier Bresson.

We introduce a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach outperforms all recently proposed autoregressive deep learning techniques in terms of solution quality, inference speed and sample efficiency for problem instances of fixed graph sizes.

model-blocks

Overview

The notebook main.ipynb contains top-level methods to reproduce our experiments or train models for TSP from scratch. Several modes are provided:

  • Notebook Mode: For debugging as a Jupyter Notebook
  • Visualization Mode: For visualization and evaluation of saved model checkpoints (in a Jupyter Notebook)
  • Script Mode: For running full experiments as a python script

Configuration parameters for notebooks and scripts are passed as .json files and are documented in config.py.

Pre-requisite Downloads

TSP Datasets

Download TSP datasets from this link: Extract the .tar.gz file and place each .txt file in the /data directory. (We provide TSP10, TSP20, TSP30, TSP50 and TSP100.)

Pre-trained Models

Download pre-trained model checkpoints from this link: Extract the .tar.gz file and place each directory in the /logs directory. (We provide TSP20, TSP50 and TSP100 models.)

Usage

Installation

We ran our code on Ubuntu 16.04, using Python 3.6.7, PyTorch 0.4.1 and CUDA 9.0.

Note: This codebase was developed for a rather outdated version of PyTorch. Attempting to run the code with PyTorch 1.x may need further modifications, e.g. see this issue.

Step-by-step guide for local installation using a Terminal (Mac/Linux) or Git Bash (Windows) via Anaconda:

# Install [Anaconda 3](https://www.anaconda.com/) for managing Python packages and environments.
curl -o ~/miniconda.sh -O https://repo.continuum.io/miniconda/Miniconda3-latest-Linux-x86_64.sh
chmod +x ~/miniconda.sh
./miniconda.sh
source ~/.bashrc

# Clone the repository. 
git clone https://github.com/chaitjo/graph-convnet-tsp.git
cd graph-convnet-tsp

# Set up a new conda environment and activate it.
conda create -n gcn-tsp-env python=3.6.7
source activate gcn-tsp-env

# Install all dependencies and Jupyter Lab (for using notebooks).
conda install pytorch=0.4.1 cuda90 -c pytorch
conda install numpy==1.15.4 scipy==1.1.0 matplotlib==3.0.2 seaborn==0.9.0 pandas==0.24.2 networkx==2.2 scikit-learn==0.20.2 tensorflow-gpu==1.12.0 tensorboard==1.12.0 Cython
pip3 install tensorboardx==1.5 fastprogress==0.1.18
conda install -c conda-forge jupyterlab

Running in Notebook/Visualization Mode

Launch Jupyter Lab and execute/modify main.ipynb cell-by-cell in Notebook Mode.

jupyter lab

Set viz_mode = True in the first cell of main.ipynb to toggle Visualization Mode.

Running in Script Mode

Set notebook_mode = False and viz_mode = False in the first cell of main.ipynb. Then convert the notebook from .ipynb to .py and run the script (pass path of config file as arguement):

jupyter nbconvert --to python main.ipynb 
python main.py --config <path-to-config.json>

Splitting datasets into Training and Validation sets

For TSP10, TSP20 and TSP30 datasets, everything is good to go once you download and extract the files. For TSP50 and TSP100, the 1M training set needs to be split into 10K validation samples and 999K training samples. Use the split_train_val.py script to do so. For consistency, the script uses the first 10K samples in the 1M file as the validation set and the remaining 999K as the training set.

cd data
python split_train_val.py --num_nodes <num-nodes>

Generating new data

New TSP data can be generated using the Concorde solver.

# Install the pyConcorde library in the /data directory
cd data
git clone https://github.com/jvkersch/pyconcorde
cd pyconcorde
pip install -e .
cd ..

# Run the data generation script
python generate_tsp_concorde.py --num_samples <num-sample> --num_nodes <num-nodes>

Resources

More Repositories

1

efficient-gnns

Code and resources on scalable and efficient Graph Neural Networks
Python
526
star
2

geometric-gnn-dojo

Geometric GNN Dojo provides unified implementations and experiments to explore the design space of Geometric Graph Neural Networks.
Jupyter Notebook
444
star
3

learning-tsp

Code for the paper 'Learning TSP Requires Rethinking Generalization' (CP 2021)
Jupyter Notebook
198
star
4

geometric-rna-design

gRNAde: Geometric Deep Learning for 3D RNA inverse design
Jupyter Notebook
138
star
5

personalized-dialog

Code for the paper 'Personalization in Goal-oriented Dialog' (NeurIPS 2017 Conversational AI Workshop)
Python
132
star
6

markowitz-portfolio-optimization

Markowitz portfolio optimization on synthetic and real stocks
Python
73
star
7

lstm-context-embeddings

Augmenting word embeddings with their surrounding context using bidirectional RNN
Python
60
star
8

regression-stock-prediction

Predicting Googleโ€™s stock price using regression
Python
58
star
9

gated-graph-transformers

Transformers are Graph Neural Networks!
Python
49
star
10

learning-paradigms-for-tsp

Code for the paper 'On Learning Paradigms for the Travelling Salesman Problem' (NeurIPS 2019 Graph Representation Learning Workshop)
Python
29
star
11

auto-mate-for-tinder

Use Artificial Intelligence to find promiscuous Tinder matches
CSS
24
star
12

knowledge-graphs

Building Knowledge Graphs from Unstructured Text
Jupyter Notebook
22
star
13

structured-self-attention

Keras implementation of the Structured Self-Attentive Sentence Embedding model
Python
19
star
14

flask-mongodb

A simple REST Api using Flask-Restful and MongoDB
Python
17
star
15

working-women

Code for the paper 'Working Women and Caste in India' (ICLR 2019 AI for Social Good Workshop)
Jupyter Notebook
14
star
16

music-library-ocd-fixer

Automatically fetch metadata for your music collection and rename files accordingly
Python
13
star
17

mnist-cnn-autoencoder

Using deep CNNs and stacked autoencoders to classify images of digits from the MNIST dataset
Python
7
star
18

Perceptron

Perceptron algorithm implemented from scratch
Python
6
star
19

nn-classification-and-regression

Using deep neural networks for classification and regression problems
Python
5
star
20

NTUOSS-MachineLearningWorkshop

Introductory Machine Learning workshop for NTU Open Source Society
Python
5
star
21

transformers-are-gnns

4
star
22

Velocity

A 2D lane-switching game made using the graphics.h C++ library
C++
1
star
23

PreparedForU

A simple tool for university aspirants and students in Singapore to estimate and visualize their spending based on publicly available data
Vue
1
star