Giter Club home page Giter Club logo

tsp_transformer's Introduction

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'




tsp_transformer's People

Contributors

xbresson avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar

tsp_transformer's Issues

Checkpoint File Mismatch for TSP100 Test

model_baseline.load_state_dict(checkpoint['model_baseline']) throws an error complaining about missing/unexpected keys. After transforming the keys from "module.start_placeholder", "module.input_emb.weight"... etc. to the form "start_placeholder", "input_emb.weight" ... in the OrderedDict, this time I get the following size mismatches:
RuntimeError: Error(s) in loading state_dict for TSP_net:
size mismatch for encoder.norm1_layers.1.weight: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm1_layers.2.bias: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm1_layers.3.running_mean: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm1_layers.4.running_var: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm2_layers.0.weight: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm2_layers.1.bias: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm2_layers.2.running_mean: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm2_layers.3.running_var: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for encoder.norm2_layers.5.weight: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for decoder.decoder_layers.0.Wq_selfatt.weight: copying a param with shape torch.Size([128]) from checkpoint, the shape in current model is torch.Size([128, 128]).
size mismatch for decoder.decoder_layers.0.Wq_selfatt.bias: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for decoder.decoder_layers.0.Wk_selfatt.weight: copying a param with shape torch.Size([128]) from checkpoint, the shape in current model is torch.Size([128, 128]).
size mismatch for decoder.decoder_layers.0.Wv_selfatt.weight: copying a param with shape torch.Size([128]) from checkpoint, the shape in current model is torch.Size([128, 128]).
size mismatch for decoder.decoder_layers.0.W0_selfatt.weight: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128, 128]).
size mismatch for decoder.decoder_layers.0.W0_att.weight: copying a param with shape torch.Size([128]) from checkpoint, the shape in current model is torch.Size([128, 128]).
size mismatch for decoder.decoder_layers.0.Wq_att.weight: copying a param with shape torch.Size([128]) from checkpoint, the shape in current model is torch.Size([128, 128]).
size mismatch for decoder.decoder_layers.0.Wq_att.bias: copying a param with shape torch.Size([]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for decoder.decoder_layers.0.BN_selfatt.weight: copying a param with shape torch.Size([128, 128]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for decoder.decoder_layers.0.BN_att.weight: copying a param with shape torch.Size([128, 128]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for decoder.decoder_layers.0.BN_MLP.weight: copying a param with shape torch.Size([128, 128]) from checkpoint, the shape in current model is torch.Size([128]).
size mismatch for WK_att_decoder.weight: copying a param with shape torch.Size([128, 128]) from checkpoint, the shape in current model is torch.Size([256, 128]).
size mismatch for WK_att_decoder.bias: copying a param with shape torch.Size([128]) from checkpoint, the shape in current model is torch.Size([256]).
size mismatch for WV_att_decoder.weight: copying a param with shape torch.Size([128, 128]) from checkpoint, the shape in current model is torch.Size([256, 128]).
size mismatch for WV_att_decoder.bias: copying a param with shape torch.Size([128]) from checkpoint, the shape in current model is torch.Size([256]).

About training time

Hi,
I want to know how long it will take to train this model.
You set the epoch = 10000, and the depth of model is also twice that of Kool et-al, so I think the good results are probably due to this reason.May I ask if you have used the model of Kool et-al to do comparative experiment under the same super parameter setting?

Problem about the project

Hello Sir, currently I am doing a project related to this. I want to ask about the minimum requirement for the gpu to do this project. Thanks for your help.

Encoder Embedding

Dear Xavier,

We read your TSP transformer paper (https://arxiv.org/abs/2103.03012) quite interesting and have some questions regarding your paper and GitHub code.

In your Github ('train_tsp_transformer_TSP50.ipythonb') code, the input x with dimension (bsz, nb_nodes, dim_input_nodes) is embedded into x with dimension (bsz, nb_nodes, dim_emb). We are wondering why this embedding process (into dim_emb dimension) is needed for the TSP problem.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.