1 of 12

Federico Berto*, Chuanbo Hua*, Junyoung Park*,

Minsu Kim, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Joungho Kim, Jinkyoo Park

NeurIPS 2023

New Frontiers in Graph Learning (GLFrontiers) Workshop

Oral Presentation

2 of 12

Neural Combinatorial Optimization (NCO)

2

Solution

Combinatorial Optimization (CO) Problems

(e.g., find shortest path among nodes on a graph)

CO solvers

Problem: many of these problems are NP-hard!

​

–> Can we “learn” solvers that are faster and/or effective than conventional hand-designed solvers? 🤔

​

2023-12-15

3 of 12

Example Problems

3

Routing Problems

Scheduling Problems

Electronic Design Automation

Motivation: the logistics industry is worth over 10 Trillion USD! (Statista, 2023)

2023-12-15

4 of 12

Taxonomy of NCO and why RL?

4

​

​

Training Scheme

​

​

Supervised

RL

Solving�Scheme

Improvement

DPDP, NeuroLKH, NCE …

EAS, COMPASS, NeuOpt…

Construction

Non-Autoregressive

Graph-MCTS, DIFUSCO…

DeepACO, GLOP…

Autoregressive

PtrNet, BQ-NCO, LEHD…

AM, POMO, Sym-NCO…

Currently, RL4CO primary focuses on “Autoregressive (AR) construction methods trained with RL” �due to two practical benefits over the other approaches:�(1) Do not require (near) optimal solutions to train�(2) Can be applied to vast CO problems with the strict constraints enforcements.

2023-12-15

5 of 12

RL4CO: Modular, flexible, and unified codebase for all things RL+CO

5

RL4CO is built upon:

​

  1. TorchRL: official PyTorch framework for RL algorithms and vectorized environments on GPUs
  2. TensorDict: a library to easily handle heterogeneous data such as states, actions and rewards
  3. PyTorch Lightning: a lightweight PyTorch wrapper for high-performance AI research
  4. Hydra: a framework for elegantly configuring complex applications

2023-12-15

6 of 12

Modularized AR Policy

6

We modularize policies with several reusable components. For example, we decouple the environment specific embeddings: Initial Embeddings, Context Embeddings and Dynamic Embeddings

(+ several tricks such as FlashAttention!)

2023-12-15

7 of 12

Few lines with additional PL superpowers

7

RL4CO is ready to supercharge Lightning powers!

Child classes of �Pytorch Lightning (PL) LightningModule and Trainer

2023-12-15

8 of 12

RL4CO: Some Benchmark Takeaways

8

  • Implementation matters!
  • Several tricks can change results
    • e.g. sampling more (i.e. more epochs, augmentations, code-level details)
  • We propose a new Pareto-optimal inference technique
  • State-of-the-art highly depends on how we evaluate
    • E.g. sample efficiency, inference methods, OOD generalization

2023-12-15

9 of 12

Future Works

9

​

​

We are expanding RL4CO in several directions!

​

Including but not limited to:

​

  • Problems: harder constraints (such as time windows), diverse problems (scheduling)
  • Models: non-autoregressive policies (NAR), neural improvement methods
  • RL algorithms: GFlowNets, recent training schemes
  • Integration with local search: C++ API to hybridize RL and heuristics
  • ... and more!

​

​

Wanna contribute? Just drop by :)!

​

2023-12-15

10 of 12

Resources

10

​

​

Follow the rl4.co link for code, the AI4CO Slack channel, and more!

pip install rl4co

Easy install the RL4CO with PyPI

2023-12-15

11 of 12

Last but not least…

11

​

​

bit.ly/ai4co-slack

✨ We are organizing the first

Neural Combinatorial Optimization (NCO) workshop at the next NeurIPS 🚀

​

​

✨ Join our Slack to find out more!

​

2023-12-15

12 of 12

Thanks for your

RL4CO Team

NeurIPS 2023

New Frontiers in Graph Learning (GLFrontiers) Workshop

Oral Presentation