RLCO-Papers

Reinforcement Learning based combinatorial optimization (RLCO) is a very interesting research area. Combinatorial Optimization Problems include: Travelling Salesman Problem (TSP), Single-Source Shortest Paths (SSP), Minimum Spanning Tree (MST), Vehicle Routing Problem (VRP), Orienteering Problem, Knapsack Problem, Maximal Independent Set (MIS), Maximum Cut (MC), Minimum Vertex Cover (MVC), Maximal Clique (MC), Integer Linear Programming (ILP), Network Optimization (Routing), Graph Coloring Problem (GCP), Bin Packing Problem, Graph Partitioning, EDA problems. Most of them are NP-hard or NP-complete. Combinatorial Problems can traditionally be solved by: exact method, heuristic method (genetic algorithm, simulated annealing), etc. Recently, better learning-based solvers are coming out.

This is a collection of resaerch & application papers of RLCO. Papers are sorted by time and categories. Some related supervised learning papers are also listed as a reference.

The sharing principle of these references here is for research. If any authors do not want their paper to be listed here, please feel free to contact [Haiguang Liao] (Email: haiguanl [AT] andrew.cmu.edu). Feedbacks on any mistakes on the repo are also welcomed

Review Papers:

• Reinforcement Learning for Combinatorial Optimization: A Survey Nina Mazyavkina et al. (Skolkovo Institute of Science and Technology, Russia)

Research Papers:

Papers are catgorized based on the solution approahces and ordered in time sequence:

1. Policy RL + (GNN)

• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning Yeong-Dae Kwon et al. NeurIPS 2020 (Samsung SDS)
• Reinforcement Learning for Integer Programming- Learning to Cut Yunhao Tang et al. ICML 2020 (Columbia University)
• Learning to Perform Local Rewriting for Combinatorial Optimization Xinyun Chen, Yuandong Tian. NeurIPS 2019 (UC Berkeley & Facebook AI Research)
• Attention, Learn to Solve Routing Problems! Max Welling et al. ICLR 2019 (Architecture: Graph Attention Network)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time Iddo Drori et al. 2020 (Columbia University, Cornell University)
• Reinforcement Learning Driven Heuristic Optimization Qingpeng Cai, Azalia Mirhoseini et al. DRL4KDD 2019 (Tsinghua University, Google Brain, Google AI)
• Neural Combinatorial Optimization with Reinforcement Learning Irwan Bello et al. ICLR 2017 (Google Brain)

2. Value RL + (GNN)

• Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case Paul Almasan et al. 2020
• Learning Combinatorial Optimization Algorithms over Graphs Hanjun Dai, Le Song et al. NeurlIPS 2017 (GaTech)

3. Supervised Learning + Tree Search + Graph Embedding

• Combinatorial Optimzation with Graph Convolutional Networks and Guided Tree Search Zhuwen Li et al. NeurlIPS 2017 (Intel)

Application Papers:

Papers are catgorized based on the application domains and ordered in time sequence:

1. Electronic Design Automation (EDA)

EDA is not easy. Some problems in EDA such as physical design (floorplan, placement, routing, etc.) can be formulated as combinatorial optimization problems. Thus, some of them are solved with RLCO.

• Track-Assignment Detailed Routing Using Attention-based Policy Model With Supervision Haiguang Liao et al. 2020 (CMU & Cadence)
• AutoCkt: Deep Reinforcement Learning of Analog Circuit Designs Keertana Settaluri et al. 2020 (UC Berkeley)
• Attention Routing: track-assignment detailed routing using attention-based reinforcement learning Haiguang Liao et al. 2020 (CMU & Cadence)
• Chip Placement with Deep Reinforcement Learning Azalia Mirhoseini et al. 2020 (Google)
• Placement Optimization with Deep Reinforcement Learning Anna Goldie, Azalia Mirhoseini ISPD 2020 (Google Brain)
• Placeto: Learning Generalizable Device Placement Algorithms for Distributed Machine Learning Ravichandra Addanki et al. 2019 (MIT CSAIL)
• GDP: Generalized Device Placement for Dataflow Graphs Yanqi Zhou et al. 2019 (Google Brain)
• A Deep Reinforcement Learning Approach for Global Routing Haiguang Liao et al. 2019 (CMU)
• A Hierarchical Model for Device Placement Azalia Mirhoseini et al. ICLR 2018 (Google)
• Device Placement Optimization with Reinforcement Learning Azalia Mirhoseini et al. ICML 2017 (Google Brain)

2. Path Planning (Routing)

RL has been extensively applied to robotic path planning, the papers listed here are only a tiny subset of those we think relevent to RLCO.

• Multi-Agent Routing Value Iteration Network Quinlan Sykora et al. PMLR 2020 (Uber)
• Value Iteration Networks (Code: https://github.com/kentsommer/pytorch-value-iteration-networks) Aviv Tamar et al. NeurlIPS 2016 (UC Berkeley)

3. Resource Management

• Resource Management with Deep Reinforcement Learning Hongzi Mao et al. ACM_HotNets 2016 (MIT & Microsoft Research)

Relevant Papers:

1. MLCO (Machine Learning for Combinatorial Optimization)

• Machine learning for combinatorial optimization: a methodological tour d’horizon Yoshua Bengio et al. 2020 (Universit´e de Montr´eal, etc.)
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking Natalia Vesselinova et al. 2020

2. ILCO (Imitation for Combinatorial Optimization)

• Exact Combinatorial Optimization with Graph Convolutional Neural Networks Maxime Gasse et al. NeurlIPS 2019 (Mila, Polytechnique Montréal, etc.)

3. GNN and CO

• Combinatorial optimization and reasoning with graph neural networks Quentin Cappart et al. (Polytechnique Montréal, UToronto, Deep Mind, etc.)

Relevant Resources:

Frameworks:

1. PyTorch Geometric (TU Dortmund University)
2. Deep Graph Library (Amazon Web Services, AWS Shanghai AI Lab, New York University, NYU Shanghai)

Libraries:

1. Facilate the learning of heuristics for CO problems similar to OpenAI Gym.

• OR-Gym (CMU)
• OpenGraphGym

2. Facilitate the learning of configuration parameters for CO solvers.

• MIPLearn

3. Offering a general, extensible framework for implementing and evaluating machine learning-enhanced CO, also based on OpenAI Gym.

• Ecole (Mila, Polytechnique Montréal)

Environments/Problems: