Neural combinatorial optimization

A peper list for machine learning models solving combinatorial problems, NP-hard problems and graph problems.

Tag abbreviations

• GAT: Graph Attention Networks
• GNN: Graph Neural Networks
• Graph ConvNet: Graph Convolutional Network
• NMT: Neural Machine Translation
• Seq2Seq: Sequence to Sequences model
• TSP: Traveling Salesman Problem
• PtrNet: Pointer Network
• RL: Reinforcement Learning

Paper list

Supervised learning

• Pointer Networks. [Vinyals | NIPS | 2015] [Paper] [Data]
  PtrNet Autoregressive TSP Convex hulls Delaunay triangulations

• Discriminative Embeddings of Latent Variable Models for Structured Data. [ICML | 2016] [Paper]
  Structure2Vect

• Residual Gated Graph ConvNets. [Bresson and Laurent | arXiv | 2017] [Paper]
  Graph ConvNet Graph problems

• Learning Combinatorial Optimization Algorithms over Graphs. [Dai et al. | NIPS | 2017] [Paper]
  Structure2Vect Graph problems, TSP RL

• Graph Attention Networks. [Velickovic et al. | arXiv | 2017] [Paper]
  GAT Graph problems

• Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks. [Nowak et al. | arXiv | 2017] [Paper]
  Non-autoregressive

• Data-Driven Approximations to NP-Hard Problems. [Milan et al. | AAAI | 2017] [Paper]
  PtrNet Data-driven TSP

• Boosting Dynamic Programming with Neural Networks for Solving NP-hard Problems. [Yang et al. | ACML | 2018] [Paper]
  Dynamic programming TSP

• Applying deep learning and reinforcement learning to traveling salesman problem. [Miki et al. | iCCECE | 2018] [Paper]
  TSP RL

• Learning heuristics for the tsp by policy gradient. [Deudon et al. | CPAIOR | 2018] [Paper]
  GAT RL Autoregressive 2OPT Local search

• Graph neural networks: A review of methods and applications. [Zhou et al. | arXiv | 2018] [Paper]
  GNN

• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem. [Joshi et al. | arXiv | 2019] [Paper] [Code] [Data]
  Graph ConvNet TSP Non-autoregressive Superviced Concorde Beam search

• Attention, Learn to Solve Routing Problems! [Kool et al. | ICLR | 2019] [Paper]
  GAT REINFORCE Autoregressive TSP

• On Learning Paradigms for the Travelling Salesman Problem. [Joshi et al. | arXiv | 2019] [Paper] [Code]
  TSP

• Solving Traveling Salesman Problem with Image-based Classification [Miki and Ebara | ICTAI | 2019] [Paper]
  Pixel-mapped Classification Network CNN TSP

• Solving Optimization Problems Through Fully Convolutional Networks: An Application to the Traveling Salesman Problem [Ling et al. | IEEE SMCS | 2020] [Paper]
  

Unsupervised learning

• Neural Combinatorial Optimization with Reinforcement Learning. [Bello et al. | ICLR | 2017] [Paper]
  PtrNet RL

Related papers

• The Graph Neural Network Model. [Scarselli et al. |IEEE | 2009] [Paper]
  GNN

• Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. [Cho et al. | EMNLP | 2014] [Paper]
  Seq2Seq NMT

• Sequence to Sequence Learning with Neural Networks. [Sutskever et al. | NIPS 2014] [Paper]
  Seq2Seq NMT

• Effective Approaches to Attention-based Neural Machine Translation. [Luong et al. | EMNLP | 2015] [Paper]
  Seq2Seq Attention NMT

• Neural Machine Translation by Jointly Learning to Align and Translate. [Bahdanau et al. | ICLR | 2015] [Paper]
  Seq2Seq Attention NMT

Solvers

• Concorde. [Site]
• LKH3. [Site]
• Gurobi. [Site]

Datasets

• TSPLIB. [Paper] [Site]