# RLOR: A Flexible Framework of Deep Reinforcement Learning for Operation
Research

Ching Pui WANLenovo Machine Intelligence CenterHong<EMAIL_ADDRESS>&Tung LILenovo Machine Intelligence CenterHong<EMAIL_ADDRESS>&Jason
Min WANGLenovo Machine Intelligence CenterHong<EMAIL_ADDRESS>
###### Abstract

Reinforcement learning has been applied in operation research and has shown
promise in solving large combinatorial optimization problems. However,
existing works focus on developing neural network architectures for certain
problems. These works lack the flexibility to incorporate recent advances in
reinforcement learning, as well as the flexibility of customizing model
architectures for operation research problems. In this work, we analyze the
end-to-end autoregressive models for vehicle routing problems and show that
these models can benefit from the recent advances in reinforcement learning
with a careful re-implementation of the model architecture. In particular, we
re-implemented the Attention Model and trained it with Proximal Policy
Optimization in CleanRL, showing at least 8 times speed up in training time.
We hereby introduce RLOR, a flexible framework for Deep Reinforcement Learning
for Operation Research. We believe that a flexible framework is key to
developing deep reinforcement learning models for operation research problems.
The code of our work is publicly available at https://github.com/cpwan/RLOR.

##  1 Introduction

Pointer Network (Vinyals et al., 2015) is a milestone work of applying neural
networks in combinatorial optimization problems. It enabled dynamic input size
and permutation invariance of input in the neural networks. In other words, we
can feed a set to a neural network. PN+RL (Bello et al., 2019) is another
milestone work. It enabled training neural networks with reinforcement
learning (RL) with REINFORCE algorithm, instead of requiring expensive ground
truths from solvers for supervised learning. Since then, the REINFORCE
algorithm (but rarely other RL algorithms) has been used in subsequent works
for vehicle routing problems, including Order-invariant PN+ RL (Nazari et al.,
2018), Attention Model (Kool et al., 2019), and POMO (Kwon et al., 2020).
Stemming from the same milestone works, DQN was preferred for graph problems,
such as in S2V-DQN (Dai et al., 2017), ECO-DQN (Barrett et al., 2020), and
GCOMB (Manchanda et al., 2020). These streams of work focused on improving
model architectures instead of exploring more advanced RL algorithms.

On the other hand, the RL community has been growing. Several RL platforms
have been proposed for academic research and industrial applications,
including StableBaselines3 (Raffin et al., 2021), RLlib(Liang et al., 2017),
DI-Engine(Contributors, 2021), Tianshou(Weng et al., 2022), and CleanRL(Huang
et al., 2022b). These RL platforms have their design philosophies and
different levels of abstraction to accommodate numerous RL algorithms.
Nevertheless, they share several similarities. In contrast to the complicated
model architectures used for vehicle routing problems, an MLP model
architecture and a 1-d vector input are assumed in most of the RL platforms.
Moreover, REINFORCE (or policy gradient), the most popular algorithm for end-
to-end vehicle routing problems, was not implemented in most of these RL
platforms. It was claimed by their developers that the 31 years old REINFORCE
algorithm (Williams, 1992) usually does not perform well compared to the
recent RL algorithms. The disentanglement has been demonstrated between the
advances in model architecture and RL algorithms.

A natural question arises: can we leverage the advanced algorithms in the RL
platforms for vehicle routing problems? In this work, we will demonstrate a
Yes to this question. However, it is a challenging task, due to two major
reasons: compatibility and efficiency. In the RL platforms, they accept agents
built with an MLP model, a CNN model, or even an RNN model, but none of them
has considered the attention model in their design. (DI-Engine (Contributors,
2021) implements DecisionTransformer (Chen et al., 2021) but it is considered
as an algorithm instead of an agent building block) As a result, it would
require a huge effort to modify the RL platform to allow nested observations,
dynamic input size, and management between hidden states. Eventually, the
model architecture can be trained in the RL platform after fixing the
compatibility issue. However, it still suffers from the efficiency issue. For
instance, the RL platforms have their own environment APIs and there are
different levels of overhead in data transformation and device communications
(between CPU/GPU). We performed experiments on several RL platforms and find
that CleanRL (Huang et al., 2022b) has the lowest overhead and thus the
highest efficiency.

We introduce the RLOR framework, which consists of four parts: model,
algorithm, environment, and search. The model describes the neural network
model architecture. Our default model is developed and refactored from the
Attention Model (Kool et al., 2019). The algorithm describes the RL algorithm.
We adapted the Proximal Policy Optimization (PPO) algorithm from CleanRL to
our problems. The environment describes the RL environments. We followed the
protocol of the OpenAI Gym (Brockman et al., 2016) when defining RL
environments for the operation research problems. The search defines the
decoding strategies of the neural network, such as greedy or sampling.

Our major contributions are in three-folds:

  1. 1.

As far as we know, it is the first work to incorporate end-to-end vehicle
routing model in modern RL platforms

  2. 2.

It speeds up the training of Attention Model by 8 times (e.g., 25 hours $\to$
3 hours)

  3. 3.

It introduces a flexible framework for developing model, algorithm,
environment, and search for operation research

In Section 2, we will discuss the related works. In Section 3, 4,5, 6, we will
discuss how we solve the compatibility issues and integrate model, algorithm,
environment, and search for OR models in RL platforms. In Section 7, we will
discuss how we solve the efficiency issues of the OR model in RL platforms. In
Section 8, we will discuss the results of our experiments. We will refer
“model” as the neural network and “OR models” as neural networks applied to
operation research problems. We will refer “trajectory” as the sequence of
actions and states until a given number of steps while a “rollout” is a
complete trajectory.

##  2 Related Work

#### Supervised learning methods.

Earlier deep learning approaches to solving combinatorial optimization
problems mostly featured supervised learning. Pointer Network (Vinyals et al.,
2015) formulated the combinatorial optimization problem as a sequence-to-
sequence problem and predicted the target sequence obtained from a numerical
solver. Later works (Joshi et al., 2019; Li et al., 2018) employed Graph
Neural Network to predict the adjacency matrix of the optimal solution and
performed searches over the adjacency matrix, showing better performance.
However, their supervised learning natures implied expensive training set
collection. The resulting model also had limited generalization power.
Generalized GNN (Fu et al., 2020) and DPDP (Kool et al., 2021) tried to
address the generalization issues with GNN model by introducing advanced
search techniques (Monte Carlo Tree Search, dynamic programming). However, the
analysis from Böther et al. (2022) suggested that the performance of the
supervised learning model may (in general) be contributed by the search
routine instead of the model architecture. Therefore, we turn our attention to
the deep RL approach.

#### Deep RL methods.

There are two streams of approaches for applying RL in solving combinatorial
optimization problems: the construction method, and the improvement method.
Construction methods, such as PN+RL (Bello et al., 2019), Attention Model
(Kool et al., 2019), POMO (Kwon et al., 2020), constructed the solution step
by step. On the other hand, the improvement methods such as Learning
Improvement Heuristics (Wu et al., 2019), (Lu et al., 2020), NeuRewritter
(Chen & Tian, 2019), DACT (Ma et al., 2021), started with a complete solution
and predicted the location for local rewriting to search for a better
solution. The improvement methods were much slower than the construction
methods but could obtain a better solution. Instead of predicting the local
rewriting with a neural network, eMagic (Ouyang et al., 2021) performed local
search (a heuristic) to find better rollouts during the RL training of their
construction method. There were also efforts to combine tree search techniques
from constraint programming in the work of Cappart et al. (2021). Readers
interested in the recent advances in neural combinatorial optimization can
refer to the survey blog of Joshi & Anand (2022).

#### RL libraries.

RL platforms provide training pipelines for a variety of RL algorithms.
Popular RL platforms include StableBaselines3 (Raffin et al., 2021), RLlib
(Liang et al., 2017), DI-Engine (Contributors, 2021), Tianshou (Weng et al.,
2022), and CleanRL (Huang et al., 2022b). In our work, we employ the PPO
algorithm provided by these RL platforms. Readers interested in the
implementation of PPO can refer to the blog of Huang et al. (2022a). On the
other hand, we reformulated OR problems into RL environments so that they can
communicate with RL algorithms through the environment API. OpenAI Gym
(Brockman et al., 2016) provides standardized API defining RL environments and
is supported in most of the RL platforms. OR-Gym (Hubbs et al., 2020)
implements RL environments for a couple of small-scale operation research
problems. Graphenv (Biagioni et al., 2022) implements the RL environment for
travelling salesman problem (TSP) while conforming to RLlib’s environment API.

##  3 Model

Figure 1: The model architecture (Backbone, Actor, and Critic) of the
refactored Attention Model. The neural networks in blue represent MLPs while
those in purple represent multi-head attention layers.

We performed detailed code reviews for the Pointer Network (Vinyals et al.,
2015) and the Attention Model (Kool et al., 2019). The pseudocodes for these
model architectures can be found in Appendix B. We refactored both models and
upgraded them to the latest PyTorch 1.13. In this section, we will focus on
the Attention Model, which we found easier to integrate into RL platforms.

The overview of the refactored Attention Model can be found in Figure 1. We
will use the capacitated vehicle routing problem (CVRP) as an example to
illustrate the workflow of the refactored Attention Model. The node-wise
static features (coordinates of customers and depots) and the node-wise
dynamic features (demands of customers) are projected to the static embedding
and dynamic embedding independently for each node. The static embeddings of
different nodes are integrated in the encoder. The dynamic embedding and the
encoder output are concatenated and serve the key and value of the decoder.
The global features (the current load of the vehicle) are projected to a
latent representation of the global context and serve the query of the
decoder. The decoder predicts a probability distribution of the next action
(which node to visit next) along with the latent representation of the current
environment state. The original implementation of Attention Model Kool et al.
(2019) concluded the model at the decoder. In our refactored version, we add
additional modules — Actor and Critic to better conform to the design of RL
algorithms.

Backbone. We regard the aforementioned steps from input embedding to the
decoder as the backbone. It is responsible for most of the computation. The
backbone provides the probability distribution for the actor model and latent
representation of the environment state to the critic model.

Actor model. The actor model selects an action from the probability
distribution and sends it to the RL environment. The RL environment then
returns the next observation. The state (node’s features and global features)
is updated accordingly and is used for the next iteration.

Critic model. The critic model predicts the value of the current state (i.e.,
the average reward we can claim starting from the current state). To predict
the value effectively, we need to feed the critic model with sufficient
information about the state. In particular, we feed the critic model with the
glimpse of the last attention layers of the decoder.

Our reformulation of the Attention Model provides a more compatible
interaction among the neural network model, the RL algorithm, and the RL
environment.

###  3.1 Adapting OR models to RL platforms

(a) OR model pipeline

(b) RL platform pipeline

Figure 2: Comparison of action sampling pipelines between OR model and RL
platform. The OR model samples action from the decoder and updates the
internal states directly until all steps in a rollout are completed. In
contrast, RL platforms sample action step-by-step during the interaction with
the RL environment and require a complete forward pass of the neural network.

Since the RL platforms employ step-wise sampling, instead of rollout-wise
sampling in OR models, we need to modify the OR models. In Figure 2, we
illustrate the difference in the pipelines. In RL platforms, a forward pass of
the entire neural network model is performed and only the action can be used
to update the next state. This is in contrast to OR models, where the internal
state of the neural network can also affect the next prediction.

Pointer Network. The step-wise sampling of environment interaction makes it
difficult to implement Pointer Network in RL platforms. In Pointer Network,
the hidden state of the LSTM layers in the decoder is used to pass information
across steps in a rollout while the output of the encoder is reused for each
of the decoding steps. Some RL platforms (RLlib, Tianshou) support RNN models
by passing the detached hidden state as additional information along with the
observations, allowing the decoder to be trained. However, if we also treat
the encoder output as additional information, the gradient would not be back-
propagated to the encoder. Alternatively, some RL platforms (Tianshou) allow
passing a non-detached hidden state, but they do not guarantee that hidden
states can be consumed in the same iteration. As a result, the non-detached
encoder output may be consumed in later iterations when the model has already
been updated, resulting in a runtime error in PyTorch.

Attention Model. The same difficulty exists in implementing the Attention
Model in the RL platforms. However, there is a workaround — with a sacrifice
of efficiency. In our refactored Attention Model, the decoder does not depend
on its previous hidden states. Instead, it can obtain all step-wise
information from the state extracted from the RL environment observation.
Hence, for each RL environment step, we can perform a feed-forward for the
entire refactored Attention Model as shown in Figure 2(b). Each component of
the Attention Model can be trained with this paradigm. However, the same
encoder output is recomputed every time. In most of the RL platforms, it is
unavoidable to make this trade-off in order to enable the training of the
Attention Model.

##  4 Algorithm

###  4.1 RL algorithms in OR models

In preceding works for vehicle routing problems, REINFORCE algorithm was used.
In RL platforms, the REINFORCE algorithm is more often referred as Policy
Gradient (PG). The goal of policy gradient with respect to an environment
instance $s$ is to maximize the expected return

$J(\theta|s)=\mathbb{E}_{\pi\sim p_{\theta}(.|s)}[L(\pi|s)]$ (1)

where $\theta$ is the neural network parameter, $\pi$ is the policy (in OR
model context, the complete sequence of actions) drawn from the actor
$p_{\theta}(.|s)$, and $L(\pi|s)$ is the return of executing policy $\pi$ on
the environment instance $s$.

The REINFORCE algorithm derived the gradient of the expected return as the
following:

$\nabla_{\theta}J(\theta|s)=\mathbb{E}_{\pi\sim
p_{\theta}(.|s)}[(L(\pi|s)-b(s))\nabla_{\theta}\log(p_{\theta}(\pi|s))].$ (2)

where $b(s)$ is the baseline. Intuitively, the return $L(\pi|s)$ is compared
against the baseline $b(s)$. The better (relatively) the return $L(\pi|s)$,
the higher the log-likelihood the policy $\log(p_{\theta}(\pi|s))$ contributes
to the gradient. Theoretically, a good choice of baseline $b(s)$ reduces the
variance of the gradient and potentially leads to faster convergence. The
preceding works for vehicle routing problems designed different baselines for
the policy gradient. Interested readers may refer to Appendix A for the
modifications they made.

###  4.2 RL algorithms in RL platforms

The formulation of policy gradient and its variants in RL platforms follows a
similar derivation from the REINFORCE algorithm. However, the policy $\pi$ in
Equation 1 is explicitly broken down into a sequence of actions
$\pi=\pi_{0},\pi_{1},...,\pi_{T}$ and the expectation in Equation 2 is then
with respect to each of these actions. The return $L(\pi|s)$ is broken down to
the sum of rewards $r(\pi_{t}|s_{t})$. The $L(\pi|s)-b(s)$ term is replaced by
a step-wise estimate $L(\pi_{t}|s_{t})-b(s_{t})$, in which $L(\pi_{t}|s_{t})$
is the sum of future rewards and $b(s_{t})$ can be predicted by the critic. As
an illustration of the algorithmic difference, we may compare Equation 2 with
the gradient computed from the step-wise estimate in RL platforms:

$\nabla_{\theta}J(\theta|s)=\mathbb{E}_{t\sim\\{0...T\\},\pi_{t}\sim
p_{\theta}(.|s_{t})}[(L(\pi_{t}|s_{t})-b(s_{t}))\nabla_{\theta}\log(p_{\theta}(\pi_{t}|s_{t}))].$
(3)

Variants of policy gradient use different step-wise estimate. For example, A2C
uses the advantage $A(\pi_{t}|s_{t})$ computed from the rewards and critic
predictions; PPO further applies clipping on the advantage with a regulation
on the deviation of the policy. The comparison of RL algorithms in OR models
and RL platforms is summarized in Table 1. We accommodated the pipeline of the
OR model to that of the RL platforms in Section 3.1.

| OR models | RL platforms
---|---|---
Algoritms | REINFORCE | A2C, PPO, DQN, …
Unit of sample | a full rollout $\\{s_{0},\pi_{0},s_{1},...,\pi_{T},s_{T+1}\\}$ | one step $s_{t},\pi_{t},s_{t+1}$
Actor predicts… |  $n$ actions in one go |  $1$ action each time
Critic predicts… | not used, baseline is derived from previous rollouts | the value of the current state

Table 1: Comparison of the RL algorithm used in OR models and RL platforms.

##  5 Environment

The primary settings and constraints of the vehicle routing problem
environments are referenced from Attention Model paper (Kool et al., 2019),
and adapted into OpenAI Gym (Brockman et al., 2016). The OpenAI Gym
environment interface is supported in most RL platforms. The environment for
each problem needs to be carefully designed such that the necessary
information would be included in the observation returned by the OpenAI Gym
environment, and a wrapper is required to transform the observation into the
schema that the RL platforms intend to receive.

###  5.1 Interface

The following steps of the OR model involve interactions with the environment:

  * •

Initialize the environment for the problem instance $s$.

  * •

Update the environment with the selected action $\boldsymbol{\pi}_{t}$.

  * •

Get whether the policy $\\{\boldsymbol{\pi}_{t}\\}$ has finished.

  * •

$\mathrm{Context}$ needs to get the global information, such as remaining
vehicle capacity.

  * •

$\mathrm{DynamicEmbedding}$ needs to get the dynamic node features.

  * •

$\mathrm{mask_{t}}$ needs to get the feasible actions.

An RL environment for vehicle routing problems should provide the following
interfaces:

⬇

class RequiredEnv():

def __init__(self, s: problem_instance): …

def step(self, action): …

def get_global_context(self): …

def get_dynamic_node_features(self): …

def get_mask(self): …

def all_finished(self): …

Compare to the OpenAI Gym environment interface:

⬇

class GymEnv():

def __init__(self, arg1, arg2, …):

# What action can be taken?

self.action_space = …

# What information can we get from the problem?

self.observation_space = …

def step(self, action):

…

return observation, reward, done, info

def reset(self):

…

return observation

To translate the `GymEnv} to our \mintinline`pythonRequiredEnv, we need to
store the results of the `GymEnv.step(action)}. When the
\mintinline`pythonRequiredEnv.get_xxxx function is called, we extract the
corresponding information from the stored `observation}. When the
\mintinline`pythonRequiredEnv.all_finished function is called, we extract the
corresponding information from the stored

    done}.
    \subsection

Adaptation to RL libraries Here, we give an example to adapt the RL libraries
interface to the Attention Model. We use CleanRL as an example for
demonstration purpose. In CleanRL, the observations from the environment is
referred as `next_obs} and is passed to the model in each step of an episode.
The \mintinline`pythonnext_obs is a `dict} of tensors. In particular, for TSP,
the \mintinline`pythonnext_obs has the following contents:

`[B,n,2]} &\mintinline`pythonfloat | coordinates of nodes
---|---
`[B] } & \mintinline`pythonint | the index of the first node visited
`[B]} & \mintinline`pythonbool | whether the current step is the first step

On the other hand, the Attention Model for TSP requires a couple of data
members and functions from a

    state} object:
    \begin

center  `shape} & \mintinline`pythontype descriptions `[B,1] } &
\mintinline`pythonint the index of the first node visited `[B]} &
\mintinline`pythonbool whether the current step is the first step Hence, we
define a wrapper to translate from the nested observations dict `(next_obs :
dict)} collected by CleanRL to the object \mintinline`python(state : object)
that our model required.

⬇

# wrapper for the problem

class stateWrapper:

”””

From dict of numpy arrays

to an object that supplies PyTorch tensors.

”””

\pardef __init__(self, next_obs, device, problem):

self.device = device

self.states = {k: torch.tensor(v, device=self.device)

for k, v in next_obs.items()}

if problem == ’tsp’:

self.is_initial_action = \ self.next_obs[”is_initial_action”].to(torch.bool)

self.first_a = self.next_obs[”first_node_idx”]

elif problem == ’cvrp’:

input = {’loc’: self.next_obs[’observations’],

’depot’: self.next_obs[’depot’].squeeze(-1),

’demand’: self.next_obs[’demand’]}

self.states[’observations’] = input

self.VEHICLE_CAPACITY = 0

self.used_capacity = -self.next_obs[”current_load”]

\pardef get_current_node(self):

return self.states[”last_node_idx”]

\pardef get_mask(self):

return (1 - self.states[”action_mask”]).to(torch.bool)

\par# Inside the Attention Model

state = stateWrapper(next_obs)

##  6 Search

During inference, we are searching for a solution with the probability
distribution predicted by the Attention Model. In RL platforms, the action of
an agent is mostly selected in two ways: greedy (choosing the highest
probability action), or sampling (selecting an action according to the
probability distribution). In contrast, some works on OR models borrow beam
search from NLP (Nazari et al., 2018) or fine-tune the model on test instance
with Efficient Active Search (Hottung et al., 2022). In the work by Cappart et
al. (2021), they treated the probability distribution as a heuristic and
performed a tree search accordingly. In our implementation, we borrow the idea
of POMO (Kwon et al., 2020) for searching. In POMO, it performed greedy
rollouts with different starting nodes during inference. We denote this
decoding strategy as Multi-Greedy.

##  7 Efficient Training on RL platform

We implemented our refactored Attention Model in 4 major RL platforms: DI-
engine, RLlib, Tianshou, and CleanRL. We did not implement it on
StableBaselines3 due to engineering difficulties. We found that CleanRL has
the highest efficiency in environment step collection and the best
convergence. The results will be discussed in Section 8. We found that even
the best RL platform could not beat the performance of the original
implementation. We performed a detailed analysis and developed several ways to
improve the training efficiency of our OR model on CleanRL.

###  7.1 Reducing communication overhead

We found that the communication overhead between GPU/ CPU devices is one of
the major overheads in the RL platforms. For example, we profiled DI-engine
and found that 30% of the computation was spent on data manipulation for
observations and moving the data across devices. In CleanRL, we implement the
RL environment with Numpy and convert the observations (in NumPy array) to
PyTorch Tensor on GPU in the state wrapper. That is, data collected from the
environment are moved to GPU only when it is needed for the forward pass. The
ad-hoc conversion of data across devices reduces the communication overhead
and makes CleanRL the most efficient RL platform for our problems.

###  7.2 Cached Encoder

In Section 3.1, we mentioned that we have to sacrifice the efficiency of the
OR model to accommodate the workflow of the RL platforms. To retain the
efficiency, we modify the CleanRL to allow caching of the encoder output. We
enable cached encoder during both value bootstrapping and model training. The
encoder output is computed once and is passed to the decoder for sampling the
action and values until the environment is done. We enforce that the encoder
output has to be consumed in the same iteration. The decoder is fed with the
non-detached version of the encoder output. The back-propagation is performed
only when the forward pass for every step is done. In this way, the encoder
can be updated with the gradients computed from every environment step. We
profiled the implementation and found that it could save $\sim$ 80%
computation during forward pass by caching the encoder output.

###  7.3 Larger Batch

With the PPO algorithm, the training is more stable and we can use a larger
learning rate with a larger batch-size. In particular, we collect $1024\cdot
51$ steps in a batch and train our model with 8 minibatch (minibatch-size =
6528) for the 50-nodes TSP. A larger learning rate of $10^{-3}$ can be used
without weight decay. It takes 6.9 GiB GPU memory. It may scale further but we
want to keep it compact so that it can be fitted in an affordable GPU (for
instance, those in the free-tier Colab notebook).

###  7.4 Parallel decoding

In Section 7.2, we share the encoder output across environment steps. In this
section, we further speed up computation by sharing the encoder output across
different trajectories of the same RL environment instance. The dynamic nodes
features and global context constitute the query in the attention layers of
the decoder. The Attention Model only passes one query (which corresponds to
one trajectory) to the decoder per environment. We can pass multiple queries,
each corresponding to different trajectories, to the decoder. By decoding
multiple trajectories in parallel in the GPU, we obtain better efficiency than
decoding them separately. The pseudo-code of the attention layer can be found
in Appendix B.2. We replace the query $q$ with a higher dimension tensor
${\bm{q}}$. Note that, during training, we sample the trajectories according
to the probability distribution predicted by the decoder. This is in contrast
to POMO (Kwon et al., 2020) in which different starting nodes are enforced.

###  7.5 Environment Vectorization

We implemented a bi-level vectorized environment. The first level is the
OpenAI Gym vector environment consisting of multiple sub-environments. In each
of these sub-environments, we implemented another layer of sub-environment —
vectorized environment written in Numpy’s vectorized operations. For example,
we can create a $M\times N$ bi-level vectorized environment, in which there
are $M$ RL environment instances and $N$ trajectories for each of the
instances. We profiled the implementation and found that the bi-level
environment vectorization can bring a 10x speed up for environment steps
collection for $M=1024,N=50$. More on the design of the bi-level environment
vectorization can be found in Appendix C

##  8 Experiment Results

Method | TSP50 | CVRP50
---|---|---
Len. | Gap | Time | Steps | Len. | Gap | Time | Steps
Optimal | 5.69 | 0.00% | - | - | 10.38 | 0.00% | - | -
Kool et al. (2019) (PG) | 5.80 | 1.93% | 25h | 6.5G | 10.98 | 5.78% | 33h | 7.8G
DI-Engine (PPO) | 5.90 | 3.69% | 3d | 480M | - | - | - | -
RLlib (PPO) | 6.15 | 8.08% | 3d | 153M | - | - | - | -
Tianshou (PPO) | 6.19 | 8.79% | 3d | 611M | - | - | - | -
CleanRL (PPO) | 5.83 | 2.46% | 3d | 1.7G | - | - | - | -
Ours (PPO) | 5.79 | 1.76% | 24h | 30G | 10.91 | 5.11% | 24h | 21G
\+ Multi-Greedy | 5.71 |  0.35% | 24h | 30G | 10.82 |  4.23% | 24h | 21G
Table 2: Experiment results across implementations and RL platforms. The second row refers to the original implementation of the Attention Model. The middle rows refer to our implementation on different RL platforms. The last two rows refer to our implementation with a bag of tricks. The RL algorithm in each implementation is indicated in the bracket. Experiments are done on 50-nodes TSP and 50-nodes CVRP environment. Method | Time | Env Steps | Performance
---|---|---|---
Kool et al. (2019) (PG) | 50m | 65M | 6.00
DI-Engine (PPO) | 12h | 40M | 6.00
RLlib (PPO) | - | - | 6.00
Tianshou (PPO) | - | - | 6.00
CleanRL (PPO) | 3h | 70M | 6.00
Ours (PPO) | 14m | 250M | 6.00
Table 3: Time and environment steps required to reach 6.0 in route length
($\sim$ 5% gap) in the 50-nodes TSP. The first row refers to the original
implementation of the Attention Model. The middle rows refer to our
implementation on different RL platforms. The last row refers to our
implementation with a bag of tricks. The RL algorithm in each implementation
is indicated in the bracket. RLlib and Tianshou did not attain the performance
in a reasonable time.

#### Training.

We first describe our experiment settings. We used the refactored Attention
Model as our agent for all OR problems. We trained our agent with the PPO
algorithm in RL platforms. The training was done with the Adam optimizer with
a learning rate of $\eta=10^{-3}$ on a single Titan RTX GPU. Each epoch
consists of 1024 randomly generated RL environment instances. For comparison,
we also trained the original implementation of the Attention Model from Kool
et al. (2019). We followed its default setting and trained it for 100 epochs
on the same GPU.

#### Inference.

For each problem, the performance is measured on the 10000 test instances as
being done in Kool et al. (2019). The optimality gap is calculated with
respect to the length of the optimal route of the vehicle routing problem
instance. Greedy search is the default decoding strategy for the Attention
Model. For Multi-Greedy search, we perform $n=50$ greedy searches with
different start nodes and select the best trajectory.

###  8.1 Attention Model On Different RL platforms

We integrated our refactored Attention Model on several RL platforms and
trained it with the PPO algorithm provided in these RL platforms. The results
are summarized in Table 2. We found that none of these RL platforms were able
to attain the performance of the original implementation of the Attention
Model. We speculate that the discrepancy between RL platforms and the original
implementation originated from the efficiency of the model-environment
interactions and data manipulations. In particular, CleanRL employed the most
efficient vector API (with the fastest environment step collection among the
RL platforms), and produced the best results among the RL platforms. We
observed a positive correlation between the number of environment steps and
the final performance across the RL platforms. It indicated that the
efficiency in environment step collection could be vital for reaching a
tighter optimality gap. Based on this assumption, we improved the training
efficiency on CleanRL with a bag of tricks which has been elaborated on in
Section 7. With the improved implementation, we were able to surpass the
Attention Model (Kool et al., 2019) in both training time and the optimality
gap. Our approach collected 5 times more environment steps and reached a
better objective given at the same time. With Multi-Greedy search, we can
obtain an even better performance. We observed a similar performance boost for
the CVRP50 instances. From another perspective, our approach can reach the
same optimality gap with a shorter training time. Table 3 reported the time
required to reach 5% gap for the 50-nodes TSP. Among the others, our approach
was the most efficient and it took only 14 minutes for the training. Our
approach is appealing in that it can train a sufficiently good OR model in a
short training time. It can accelerate the development of a new OR model. For
instance, hyper-parameter tuning can be done in a shorter time.

Method | Training Time | Env Steps | Performance
---|---|---|---
Kool et al. (2019) | 25h | 6.5G | 5.80
Baseline | 11d | 6G | 5.79
\+ Cached Encoder | 4d | 6G | 5.79
\+ Larger Batch | 2.5d | 6G | 5.79
\+ Parallel Decoding & Env Vectorization | 24h | 32G | 5.79
\+ Multi-Greedy | 3h | 5G | 5.79
Table 4: Ablation study on different components of our framework. The first
row refers to the original implementation of Attention Model. The following
rows refer to the designs in our framework. Experiments were done on the
50-nodes TSP.

###  8.2 Ablation Study

As an ablation study, we performed experiments with CleanRL with different
parts of our design. The results are shown in Table 4. We can observe
significant improvements with the components. By caching the encoder outputs,
we were able to greatly reduce unnecessary re-computation during training. We
profiled the implementation and found that 80% of the training time can be
saved by caching the encoder output. By using a larger batch with a higher
learning rate, we could scale the training while fitting the training inside a
single GPU. By using parallel decoding and the bi-level environment
vectorization, we were able to substantially increase the environment steps
trained per second, boosting the collection efficiency of the environment
observations. With these designs, our implementation has already surpassed the
original implementation of the Attention Model. Lastly, by employing Multi-
Greedy search during inference, we were able to achieve the same performance
in just 3 hours.

Method | TSP50 | CVRP50
---|---|---
Len. | Gap | Time | Steps | Len. | Gap | Time | Steps
Optimal | 5.69 | 0.00% | - | - | 10.38 | 0.00% | - | -
POMO (PG) | 5.73 | 0.70% | 24h | 61G | 10.84 | 4.43% | 24h | 55G
\+ Multi-Greedy | 5.71 |  0.32% | 24h | 61G | 10.60 | 2.21% | 24h | 55G
Ours (PPO) | 5.79 | 1.76% | 24h | 30G | 10.91 | 5.11% | 24h | 21G
\+ Multi-Greedy | 5.71 | 0.35% | 24h | 30G | 10.82 | 4.23% | 24h | 21G
Table 5: Experiment results compared to POMO. The RL algorithm in each
implementation is indicated in the bracket. Experiments are done on 50-nodes
TSP and 50-nodes CVRP.

###  8.3 Potential extension with POMO

As a comparison, we also trained the implementation from POMO (Kwon et al.,
2020), a state-of-the-art construction method. We used equivalent model
settings (e.g., 3 encoder layers) and trained POMO for 24 hours. The result is
reported in Table 5. We note that our method did not outperform POMO. In our
design, we attempt to modularize the model, algorithm, environment, and
search, in order to create a flexible and comprehensive framework for
developing deep RL model for the operation research problem. We made a trade-
off between flexibility and the environment step collection efficiency. For
instance, we could implement the entire vectorized environment in PyTorch and
obtain higher efficiency in environment step collection. Yet, it will incur
burdens on fine-grained control over the RL environment. Nevertheless, we are
still close behind the state-of-the-art benchmark, with a clean one-page code
defining the environment, a one-page code for the algorithm, and a refactored
modularized neural network architecture. In addition, we demonstrated that PPO
is a viable algorithm for solving vehicle routing problems, as seen from its
better performance with the Attention Model. Moving forward, our work can be
further improved with more recent advances in OR models and RL algorithms. For
instance, we only borrow the Multi-Greedy search strategies from POMO, yet its
multi-start-nodes training strategy and inference augmentation strategy may
also be helpful. We hope our work will serve as a new avenue for future
vehicle routing problem research.

##  9 Conclusion

In this paper, we presented RLOR, a flexible framework of deep reinforcement
learning for operation research that leverages recent advances in
reinforcement learning algorithms. RLOR provides a comprehensive end-to-end
deep learning model on a modern RL platform while improving the training
efficiency of the original implementation of the Attention Model. We evaluated
the performance of RLOR on the travelling salesman problem and capacitated
vehicle routing problem. We demonstrated the improvement of RLOR over the
original implementation of the Attention Model, showing the potential of the
RLOR framework.

## References

  * Barrett et al. (2020) Thomas D. Barrett, William R. Clements, Jakob N. Foerster, and A. I. Lvovsky.  Exploratory Combinatorial Optimization with Reinforcement Learning.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(04):3243–3250, 4 2020.  ISSN 2374-3468.  doi: 10.1609/AAAI.V34I04.5723.  URL https://ojs.aaai.org/index.php/AAAI/article/view/5723.
  * Bello et al. (2019) Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio.  Neural combinatorial optimization with reinforcement learning.  In _5th International Conference on Learning Representations, ICLR 2017 - Workshop Track Proceedings_ , 2019.
  * Biagioni et al. (2022) David Biagioni, Charles Edison Tripp, Struan Clark, Dmitry Duplyakin, Jeffrey Law, and Peter C St John.  graphenv: a Python library for reinforcement learning on graph search spaces.  _Journal of Open Source Software_ , 7(77):4621, 2022.
  * Böther et al. (2022) Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich.  What’s wrong with deep learning in tree search for combinatorial optimization.  _arXiv preprint arXiv:2201.10494_ , 2022.
  * Brockman et al. (2016) Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  OpenAI Gym, 2016.
  * Cappart et al. (2021) Quentin Cappart, Thierry Moisan, Louis Martin Rousseau, Isabeau Prémont-Schwarz, and Andre A. Cire.  Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization.  _AAAI 2021_ , 5A:3677–3687, 2021.  URL https://github.com/qcappart/hybrid-cp-rl-solver.
  * Chen et al. (2021) Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Michael Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch.  Decision Transformer: Reinforcement Learning via Sequence Modeling.  _Advances in Neural Information Processing Systems_ , 18:15084–15097, 6 2021.  ISSN 10495258.  doi: 10.48550/arxiv.2106.01345.  URL https://arxiv.org/abs/2106.01345v2.
  * Chen & Tian (2019) Xinyun Chen and Yuandong Tian.  Learning to perform local rewriting for combinatorial optimization.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.  URL https://github.com/facebookresearch/neural-rewriter.
  * Contributors (2021) DI-engine Contributors.  {DI-engine: OpenDILab} Decision Intelligence Engine.  \url{https://github.com/opendilab/DI-engine}, 2021\.
  * Dai et al. (2017) Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial optimization algorithms over graphs.  In _Advances in Neural Information Processing Systems_ , volume 2017-Decem, pp. 6349–6359, 2017.
  * Fu et al. (2020) Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha.  Generalize a Small Pre-trained Model to Arbitrarily Large {TSP} Instances.  _CoRR_ , abs/2012.1, 2020.  URL https://arxiv.org/abs/2012.10658.
  * Hottung et al. (2022) André Hottung, Yeong-Dae Kwon, and Kevin Tierney.  Efficient Active Search for Combinatorial Optimization Problems.  _ICLR 2022_ , 2022.  URL http://arxiv.org/abs/2106.05126.
  * Huang et al. (2022a) Shengyi Huang, Rousslan Fernand Julien Dossa, Antonin Raffin, Anssi Kanervisto, and Weixun Wang.  The 37 Implementation Details of Proximal Policy Optimization.  In _ICLR Blog Track_ , 2022a.  URL https://iclr-blog-track.github.io/2022/03/25/ppo-implementation-details/.
  * Huang et al. (2022b) Shengyi Huang, Rousslan Fernand, Julien Dossa, Chang Ye, Jeff Braga, Dipam Chakraborty, Kinal Mehta, and João G M Araújo.  CleanRL: High-quality Single-file Implementations of Deep Reinforcement Learning Algorithms.  _Journal of Machine Learning Research_ , 23:1–18, 2022b.  URL http://jmlr.org/papers/v23/21-1342.html.
  * Hubbs et al. (2020) Christian D Hubbs, Hector D Perez, Owais Sarwar, Nikolaos V Sahinidis, Ignacio E Grossmann, and John M Wassick.  OR-Gym: A Reinforcement Learning Library for Operations Research Problems, 2020.
  * Joshi & Anand (2022) Chaitanya K Joshi and Rishabh Anand.  Recent Advances in Deep Learning for Routing Problems.  In _ICLR Blog Track_ , 2022.  URL https://iclr-blog-track.github.io/2022/03/25/deep-learning-for-routing-problems/.
  * Joshi et al. (2019) Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson.  An efficient graph convolutional network technique for the travelling salesman problem.  _arXiv preprint arXiv:1906.01227_ , 2019.
  * Kool et al. (2019) Wouter Kool, Herke Van Hoof, and Max Welling.  Attention, learn to solve routing problems!  _7th International Conference on Learning Representations, ICLR 2019_ , 2019.
  * Kool et al. (2021) Wouter Kool, Herke van Hoof, Joaquim A S Gromicho, and Max Welling.  Deep Policy Dynamic Programming for Vehicle Routing Problems.  _CoRR_ , abs/2102.1, 2021.  URL https://arxiv.org/abs/2102.11756.
  * Kwon et al. (2020) Yeong Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min.  POMO: Policy optimization with multiple optima for reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 2020-Decem, 2020.
  * Li et al. (2018) Zhuwen Li, Qifeng Chen, and Vladlen Koltun.  Combinatorial optimization with graph convolutional networks and guided tree search.  _Advances in Neural Information Processing Systems_ , 2018-Decem(Nips):539–548, 2018.  ISSN 10495258.
  * Liang et al. (2017) Eric Liang, Richard Liaw, Philipp Moritz, Robert Nishihara, Roy Fox, Ken Goldberg, Joseph E. Gonzalez, Michael I. Jordan, and Ion Stoica.  RLlib: Abstractions for Distributed Reinforcement Learning.  _35th International Conference on Machine Learning, ICML 2018_ , 7:4768–4780, 12 2017.  doi: 10.48550/arxiv.1712.09381.  URL https://arxiv.org/abs/1712.09381v4.
  * Lu et al. (2020) Hao Lu, Xingwen Zhang, and Shuang Yang.  A Learning-Based Iterative Method for Solving Vehicle Routing Problems.  In _ICLR 2022_ , volume 3, pp. 1–15, 2020.  URL https://openreview.net/forum?id=BJe1334YDH.
  * Ma et al. (2021) Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang.  Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer.  _NeurIPS 2021_ , 34:11096–11107, 12 2021.
  * Manchanda et al. (2020) Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh.  GCOMB: Learning budget-constrained combinatorial algorithms over billion-sized graphs.  _Advances in Neural Information Processing Systems_ , 2020-Decem, 2020\.  ISSN 10495258.
  * Nazari et al. (2018) Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V Snyder.  Reinforcement learning for solving the vehicle routing problem.  In _Advances in Neural Information Processing Systems_ , volume 2018-Decem, pp. 9839–9849, 2018.
  * Ouyang et al. (2021) Wenbin Ouyang, Yisen Wang, Paul Weng, and Shaochen Han.  Generalization in Deep {RL} for {TSP} Problems via Equivariance and Local Search.  _CoRR_ , abs/2110.0, 2021.  URL https://arxiv.org/abs/2110.03595.
  * Raffin et al. (2021) Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann.  Stable-Baselines3: Reliable Reinforcement Learning Implementations.  _Journal of Machine Learning Research_ , 22(268):1–8, 2021.  URL http://jmlr.org/papers/v22/20-1364.html.
  * Vinyals et al. (2015) Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  In _Advances in Neural Information Processing Systems_ , volume 2015-Janua, pp. 2692–2700, 2015.
  * Weng et al. (2022) Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Duburcq, Minghao Zhang, Yi Su, Hang Su, and Jun Zhu.  Tianshou: A Highly Modularized Deep Reinforcement Learning Library.  _Journal of Machine Learning Research_ , 23(267):1–6, 2022.  URL http://jmlr.org/papers/v23/21-1127.html.
  * Williams (1992) Ronald J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning 1992 8:3_ , 8(3):229–256, 5 1992.  ISSN 1573-0565.  doi: 10.1007/BF00992696.  URL https://link.springer.com/article/10.1007/BF00992696.
  * Wu et al. (2019) Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim.  Learning Improvement Heuristics for Solving the Travelling Salesman Problem.  _CoRR_ , abs/1912.0, 2019.  URL http://arxiv.org/abs/1912.05784.

##  Appendix A Algorithmic structures

In this section, we will look at the algorithm structures of three works:
PN+RL (Bello et al., 2019), Attention Model (Kool et al., 2019), and POMO
(Kwon et al., 2020). Without specification, the train function describes the
algorithm in a single epoch.

###  A.1 Basic algorithm

⬇

# REINFORCE Algorithm (basic)

def train(policy network @$p_\theta$@, training set @$S$@, batch size @$B$@):

for @$i$@ in @$1…B$@:

@$s_i$@ = RandomInstance(@$S$@)

@$\pi_i$@ = SampleRollout(@$s_i,p_\theta$@)

@$\vb$@ = UpdateBaseline(@$\vs,\bm{\pi}$@)

@$\nabla\mathcal{L}$@ = @$\frac{1}{B}\sum_{i=1}^B
(L(\pi_i|s_i)-b_i)\nabla_\theta\log(p_\theta(\pi_i|s_i))$@

@$\theta$@ = GradientDescent(@$\theta,\nabla\mathcal{L}$@)

Note that, the same REINFORCE algorithm can be used to fine-tune on a testing
sample. It is denoted as Active Search in PN+RL from Bello et al. (2019).

⬇

# Fine tuning with Active Search

def finetune(policy network @$p_\theta$@, testing sample @$s$@, batch size
@$B$@):

for @$i$@ in @$1…B$@:

@$\pi_i$@ = SampleRollout(@$s,p_\theta$@) # roll for a single instance

@$\vb$@ = UpdateBaseline(@$s,\bm{\pi}$@)

@$\nabla\mathcal{L}$@ = @$\frac{1}{B}\sum_{i=1}^B
(L(\pi_i|s)-b_i)\nabla_\theta\log(p_\theta(\pi_i|s))$@

@$\theta$@ = GradientDescent(@$\theta,\nabla\mathcal{L}$@)

###  A.2 Modifications

We describe the changes different works have made.

⬇

# Attention model : new baseline

def train(policy network @$p_\theta$@, training set @$S$@, batch size @$B$@,

+ significance @$\alpha$@):

for @$i$@ in @$1…B$@:

@$s_i$@ = RandomInstance(@$S$@)

@$\pi_i$@ = SampleRollout(@$s_i,p_\theta$@)

@\Colorbox{diffminus}{- $\vb$ = UpdateBaseline($\vs,\bm{\pi}$)}@

+ @$\vb$@ = UpdateBaseline(@$\vs,\bm{\pi},p_{\theta^\mathrm{BL}}$@)

@$\nabla\mathcal{L}$@ = @$\frac{1}{B}\sum_{i=1}^B
(L(\pi_i|s_i)-b_i)\nabla_\theta\log(p_\theta(\pi_i|s_i))$@

@$\theta$@ = GradientDescent(@$\theta,\nabla\mathcal{L}$@)

+ if OneSidedPairedTest(@$p_\theta,p_{\theta^\mathrm{BL}}$@) < @$\alpha$@: # $p_\theta$ is better than $p_{\theta^\mathrm{BL}}$

+ @$\theta^\mathrm{BL}$@ = @$\theta$@

⬇

# POMO : new policy sampler

def train(policy network @$p_\theta$@, training set @$S$@, batch size @$B$@,

+ number of start nodes @$N$@):

for @$i$@ in @$1…B$@:

@$s_i$@ = RandomInstance(@$S$@)

@\Colorbox{diffminus}{- $\pi_i$ = SampleRollout($s_i,p_\theta$)}@

+ @$\alpha_{i}^1,…,\alpha_{i}^N$@ = SelectStartNodes(@$s_i$@)

+ @$\pi_{i}^1,…,\pi_{i}^N$@ = SampleRollout(@$s_i,p_\theta,\\{\alpha_{i,j}\\}$@)

@$\vb$@ = UpdateBaseline(@$\vs,\bm{\pi}$@)

@\Colorbox{diffminus}{- $\nabla\mathcal{L}$ = $\frac{1}{B}\sum_{i=1}^B
(L(\pi_i|s_i)-b_i)\nabla_\theta\log(p_\theta(\pi_i|s_i))$}@

+ @$\nabla\mathcal{L}$@ = @$\frac{1}{NB}\sum_{i=1}^B\sum_{j=1}^N (L(\pi_i^j|s_i)-b_i)\nabla_\theta\log(p_\theta(\pi_i^j|s_i))$@

@$\theta$@ = GradientDescent(@$\theta,\nabla\mathcal{L}$@)

###  A.3 Baselines

For different works, they use different baselines.

⬇

# PN+RL

def UpdateBaseline(@$\vs,\bm{\pi}$@):

for @$i$@ in @$1…B$@:

@$b_i$@ = criticNetwork(@$s_i$@)

return @$b$@

\par# Attention model

def UpdateBaseline(@$\vs,\bm{\pi},p_{\theta^\mathrm{BL}}$@):

for @$i$@ in @$1…B$@:

@$\pi_i^{\mathrm{BL}}$@ = GreedyRollout(@$s_i,p_{\theta^\mathrm{BL}}$@) #
$p_{\theta^\mathrm{BL}}$ is the best model so far

@$b_i$@ = @$L(\pi_i^{\mathrm{BL}}|s_i)$@

return @$b$@

\par# POMO

def UpdateBaseline(@$\vs,\bm{\pi}$@):

for @$i$@ in @$1…B$@:

@$b_i$@ = @$\frac{1}{N}\sum_{j=1}^N(L(\pi_i^j|s_i))$@ # $N$ rollouts for each
$\pi_i$

return @$b$@

###  A.4 Decoding strategies

In this subsection, we denote $\pi_{t}$ to be the action chosen at step $t$.

⬇

# Greedy strategy

def GreedyRollout(instance @$s$@, policy network @$p_\theta$@):

@$\pi$@ = []

while not Done(@$s,\pi$@):

@$\pi_{next}$@ = @$\mathrm{argmax}_i\,{ p_\theta(i|s,\pi)}$@

@$\pi$@.append(@$\pi_{next}$@)

return @$\pi$@

\pardef inference(instance @$s$@, policy network @$p_\theta$@):

@$\pi$@ = GreedyRollout(@$s$@,@$p_\theta$@)

return @$\pi$@

⬇

# Sampling strategy

def SampleRollout(instance @$s$@, policy network @$p_\theta$@):

@$\pi$@ = []

while not Done(@$s,\pi$@):

@$\pi_{next}$@ = Sample(@${ p_\theta( . |s,\pi)}$@)

@$\pi$@.append(@$\pi_{next}$@)

return @$\pi$@

\pardef inference(instance @$s$@, policy network @$p_\theta$@, sampling size
@$N$@):

for @$i$@ in @$1…N$@:

@$\pi_i$@ = SampleRollout(@$s$@,@$p_\theta$@)

@$\pi_{bext}$@ = @$\mathrm{argmin}_{\pi_i}\,{ L(\pi_i|s)}$@

return @$\pi_{best}$@

⬇

# Beam Search

def inference(instance @$s$@, policy network @$p_\theta$@, beam size @$w$@):

beam = [([],0)] # [seq, score = $\sum_{\pi_t}
\logp_\theta(\pi_t|s,\pi_{1:t-1})$]

finalBeam = []

while beam is not empty:

expansion = []

for (@$\pi$@, score) in beam:

if Done(@$s$@,@$\pi$@):

finalBeam.append(@$\pi$@)

continue

for j in @$p_\theta(.|s,\pi)_{>0}$@: # only feasible actions

expansion.append((@$\pi$@+[j], score + @$\logp_\theta(\pi_t=j|s,\pi)$@))

beam = TopK(expansion)

@$\pi_{bext}$@ = @$\mathrm{argmin}_{\pi\in\texttt{finalBeam}}\,{ L(\pi|s)}$@

return @$\pi_{bext}$@

As mentioned in Section A.1, the model can be fine-tuned during inference with
Active Search.

⬇

# Active Search

def finetune(policy network @$p_\theta$@, testing sample @$s$@, batch size
@$B$@):

for @$i$@ in @$1…B$@:

@$\pi_i$@ = SampleRollout(@$s,p_\theta$@)

@$\vb$@ = UpdateBaseline(@$s,\bm{\pi}$@)

@$\nabla\mathcal{L}$@ = @$\frac{1}{B}\sum_{i=1}^B
(L(\pi_i|s)-b_i)\nabla_\theta\log(p_\theta(\pi_i|s))$@

@$\theta$@ = GradientDescent(@$\theta,\nabla\mathcal{L}$@)

\pardef inference(policy network @$p_\theta$@, testing sample @$s$@, batch
size @$B$@,

epochs @$T$@):

for @$t$@ in @$1…T$@:

finetune(@$p_\theta$@,@$s$@,@$B$@)

@$\pi_{bext}$@ = best policy encounted during fine-tuning

return @$\pi_{bext}$@

\par

We can integrate the end2end learning model with classical exact algorithms
and use our policy network output as a heuristic. This converts the end2end
learning model to an exact model (we can run exhaustive search under the
classical exact algorithm framework).

⬇

def DepthFirstBranchAndBound(instance @$s$@, policy network @$p_\theta$@ ):

bound = @$\infty$@

solution = None

def dfs(@$\pi$@):

# bound stage: prune

# Prune if the partial solution is worse than the incumbent

if @$L(\pi|s)$@ >= bound:

return

# bound stage: update bound

# Update the bound if a better solution is found

if Done(@$s,\pi$@) and @$L(\pi|s)$@ < bound:

bound = @$L(\pi|s)$@

solution = @$\pi$@

return

\par# branch stage: RL prediction as the heuristic

values = @$\mathrm{argsort}_j p_\theta(\pi_t=j|s,\pi)$@

for action in values:

@$\pi_{new}$@ = copy(@$\pi$@).append(action)

dfs(@$\pi_{new}$@)

@$\pi_{0}$@ = []

dfs(@$\pi_{0}$@)

return solution

##  Appendix B Models

In this section, we will look at the neural network architecture of two works:
Pointer Network (Vinyals et al., 2015), and Attention Model (Kool et al.,
2019).

###  B.1 Pointer Network

⬇

Embedding(@$s$@)

-> @$\vx=W_0s$@

\parEncoder(@$\vx$@) # 1 layer lstm

-> @$\vo,(h,c)$@ = LSTM(@$\vx$@) # output, (hidden state, cell state)

\parAttention(@$q,\vk$@)

-> (@$W_1k_j$@, @$u_j=v^T \mathrm{tanh}(W_1k_j+W_2q)$@) @$\text{for each key }k_j$@

\parAttention@$_{clip}$@(@$q,\vk$@) # clip the range of logits to [-C,C]

-> (@$W_1k_j$@, @$C\mathrm{tanh}(u_j)$@ )

\parDecoder(@$\vx,(h_0 ,c_0), \vo$@):

for @$t$@ in 1…T:

# Predict Step

@$h_t, c_t=\mathrm{LSTMCell}(\vx_{\pi_{t-1}},(h_{t-1},c_{t-1}))$@

@$\ve_t, \vu_t=\mathrm{Attention}(h_t, \vo)$@

@$\va_t = \mathrm{Softmax}(\mathrm{Masked}_t(\vu_t))$@

@$h_t^{\prime}=\sum_i a_{t,i}e_{t,i}$@ # glimpse

@$\ve_t^{\prime}, \vu_t^{\prime}=\mathrm{Attention_{clip}}(h_t^{\prime},
\vo)$@

@$\vp_t = \mathrm{Softmax}(\mathrm{Masked}_t(\vu_t^{\prime}))$@

# Decode Step

@$\pi_{t} = \mathrm{DecodingStartegy}(\vp_t)$@

# Update Step

@$\mathrm{Masked}_{t+1} = \mathrm{Masked}_t.update(\pi_t)$@

return @$\\{\log(\vp_t)\\},\pi$@

\parPointerNetwork(@$s$@):

@$\vx$@ = Embedding(@$s$@)

@$\vo,(h,c)$@ = Encoder(@$\vx$@)

@$\\{\log(\vp_t)\\},\pi$@ = Decoder(@$\vx,(h_{-1} ,c_{-1}), \vo$@)

@$\log(p_\theta(\pi|s))$@ = @$\sum_t\log(\vp_{t,\pi_t})$@

return @$\log(p_\theta(\pi|s)),\pi$@

###  B.2 Attention Model

⬇

#####################################

### Helper classes for attention ###

#####################################

\parAttentionScore(@$q,\vk, \mathrm{mask}$@)

-> @$u_j=\begin{cases}\frac{q^Tk_j}{\sqrt{\smash{d_q}}}\text{ for node }j \notin\mathrm{mask}\\\\-\infty\text{ otherwise. }\end{cases} $@

\parAttentionScore@$_{clip}$@(@$q,\vk, \mathrm{mask}$@) # clip the range of
logits to [-C,C]

-> @$u_j=\begin{cases}C\mathrm{tanh}(\frac{q^Tk_j}{\sqrt{\smash{d_q}}})\text{ for node }j \notin\mathrm{mask}\\\\-\infty\text{ otherwise. }\end{cases} $@

\parMultiHeadAttention(@$q,\vk,\vv, \mathrm{mask}$@):

@$\pmb{a}^{(j)} =
\mathrm{Softmax}(\mathrm{AttentionScore}(q^{(j)},\pmb{k}^{(j)},
\mathrm{mask})) \text{ for each head }j$@

@$h^{(j)} = \sum\nolimits_i \pmb{a}^{(j)}_i\pmb{v}_i$@ #reweigh value with
attention weight in each head

@$q^\prime= W^O \left[h^{(1)},…,h^{(J)}\right]$@ # flatten to single head

return @$q^\prime$@

\parMultiHeadAttentionProj(@$q_0,\vh, \mathrm{mask}$@): # with projection

@$q, \pmb{k}, \pmb{v} = W^Qq_0, W^K\vh, W^V\vh$@

@$q^\prime= \mathrm{MultiHeadAttention}(q,\vk,\vv, \mathrm{mask})$@

return @$q^\prime$@

⬇

#####################################

### Main code for attention model ###

#####################################

\parEmbedding(@$s$@)

-> @$\vx=\left[W_0[s_{loc},s_{fea}], W_{depot}s_{depot}\right]$@

\parMHALayer(@$\pmb{x}$@): # self attention, then MLP

@$\pmb{x}_0=\pmb{x}+\mathrm{MultiHeadAttentionProj}(\pmb{x})$@

@$\pmb{x}_1=\mathrm{BatchNorm}(\pmb{x}_0)$@

@$\pmb{x}_2=\pmb{x}_1+\mathrm{MLP_{\text{2 layers}}}(\pmb{x}_1)$@

@$\pmb{h} =\mathrm{BatchNorm}(\pmb{x}_2)$@

return @$\pmb{h}$@

\parEncoder(@$\vx$@) # 2 MHA layers

@$\pmb{h} = \pmb{x}$@

for i in n_layers:

@$\pmb{h} = \mathrm{MHALayer_i}(\pmb{h})$@

return @$\pmb{h}$@

\parContext(@$s,\vh$@):

-> @$(\vh_{\pi_{t-1}}, \vh_{s}) = \text{(previous node, global state (e.g. remaining capacity) }$@

\parDecoder(@$\vx,\vh$@):

for @$t$@ in 1…T:

# Predict Step

@$\bar{\pmb{h}} = \frac{1}{N}\sum\nolimits_i \pmb{h}_i$@ # graph embedding

@$\pmb{h}_{(c)} = [\bar{\pmb{h}}, \text{Context}(s, \pmb{h})]$@

@$q_{gl} = \mathrm{MultiHeadAttention}(W^Q \pmb{h}_{(c)},W^K \pmb{h},W^V
\pmb{h},\mathrm{mask}_t)$@

@$\pmb{p}_t =
\mathrm{Softmax}(\mathrm{AttentionScore}_{\text{clip}}(q_{gl},W^{K^\prime}
\pmb{h}, \mathrm{mask}_t))$@

# Decode Step

@$\pi_{t} = \mathrm{DecodingStartegy}(\vp_t)$@

# Update Step

@$\mathrm{mask}_{t+1} = \mathrm{mask}_t.update(\pi_t)$@

return @$\\{\log(\vp_t)\\},\pi$@

\parAttentionModel(@$s$@):

@$\vx$@ = Embedding(@$s$@)

@$\vh$@ = Encoder(@$\vx$@)

@$\\{\log(\vp_t)\\},\pi$@ = Decoder(@$s,\vh$@)

@$\log(p_\theta(\pi|s))$@ = @$\sum_t\log(\vp_{t,\pi_t})$@

return @$\log(p_\theta(\pi|s)),\pi$@

Note that there are some tricks to speed up the training and inference for the
decoder, such as precomputing and caching the projection of the graph
embedding $\bar{\boldsymbol{h}}$, as well as the keys and values
$W^{K}\boldsymbol{h},W^{V}\boldsymbol{h},W^{K^{\prime}}\boldsymbol{h}$. For
dynamic node features, their projections are recomputed in every decoding
steps with $\mathrm{DynamicEmbedding}$. The projections are added to the keys
and values to form the new keys and values in the decoder.

##  Appendix C More on Vectorized Environment

A vectorized environment runs multiple environments, either sequentially/ in
parallel/ in other way. It receives a batch of actions, runs environment
steps, and returns a batch of observations at that step. The way a RL library
manipulates multiple environments (including creation, step, reset) is denoted
as the vector API. Among the RL platforms, CleanRL has the most efficient
vector API — the one from OpenAI Gym, instead of writing its own. RLlib is
also planning to depreciate its own vector API and migrate it to Gym’s vector
API as indicated in the github repo. The Gym’s vector API is a gym
environment. It can be treated as a wrapper to interact with multiple
environments. Take `gym.vector.SyncVectorEnv} as an example. When it is
instantiated, it sequentially instantiates each of the sub-environments. In
each \mintinline`pythonstep, it sequentially feeds the actions to the sub-
environments, receives the results from them and stores the `reward},
\mintinline`pythondone directly to the pre-allocated numpy arrays while the
`observations} are concatenated according to their type (dict, list, tuple,
float, int, ... ). To handle the concatenation/ array pre-allocation of
different types, Gym’s vector API makes heavy use of single-dispatch function
instead of nested \mintinline`pythonisinstance as in DI-engine. The single-
dispatch function approach is cleaner and is easier to extend. We compared
`SyncVectorEnv} (run sequentially) and \mintinline`pythonAsyncVectorEnv (run
in parallel) on our routing problem environments. We found that the sequential
one is faster. It may be attributed to the communication overhead across the
pipes for the parallel settings.

#### Explicitly vectorized environment.

Instead of using Gym’s vector API, we can implement the vectorized environment
explicitly. For example, the environments in the Attention Model paper (Kool
et al., 2019) are written with PyTorch tensors and PyTorch’s vectorized
operations. The Gym environment for a routing problem written with numpy can
also be re-implemented with numpy’s vectorized operations. The explicit
implementation of vectorized environment provides the same interface as the
vector API, yet allows more room of optimization in computation efficiency.

###  C.1 Chunking Vectorized Environment

Thanks to the flexibility of the Gym’s vector API, it is possible to implement
chunking: vectorization of multiple vectorized envinronment. There are a
couple of advantages of chunking: efficiency and flexibility. The explicitly
vectorized environments are faster than running individual environments
sequentially/ in parallel with the vector API. However, it requires careful
design for fine-grained control in these explicitly vectorized environments.
With chunking, we do not need to dive into the implementation of explicitly
vectorized environments. Instead, we can apply different wrappers to these
vectorized environments. An example usage of chunking is that, we want to
create $M$ TSP problems and explore $N$ trajectories in each of the TSP
problems. First, we can create a vectorized environment (denote as
$\mathrm{TrajEnv}_{i}$) of $N$ sub-environments. We can apply a wrapper to
ensure the same nodes coordinates in these sub-environments. Then, we create a
higher level of vectorized environment (denote as $\mathrm{ProblemEnv}$) of
these $M$ sub-environments $\\{\mathrm{TrajEnv}_{i},i=1...M\\}$. The bi-level
vectorized environment can now well describe the setting we required. With
Gym’s vector API, the `observations} from the bi-level vectorized environment
has its dimensions extended accordingly. It provides clearer semantics for
performing operations on observations from different level of vectorized
environments. For example, the static features from the same
$\mathrm`TrajEnv_i$needonlytobecomputedonceandcanbesharedamongdifferenttrajectoriesinthesub-
environments.Itisstraight-
forwardtodosowithGym^{\prime}svectorAPI,otherwiseitwouldrequirecarefulreshapingandindexing.\par\@add@PDF@RDFa@triples\par\end{document}$