# Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions

Cong Dao Tran & Thong Bach
FPT Software AI Center, Hanoi, Vietnam &Truong Son Hy 11footnotemark: 1
Indiana State University, Terre Haute, USA Equal contributionCorrespondence to
<EMAIL_ADDRESS>
###### Abstract

Travelling Salesperson Problems (TSPs) and Vehicle Routing Problems (VRPs)
have achieved reasonable improvement in accuracy and computation time with the
adaptation of Machine Learning (ML) methods. However, none of the previous
works completely respects the symmetries arising from TSPs and VRPs including
rotation, translation, permutation, and scaling. In this work, we introduce
the first-ever completely equivariant model and training to solve
combinatorial problems. Furthermore, it is essential to capture the multiscale
structure (i.e. from local to global information) of the input graph,
especially for the cases of large and long-range graphs, while previous
methods are limited to extracting only local information that can lead to a
local or sub-optimal solution. To tackle the above limitation, we propose a
multiresolution scheme in combination with Equivariant Graph Attention network
(mEGAT) architecture, which can learn the optimal route based on low-level and
high-level graph resolutions in an efficient way. In particular, our approach
constructs a hierarchy of coarse-graining graphs from the input graph, in
which we try to solve the routing problems on simple low-level graphs first,
then utilize that knowledge for the more complex high-level graphs.
Experimentally, we have shown that our model outperforms existing baselines
and proved that symmetry preservation and multiresolution are important
recipes for solving combinatorial problems in a data-driven manner. Our source
code is publicly available at https://github.com/HySonLab/Multires-NP-hard.

##  1 Introduction

Routing problems, such as TSPs and VRPs, are a class of NP-hard combinatorial
optimization (CO) problems with numerous practical and industrial applications
in logistics, transportation, and supply chain (Feillet et al., 2005; Laporte,
2009). Consequently, they have attracted intensive research efforts in
computer science and operations research (OR), with many exact and heuristic
approaches proposed (Croes, 1958; Applegate et al., 2009; Helsgaun, 2017;
Gurobi Optimization, 2021). Exact methods often suffer from the drawback of
high time complexity, making them impractical for real-world applications
where instances have large sizes. Heuristic methods are more commonly used in
practical applications, providing near-optimal solutions with much lower
computational time and complexity. However, these algorithms lack guarantees
of optimality and non-trivial theoretical analysis and heavily rely on
handcrafted rules and domain knowledge, leading to difficulty in
generalization to other combinatorial optimization problems. Therefore, it is
important to build efficient data-driven methods that can learn to solve these
challenging problems.

In recent times, machine learning methods (especially deep and reinforcement
learning) inspired by Pointer Network (Vinyals et al., 2015), Graph Neural
Network (Wu et al., 2020), and Transformer (Vaswani et al., 2017) have been
used to automatically learn complex patterns, heuristics, or policies from
generated instances for both TSPs and VRPs. These approaches are collectively
referred to as learning-based (or data-driven) methods and are promising
alternatives that can reduce computation time while maintaining solution
quality compared to traditional non-learning-based methods. However, these
machine learning models still face two major challenges: Firstly, since
routing problems, e.g., TSP and VRP, are often represented in the 2D Euclidean
space, their solutions must be invariant to geometric transformations of the
input city coordinates, such as rotation, permutation, translation, and
scaling (see Figure 1). Nevertheless, most existing sequence-to-sequence
machine learning-based methods, e.g., Attention Model (Kool et al., 2019),
have not yet fully considered the underlying symmetries of routing problems.
Secondly, current learning-based methods often focus on learning from local
information (spatial locality) to improve solution quality, which may lead to
the model converging to local optima and missing leveraging global
information.

In this paper, we aim to incorporate a geometric deep learning architecture
into our model to enforce invariance (i.e. symmetry preservation) with respect
to rotations, reflections, and translations of the input city coordinates.
More specifically, we present an Equivariant Attention Model with
Multiresolution architecture training for guiding the model to learn at
multiple resolutions and multiple scales while remaining invariant to
geometric transformations. To learn information from multiple resolutions and
scales, we divide a problem instance into smaller sub-instances, each with its
own feature, such as proximity space. We then build higher-level instances
based on these sub-instances at a lower level and synthesize their
information. These multiresolution instances are fed into the model to train
together with the original instance using shared network weights to help the
model generalize better and converge faster.

Figure 1: Invariant TSP with node coordinate transformations: rotation,
translation, and scaling. Note that when we apply any of these geometric
transformations to the original graph (in the first row), the optimal solution
(OTP) of the instance remains unchanged (in the second row). This is one of
the necessary invariant properties that deep models need to respect for
routing problems.

Accordingly, our main contributions are summarized as follows:

  * •

We first identify the equivariance and symmetries in deep (reinforce) models
for solving routing problems and suggest incorporating an Equivariant Graph
Attention model to respect invariant transformations on the input graphs. Such
equivariant models are more stable than existing non-equivariant models when
dealing with CO problems with invariant transformations, e.g., TSPs and VRPs.

  * •

We propose Multiresolution graph training for learning routing problems at
multiple levels, i.e. sub-graphs and high-level graphs. Our model is derived
from Attention Model with Equivariant components and trained with sharing
weights of different scales of an original problem instance to quickly capture
both local and implicitly global structures of problems.

  * •

We validate the efficiency and efficacy of our model on synthetic and real-
world large-scale datasets of TSP with various distributions, sizes, and
symmetries. We also devise our model for another routing problem, e.g.,
Capacitated Vehicle Routing Problem (CVRP). The obtained results show our
model could have better generalization and stability compared to previous
data-driven methods based on Attention Model in terms of solution quality.

##  2 Related work

#### Classical methods.

Classical methods for TSPs and VRPs have been extensively studied in the
literature, typically including exact and approximate (approximation,
heuristic) approaches (Laporte, 1992a; b). For TSPs, exact algorithms such as
branch and bound (Clausen, 1999) and dynamic programming (Bellman, 1962) and
heuristic methods such as the nearest neighbor (Held & Karp, 1962), 2-opt
(Croes, 1958), and LKH (Lin & Kernighan, 1973) are well-known. Similarly, for
VRPs, classical methods include exact algorithms such as branch and cut
(Lysgaard et al., 2004), and heuristics such as Tabu search (Glover & Laguna,
1998), Genetic Algorithms (Holland, 1992), and LKH-3 (Helsgaun, 2017).
Although these methods have successfully solved small to medium-sized
instances of TSP and VRP, they often struggle to scale up to large-scale
problems due to their exponential growth in time complexity.

#### Neural methods.

In CO, deep learning methods have been applied and obtained promising results
and better scalability. The popular deep architectures are comprised of two
components, i.e. encoder and decoder (Sutskever et al., 2014; Kool et al.,
2019; Joshi et al., 2019). Recent researches tend to focus more on building
efficient decoders and loss functions. Kool et al. (2019) generates solutions
in an autoregressive manner, whereas Joshi et al. (2019) generates solutions
directly. Besides, constructing labels for large-scale problems is often
costly or infeasible; hence using reinforcement learning to train models is
more appropriate and attractive (Peng et al., 2020; Kwon et al., 2020). Cheng
et al. (2023); Li et al. (2021); Xin et al. (2021) try to improve the results
by finding and re-optimizing sub-paths, then merging them into the original
solution via a heuristic way. Some efforts have been made to address the issue
of symmetries for TSPs, such as POMO (Kwon et al., 2020) and Sym-NCO Kim et
al. (2022). However, these methods are not fully optimized and cannot respect
geometric transformations. Different from previous studies, our work focuses
on building an equivariant deep model that can systematically extract problem
information in the encoder at multiple levels, which can jointly help the
decoder generate a better solution and preserve invariance to geometric
transformations.

#### Symmetry preserving methods.

Starting with (Cohen & Welling, 2016), group equivariance and symmetry
preserving have emerged as core organizing principle of deep neural network
architectures. From classical Convolutional Neural Networks (CNNs) (LeCun et
al., 1989; Krizhevsky et al., 2012) that are equivariant to translations,
researchers have also constructed neural networks that are equivariant to the
Euclidean group of translations and rotations (Cohen & Welling, 2017; Weiler
et al., 2018), the three dimensional rotation group (Cohen et al., 2018;
Anderson et al., 2019), the permutation group in the context of learning on
sets (Zaheer et al., 2017) and learning on graphs (Maron et al., 2019; Kondor
et al., 2018; Hy et al., 2018; 2019), and other symmetry groups (Ravanbakhsh
et al., 2017). Based on the existing development of equivariant neural
networks, we propose a general learning architecture for solving combinatorial
problems (e.g., TSPs and VRPs) that respects all underlying symmetries
including rotation, permutation, translation, and scaling.

#### Multiresolution learning on graphs.

Graph neural networks (GNNs) that generalize the concept of convolution to
graphs (Scarselli et al., 2009; Niepert et al., 2016) have been widely applied
to several applications including modeling physical systems (Battaglia et al.,
2016), predicting molecular properties (Kearnes et al., 2016; Gilmer et al.,
2017; Hy et al., 2018), learning to solve NP-complete (Prates et al., 2019)
and NP-hard problems (Dai et al., 2017), etc. Most GNNs are constructed based
on the message passing scheme (Gilmer et al., 2017) in which each node
propagates and aggregates to and from its local neighborhood. Because of the
restriction to locality, the message passing scheme lacks the ability to
capture the multiscale and hierarchical structures that are present in complex
and long-range graphs (Dwivedi et al., 2022). (Hy & Kondor, 2023; Ngo et al.,
2023) proposed a learning to cluster algorithm in a data-driven manner that
iteratively partitions a graph and coarsens it in order to build multiple
resolutions of a graph, i.e. multiresolution. In our work, we adopt the
multiresolution framework to capture both local and global information of the
input structure that are essential in solving combinatorial problems.

##  3 Preliminaries

###  3.1 Routing Problem via Markov Decision Process

We investigate the routing problems in 2D Euclidean space, where a problem
instance $s$ is defined as a graph $G=(V,E)$ with a set of $n$ nodes
$V=\\{v_{1},v_{2},...,v_{n}\\}$. Each node $v_{i}$ is represented by a 2D
coordinate. The edges set $E$ represent connections between these nodes, and
the edges are weighted by the Euclidean distance. In many cases, a solution to
the problems can be represented as a sequence of nodes. The optimization
objective of these problems is commonly to minimize the total traveling
distance (length).

For a simple illustration, we take a TSP as a representative example, although
our proposed approach can be applied to other routing problems, such as VRPs.
A feasible solution for a TSP with $n$ cities, typically denoted
$\text{TSP}n$, is defined as a tour $\bm{\pi}=(\pi_{1},...,\pi_{n})$ as a
permutation of the $n$ nodes that each node is visited once and only once. The
length of a tour is defined as:
$\mathbb{L}(\bm{\pi})=||c_{\pi_{n}}-c_{\pi_{1}}||+\sum_{i=1}^{n-1}||c_{\pi_{i}}-c_{\pi_{i+1}}||_{2},$
where $c_{i}$ is the coordinate of node $v_{i}$ and $||.||_{2}$ denotes the
$l_{2}$ norm.

###  3.2 Symmetries, groups and equivariance

In group theory, the collection of symmetries form an algebraic object known
as a group. Formally, a group is defined by 4 axioms (i.e. closure,
associativity, identity and inverse) as in Def. A.1. In this work, we are
particularly interested in the symmetry of permutation, rotation, translation,
and scale. Our purpose is to design an equivariant model with respect to all
these groups:

  * •

A permutation of order $n$ is a bijective map
$\sigma:\\{1,2,\cdots,n\\}\rightarrow\\{1,2,\cdots,n\\}$. The permutation
group or symmetric group of degree n, denoted as $\mathbb{S}_{n}$, is the set
of all $n!$ permutations of order $n$. Any graph neural network must be
permutation-invariant or $\mathbb{S}_{n}$-invariant, i.e. regardless of how we
permute the set of vertices, the output of GNN must remain the same because
permutation does not change the graph topology. In TSP of $n$ cities, a
permutation will reindex/rename the cities but never change the length of the
optimal tour. We say that the (unique) optimal tour is
$\mathbb{S}_{n}$-equivariant and its length is $\mathbb{S}_{n}$-invariant.

  * •

The 2D or 3D rotation group or special orthogonal group, denoted as
$\text{SO}(2)$ or $\text{SO}(3)$ respectively, is the group of all rotations
about the origin of the Euclidean space under the operation of composition.

  * •

The set of all translations $T_{\Delta x,\Delta y}:(x,y)\mapsto(x+\Delta
x,y+\Delta y)$ form the translation group.

In TSPs and VRPs, we assume that locations are mapped into a 2D Euclidean
space; and regardless of how we rotate, translate or scale (i.e. multiplying
all the coordinates with a non-zero constant) them, the optimal solution
remains unchanged (see Fig. 1). Any model trying to solve these combinatorial
problems must be rotation-invariant or $\text{SO}(2)$-invariant, translation-
invariant and scale-invariant. In summary, any solver must be $G$-invariant
where $G$ is a group of any symmetry that arises from the input domain.

##  4 Methodology

Figure 2: Overview of our mEGAT framework. Given an input graph, our
multiresolution graph construction first output all sub-graphs and
multiresolution high-level graphs, e.g., a bi-level graph, based on graph
clustering. Then, we train our model at multi-level graphs by feeding the
original graph, sub-graphs, and high-level graph into our model to jointly
learn and optimize.

Motivation. For complex TSPs or VRPs, an effective approach commonly employed
in prior works is to divide an original problem into simplified sub-problems,
solve them individually, and then combine their solutions to form the final
solution for the original problem. Our work is also motivated by this idea,
but it differs from previous works in that we propose a framework capable of
constructing both sub-problems and higher-level problems (see 4.1).
Furthermore, we utilize these constructed problems in joint training with the
original problem using our Multiresolution graph training (see 4.2).
Additionally, we handle a symmetry-preserving graph attention network that can
learn solutions invariant to geometric transformations (see 4.3). The overall
approach is illustrated in Figure 2.

###  4.1 Learning multiple resolution graphs

#### Sub-graph construction.

As mentioned in 3.1, a routing problem in 2D Euclidean space is typically
defined over an undirected graph $G=(V,E)$ with node set
$V=\\{v_{i}=(x_{v_{i}},y_{v_{i}})|x_{v_{i}},y_{v_{i}}\in\mathbb{R},i\in[\\![1,n]\\!]\\}$
and edge set $E=\\{e=(v_{i},v_{j})|v_{i},v_{j}\in V,i\neq j)\\}$. We give some
definitions as follows.

######  Definition 4.1.

A $K$-subgraph construction of graph $G$ is a partition of the set of nodes
$V$ into $K$ mutually exclusive cluster $V_{1}^{sub},...,V_{K}^{sub}$. Each
cluster corresponds to an induced sub-graph
$G_{k}^{sub}=G[V_{k}^{sub}]=(V_{k}^{sub},E_{k}^{sub})$ in which
$V=V_{1}^{sub}\cup\cdots\cup V_{K}^{sub}$ and $E_{k}^{sub}=\\{e=(u,v)\in
E|u,v\in V_{k}^{sub}\\}$, $k\in[\\![1,K]\\!]$.

######  Definition 4.2.

Given a sub-graph construction, a high-level (i.e. coarsened graph) of a
weighted graph $G=(V,E)$ is a weighted complete graph
$G^{\prime}=(V^{\prime},E^{\prime})$ which includes $K$ nodes corresponding to
the $K$ clusters that are determined from the sub-graph construction. Each
node $v_{k}^{\prime}\in V^{\prime}$ can be determined by a 2D Euclidean
coordinate as:

$x_{v_{k}^{\prime}}=\frac{1}{|V_{k}^{sub}|}\sum_{v\in V_{k}^{sub}}x_{v},\ \ \
\ \ y_{v_{k}^{\prime}}=\frac{1}{|V_{k}^{sub}|}\sum_{v\in V_{k}^{sub}}y_{v}.$
(1)

The weight of each edge $e^{\prime}=(v^{\prime}_{i},v^{\prime}_{j})\in
E^{\prime}$ connecting $V_{i}^{sub}$ and $V_{j}^{sub}$ is determined as:

$w(e^{\prime})=d(v^{\prime}_{i},v^{\prime}_{j})=||v^{\prime}_{i}-v^{\prime}_{j}||_{2},$
(2)

where $d:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$ denotes the
Euclidean distance between two nodes.

######  Definition 4.3.

A $L$-level multiresolution (i.e. multiple of resolutions) of graph $G$ is a
series of $L$ graphs $G_{1},\ldots,G_{L}$ where:

  * •

$G_{L}$ is $G$ itself.

  * •

For $1\leq\ell\leq L-1$, the $\ell$-th level graph $G_{\ell}$ is a high-level
graph of $G_{\ell+1}$, as defined in Def. 4.2, where the number of nodes in
$G_{\ell}$ is the number of clusters in $G_{\ell+1}$.

  * •

The top-level $G_{1}$ is a graph with at least $5$ nodes111In our experiments
for TSP and VRP, the top-level graph has at least 5 nodes..

Input: Input graph $G=(V,E)$.

$\\{V_{k}^{sub}\\}_{k=1}^{K}$ $\leftarrow$ $\text{Clustering}(G)$;

$V^{\prime}\leftarrow\emptyset$ and $E^{\prime}\leftarrow\emptyset$;

for  _$k\leftarrow 1..K$_ do

$E_{k}^{sub}=\\{e=(u,v)|u,v\in V_{k}^{sub}\\}$;

$G_{k}^{sub}\leftarrow(V_{k}^{sub},E_{k}^{sub})$;

$V^{\prime}\leftarrow V^{\prime}\cup\\{v^{\prime}_{k}\\}$ with
$v^{\prime}_{k}=(x_{v^{\prime}_{k}},y_{v^{\prime}_{k}})$ updated by Eq. 1;

$E^{\prime}\leftarrow E^{\prime}\cup\\{e^{\prime}\\}$ with $w(e^{\prime})$
updated by Eq. 2;

Output: Sub-graphs $\\{G_{k}^{sub}=(V_{k}^{sub},E_{k}^{sub})\\}_{k=1}^{K}$ and
high-level graph $G^{\prime}=(V^{\prime},E^{\prime})$.

Algorithm 1 Multiresoltion graphs construction

Algorithm 1 describes a simplified implementation of our multiresolution
graphs construction with 2-level (i.e., $L=2$), given an input graph $G$. We
can repeat the algorithm on the existing-level graph to obtain a higher-level
resolution graph. These corresponding sub-graphs could capture the local
information, while these high-level graphs could capture the global
information in a long range of the original graph. We subsequently utilize the
features from these subgraphs to facilitate solving the original problem. Our
motivation is rooted in the observation that many combinatorial optimization
problems exhibit inherent spatial locality, whereby the entities within the
problem are more strongly influenced by their neighboring entities than those
far away.

###  4.2 Model Training at multiple level graphs

Most previous learn-to-struct methods, such as AM Kool et al. (2019) and POMO
Kwon et al. (2020), use RL to train a sequence-to-sequence policy for solving
routing problems directly. The corresponding stochastic policy $p(\bm{\pi}|s)$
for selecting a solution $\bm{\pi}$ which is factorized and parameterized by
$\bm{\theta}$ as:

$p_{\bm{\theta}}(\bm{\pi}|s)=\prod\limits_{t=1}^{n}p_{\bm{\theta}}(\pi_{t}|s,\bm{\pi}_{1:t-1}).$
(3)

From the probability distribution $p_{\theta}(\bm{\pi}|s)$, the model can
obtain a solution $\bm{\pi}|s$ by sampling. Normally, the expectation of the
tour length (cost) is used as the training loss:
$\operatorname{\mathcal{L}}(\bm{\theta}|s)=\mathbb{E}_{p_{\bm{\theta}}(\bm{\pi}|s)}\left[\mathbb{L}(\bm{\pi})\right]$
on the original instance $s$.

In this paper, we use the constructed sub-problems (section 4.1) in joint
training with the original problem to leverage local and global features to
learn the problem more effectively. Given a problem instance $s$, we obtain a
set of $K$ sub-instances $s_{k}^{sub}$, ($k\in[\\![1,K]\\!]$) and a set of $L$
high-level instances $s_{\ell}^{high}$ ($\ell\in[\\![1,L]\\!]$) after
performing a clustering method on the original instance. Note that in our
work, the terms (sub, high-level) instance and (sub, high-level) graph are
equivalent and can be used interchangeably.

Motivated by the idea of multiple level-graphs training, we define a new loss
function to help our model learn and generalize better in both the original
graph and different multi-scale graphs. Our model learns a policy
$p_{\bm{\theta}}$ by minimizing the total loss function:

$\operatorname{\mathcal{L}}_{\text{total}}=\operatorname{\mathcal{L}}_{\text{original
instance}}+{\color[rgb]{0,0,1}\operatorname{\mathcal{L}}_{\text{sub-
instances}}}+{\color[rgb]{1,.5,0}\operatorname{\mathcal{L}}_{\text{high-level
instances}}},$ (4)

where $\operatorname{\mathcal{L}}_{\text{original instance}}$,
${\color[rgb]{0,0,1}\operatorname{\mathcal{L}}_{\text{sub-instances}}}$, and
${\color[rgb]{1,.5,0}\operatorname{\mathcal{L}}_{\text{high-level
instances}}}$ are REINFORCE loss that needs to be optimized for original, sub,
and high-level instances, respectively. The terms of two additional loss
functions for sub and high-level instances are defined as follows:

$\operatorname{\mathcal{L}}_{\text{sub-
instances}}(\bm{\theta}|s^{sub})=\frac{1}{K}\sum^{K}_{k=1}\mathbb{E}_{p_{\bm{\theta}}(\bm{\pi}^{sub}_{k}|s^{sub}_{k})}\left[\mathbb{L}(\bm{\pi}^{sub}_{k})\right],$
(5) $\operatorname{\mathcal{L}}_{\text{high-level
instances}}(\bm{\theta}|s^{high})=\frac{1}{L-1}\sum^{L-1}_{\ell=1}\mathbb{E}_{p_{\bm{\theta}}(\bm{\pi}_{\ell}^{high}|s_{\ell}^{high})}\left[\mathbb{L}(\bm{\pi}_{\ell}^{high})\right],$
(6)

where $\bm{\pi}^{sub}$ and $\bm{\pi}^{high}$ are solutions on sub-instance
$s^{sub}$ and high-level instance $s^{high}$, respectively (e.g.,
$\bm{\pi}_{k}^{sub}$ denotes the $k$-th sub-instance’s solution on low-level,
and $\bm{\pi}_{\ell}^{sub}$ denotes the $\ell$-th resolution’s solution on the
high-level instance).

Different from previous studies, such as AM Kool et al. (2019) and POMO Kwon
et al. (2020), our loss function guides the model to learn information of the
instance $s$ at multiple scales by combining both global information (at the
original graph and high-level graph) and local information (at sub-graphs).
These pieces of information can help our model converge faster and prevent it
from converging to local optima. Moreover, training on multiple graph scales
simultaneously helps improve the generalization ability of our pre-trained
model when solving instances of various sizes. The loss
$\operatorname{\mathcal{L}}$ can be optimized by gradient descent using
REINFORCE (Williams, 1992) gradient estimator with a deterministic greedy
rollout baseline used in AM Kool et al. (2019) or shared baseline for
gradients used in POMO Kwon et al. (2020). Note that the shared baseline of
POMO training is a significant improvement of AM. Therefore, in this work, we
use the same REINFORCE algorithm in POMO to train our model for better
performance. More details of training and baseline policy can be found in
Appendix B. Algorithm 2 presents our multiple resolutions graph training with
minibatch in one epoch.

Input: steps per epoch $T$, batch size $B$, number of clusters $K$, number of
resolution levels $L$.

Initialize policy network parameter $\bm{\theta}$;

for  _$\text{step}=1,\ldots,T$_ do

$s_{i}\leftarrow\text{SampleInstance()}\enspace\forall i\in\\{1,\ldots,B\\}$;

$\\{{s_{i}}_{k}^{sub}\\}_{k=1}^{K}$,
$\\{{s_{i}}_{\ell}^{high}\\}_{\ell=1}^{L}$ $\leftarrow$ Multiresolution graphs
construction according to Algorithm 1;

$\bm{\pi}_{i},{\bm{\pi}_{i}}_{k}^{sub},{\bm{\pi}_{i}}_{\ell}^{high}\leftarrow\text{SampleRollout}(s_{i},{s_{i}}_{k}^{sub},{s_{i}}_{\ell}^{high},p_{\bm{\theta}})\enspace\forall
i\in\\{1,\ldots,B\\}$;

$\bm{\pi}_{i}^{\text{BL}},{{\bm{\pi}_{i}}_{k}^{sub}}^{\text{BL}},{{\bm{\pi}_{i}}_{\ell}^{high}}^{\text{BL}}\leftarrow\text{GreedyRollout}(s_{i},{s_{i}}_{k}^{sub},{s_{i}}_{\ell}^{high},{p_{\bm{\theta}}^{\text{BL}}})\enspace\forall
i\in\\{1,\ldots,B\\}$;

$\nabla\mathcal{L}\leftarrow\sum_{i=1}^{B}\left(\Delta_{\mathbb{L}}(\bm{\pi}_{i})+\frac{1}{K}\sum_{k=1}^{K}{\Delta_{\mathbb{L}}({\bm{\pi}_{i}}_{k}^{sub})}+\frac{1}{L-1}\sum_{\ell=1}^{L-1}{\Delta_{\mathbb{L}}({\bm{\pi}_{i}}_{\ell}^{high})}\right)\nabla_{\bm{\theta}}\log
p_{\bm{\theta}}(\bm{\pi}_{i})$, where
$\Delta_{\mathbb{L}}(\bm{\pi}_{x})=\mathbb{L}(\bm{\pi}_{x})-\mathbb{L}({\bm{\pi}_{x}}^{\text{BL}})$;

$\bm{\theta}\leftarrow\text{Adam}(\bm{\theta},\nabla\mathcal{L})$;

Algorithm 2 Multisolution graph Training

###  4.3 Equivariant Attention Model

We use an encoder-decoder architecture similar to the Attention Model (AM)
(Kool et al., 2019). However, we replace the Encoder with an Equivariant Graph
Encoder to respect the equivariant property with geometric transformations on
the input graphs. The Decoder is used in the same manner as the architecture
of AM.

Equivariant Graph Attention Encoder. Take the $d_{\text{x}}$-dimensional input
features $\mathbf{x}_{i}$ of node $v_{i}$ (for TSP, $d_{\text{x}}$ = 2), the
encoder uses a learned linear projection with parameters $W^{\text{x}}$ and
$\mathbf{b}^{\text{x}}$ to computes initial $d_{\text{h}}$-dimensional node
embeddings $\mathbf{h}_{i}^{(0)}$ by
$\mathbf{h}_{i}^{(0)}=W^{\text{x}}\mathbf{x}_{i}+\mathbf{b}^{\text{x}}$. After
obtaining the embeddings, we feed them to $N$ equivariant attention layers. We
denote with $\mathbf{h}_{i}^{(l)}$ the node embeddings produced by layer
$l\in\\{1,\ldots,N\\}$. The encoder computes an aggregated embedding
$\bar{\mathbf{h}}^{(N)}$ of the input graph as the mean of the final node
embeddings $\mathbf{h}_{i}^{(N)}$:
$\bar{\mathbf{h}}^{(N)}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{h}_{i}^{(N)}$.
Similar to AM, both the node embeddings $\mathbf{h}_{i}^{(N)}$ and the graph
embedding $\bar{\mathbf{h}}^{(N)}$ are used as input to the decoder. For the
attention mechanism, we use the Linear, Layer Norm, and Equivariant Graph
Attention sublayers designed by Liao & Smidt (2022) that are equivariant
operators. More details of these sublayers can be found in Appendix B.

Decoder. We use the same decoder as AM (Kool et al., 2019) that reconstructs
the solution (tour $\bm{\pi}$) sequentially. Particularly, the decoder outputs
the node $\pi_{t}$ at each time step $t\in\\{1,..,n\\}$ based on the context
embedding coming from the feature embeddings of node and graph obtained by the
encoder and the previous outputs $\pi_{t}^{\prime}$ at timestep
$t^{\prime}<t$.

##  5 Experiments

###  5.1 Setup

Baselines and Metrics. We compare our proposed model to the solid baseline
methods for both TSP and CVRP, including non-learnable baselines (heuristics):
Concorde (Applegate et al., 2006), LKH3 (Helsgaun, 2017), and Gurobi (Gurobi
Optimization, 2021) and recent neural constructive baselines: AM Kool et al.
(2019), POMO Kwon et al. (2020), MDAM Xin et al. (2021), and Sym-NCO Kim et
al. (2022). We use tour length (Obj), optimality gap (Gap), and evaluation
time (Time) as the metrics to evaluate the performance of our models compared
to other baselines. The smaller the metric values are, the better performance
the model achieves.

Datasets. For synthetic instances, we follow the data generation in previous
works (Kool et al., 2019; Kim et al., 2022) to generate 2D Euclidean instances
where city coordinates are generated independently from a unit square
$[0,1]^{2}$ uniform distribution. We train our model using 20, 50, and
100-node instances. More details are shown in Appendix C. For benchmark
instances, we use the test instances from real-world TSP problems with problem
sizes from 50 up to 400.

Training and hyperparameters. To make fair comparisons, we use the same
training-related hyperparameters from the original paper on neural baselines
when applying our method to these models. We implement our models in Pytorch
(Paszke et al., 2019) and train all models on a machine with server A100
40GPUs. For clustering, we perform the K-means algorithm and execute it in
parallel on GPUs to speed up training time and select 2D coordinates of the
cities as features, and we set $L=2$ for our multiresolution graph
construction. Please refer to Appendix C for more details.

###  5.2 Results on TSP and CVRP

Table 1: Performance of our mEGAT and baseline for TSPs. ‘g’, ‘s’, and ‘bs’
denote greedy, sampling, and the beam search method, respectively. The best
results are in bold.

Model | n=20 | n = 50 | n = 100
---|---|---|---
Obj$\downarrow$ | Gap | Time | Obj$\downarrow$ | Gap | Time | Obj$\downarrow$ | Gap | Time
TSP | Concorde | 3.84 | 0.00 $\%$ | 1m | 5.70 | 0.00 $\%$ | 2m | 7.76 | 0.00 $\%$ | 3m
LKH3 | 3.84 | 0.00 $\%$ | 18s | 5.70 | 0.00 $\%$ | 5m | 7.76 | 0.00 $\%$ | 21m
Gurobi | 3.84 | 0.00 $\%$ | 7s | 5.70 | 0.00 $\%$ | 2m | 7.76 | 0.00 $\%$ | 17m
AM (g.) Kool et al. (2019) | 3.85 | 0.34 $\%$ | 0s | 5.80 | 1.76$\%$ | 2s | 8.12 | 4.53 $\%$ | 6s
AM (s.) Kool et al. (2019) | 3.84 | 0.08 $\%$ | 5m | 5.73 | 0.52$\%$ | 24m | 7.94 | 2.26 $\%$ | 1h
POMO (g.) Kwon et al. (2020) | 3.84 | 0.06 $\%$ | 0s | 5.75 | 0.71 $\%$ | 1s | 7.85 | 1.21 $\%$ | 3s
POMO (s.) Kwon et al. (2020) | 3.84 | 0.02 $\%$ | 1s | 5.72 | 0.50 $\%$ | 3s | 7.80 | 0.48 $\%$ | 16s
MDAM (g.) Xin et al. (2021) | 3.84 | 0.05 $\%$ | 5s | 5.73 | 0.62 $\%$ | 15s | 7.93 | 2.19 $\%$ | 45s
MDAM (bs.) Xin et al. (2021) | 3.84 | 0.00 $\%$ | 5m | 5.70 | 0.03 $\%$ | 20m | 7.80 | 0.48 $\%$ | 1h
Sym-NCO (g.) Kim et al. (2022) | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | 7.84 | 0.94 $\%$ | 2s
Sym-NCO (s.) Kim et al. (2022) | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | 7.79 | 0.39 $\%$ | 16s
mGAT (g.) (Ours) | 3.84 | 0.02 $\%$ | 1s | 5.73 | 0.62 $\%$ | 1s | 7.82 | 0.79 $\%$ | 3s
mGAT (s.) (Ours) | 3.84 | 0.00 $\%$ | 3s | 5.70 | 0.02 $\%$ | 3s | 7.78 | 0.25 $\%$ | 16s
CVRP | LKH3 | 6.14 | 0.58 $\%$ | 2h | 10.38 | 0.00 $\%$ | 7h | 15.65 | 0.00 $\%$ | 13h
Gurobi | 6.10 | 0.00 $\%$ |  | $\\_$ | $\\_$
AM (g.) Kool et al. (2019) | 6.40 | 4.97 $\%$ |  | 10.98 | 5.86 $\%$ | 3s | 16.80 | 7.34 $\%$ | 8s
AM (s.) Kool et al. (2019) | 6.25 | 2.45 $\%$ | 9m | 10.62 | 2.40$\%$ | 28m | 16.23 | 3.72 $\%$ | 1h
POMO (g.) Kwon et al. (2020) | 6.22 | 1.97 $\%$ | 2s | 10.54 | 1.56 $\%$ | 12s | 16.26 | 3.93 $\%$ | 3s
POMO (s.) Kwon et al. (2020) | 6.19 | 1.48 $\%$ | 5s | 10.49 | 1.14 $\%$ | 6s | 15.90 | 1.67 $\%$ | 16s
MDAM (g.) Xin et al. (2021) | 6.24 | 2.29 $\%$ | 15s | 10.74 | 3.47 $\%$ | 16s | 16.40 | 4.86 $\%$ | 45s
MDAM (bs.) Xin et al. (2021) | 6.15 | 0.82 $\%$ | 6m | 10.50 | 1.18 $\%$ | 20m | 16.03 | 2.49 $\%$ | 1h
SymNCO (g.) Kim et al. (2022) | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | 16.10 | 2.88 $\%$ | 3s
Sym-NCO (s.) Kim et al. (2022) | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | $\\_$ | 15.87 | 1.46 $\%$ | 16s
mGAT (g.) (Ours) | 6.20 | 1.64 $\%$ | 2s | 10.50 | 1.15 $\%$ | 12s | 16.08 | 2.75 $\%$ | 3s
mGAT (s.) (Ours) | 6.14 | 0.65 $\%$ | 5s | 10.46 | 0.77 $\%$ | 6s | 15.84 | 1.21 $\%$ | 16s

We first report the testing results of our model for TSPs and VRPs compared
with other baselines on the test instances with 20, 50, and 100 nodes in Table
1. The results are reported on an average of 10,000 test instances via greedy
decoding, i.e., select the best action at each step, and sampling, i.e.,
sample 1280 samples and report the best. It can be seen that our models
outperform the neural baselines for TSPs and CVRPs ($n=$20, 50, and 100) in
terms of solution quality and evaluation time. For the larger size in real-
world TSP instances, we report the results in Table 3 (see Appendix D). The
obtained results also demonstrate that our model performs better solutions in
the fastest time compared with other neural baselines.

###  5.3 Generalization study

Variable-size generalization. We first test the generalization of our model
trained on a larger size ($n=100$) to various smaller sizes of 20 and 50. As
shown in Table 2, the results indicate that our model trained on larger sizes
could perform well on downgrade ones and better than all neural baselines such
as AM, POMO, MDAM, and Sym-NCO. One possible reason is that our model (trained
on TSP100) leverages joint training (multiresolution) on low-level graphs with
smaller sizes. For scale-up sizes, the results on larger sizes ($>100$) in
TSPLib Reinelt (1991) in Table 3 also confirm the superior performance of our
model compared to these previous attention-based models.

Cross-distribution generalization. We examine our model performance on the
cluster and mixed distributions of TSP datasets. As shown in Table 4 in
Appendix D, our model achieves better results for both distributions than POMO
in all settings, especially in Mixed distribution, thus confirming the
efficiency of our multiresolution learning from low-level and high-level
graphs. Please see the Appendix D for more details.

Table 2: Performance of our model compared with baselines (all models trained
on TSP100) on variable TSP sizes.

Model | TSP20 | TSP50 | TSP100
---|---|---|---
Obj$\downarrow$ | Gap | Time | Obj$\downarrow$ | Gap | Time | Obj$\downarrow$ | Gap | Time
AM Kool et al. (2019) | 3.97 | 3.39 $\%$ | 5m | 5.82 | 2.33 $\%$ | 14m | 7.94 | 2.26 $\%$ | 30m
POMO Kwon et al. (2020) | 3.89 | 1.06 $\%$ | 2s | 5.74 | 0.71 $\%$ | 6s | 7.80 | 0.48 $\%$ | 16s
MDAM Xin et al. (2021) | 3.95 | 2.86 $\%$ | 5m | 5.81 | 1.94 $\%$ | 28m | 7.80 | 0.48 $\%$ | 45m
Sym-NCO Kim et al. (2022) | 3.88 | 1.04 $\%$ | 3s | 5.73 | 0.53 $\%$ | 8s | 7.79 | 0.39 $\%$ | 17s
mGAT (Ours) | 3.85 | 0.27 $\%$ | 2s | 5.71 | 0.18 $\%$ | 6s | 7.78 | 0.25 $\%$ | 16s

###  5.4 Ablation studies

Equivariance analysis. To validate the equivariant performance of our models
on transformation data sets, we generate a new test set, including instances
from the training set that undergoes three transformations: rotation,
translation, and scaling. Particularly, we use a $90\degree$ counterclockwise
rotation on the center point located at $[0.5,0.5]$, a translation with
mapping rule $(x,y)\mapsto(x+\Delta x,y+\Delta y)$ ($\Delta x,\Delta
y\in[0,1]$), and a random scaling of the distances in the range of
$[0.7,1.2]$. The results in Figure 3 show that our model is more stable than
the baseline on the transformation datasets, thus confirming the crucial role
of the equivariant deep model for CO problems.

(a) TSP20

(b) TSP50

(c) TSP100

Figure 3: Equivariance ablation analysis to geometric transformations. (a)
Performance on TSP20, (b) Performance on TSP50, (c) Performance on TSP100.

Multiple resolutions learning. We conduct an ablation study on TSP50 and
TSP100 to verify the design of our model, where we replace the multiresolution
graph training (w/o multiresolution) with the same baseline training as POMO
and equivariant graph attention encoder (w/o equivariant) with the same
attention encoder as AM. As can be seen from Table 4, the use of
multiresolution graph training further enhances the learning effectiveness,
and the equivariant encoder plays a prominent role in the stability
performance of our model.

Figure 4: Ablation studies of our model designs and the impact of $K$ (number
of clusters) on model’s performance.

Model | TSP50 | TSP100
---|---|---
Obj. | Gap | Obj. | Gap
w/o multiresolution | $5.74$ | $0.70\%$ | $7.94$ | $2.26\%$
w/o equivariant | $5.71$ | $0.18\%$ | $7.87$ | $1.42\%$
Ours | $5.70$ | $0.00\%$ | $7.86$ | $1.29\%$
Ours ($K=5$) | $5.74$ | $0.7\%$ | $8.20$ | $5.67\%$
Ours ($K=10$) | $5.76$ | $1.05\%$ | $8.01$ | $3.22\%$

Furthermore, we also evaluate the influence of the number of clusters $K$ when
dividing the original graph into sub-graphs on the model’s performance. We
report the results with $K=5$, $K=10$ of our models trained on 100,000 samples
on the fly and evaluated on the 10,000 test instances in Table 4. It can be
seen that concerning the larger input graph size, a larger number of clusters
$K$ help the model learn and obtain better performance. To further validate
the faster convergence of our model via multiresolution graph training, we
show additional results in Appendix D. Figure 6 indicates that leveraging
multiresolution learning can help the model convergence faster and more
stable.

##  6 Conclusion

The routing problems, e.g., TSPs and VRPs, are key topics in operations
research due to their wide applications in transportation and logistics. In
this work, we propose a novel multiple-resolution equivariant architecture
that learns and extracts features effectively to generate better routing
solutions. Moreover, we demonstrate empirically that our model is equivariant
to input transformations and generalizes well to various input sizes, which
significantly reduces the training costs in real-world applications and can
have positive social impacts. Our research suggests that imposing symmetries
and exploiting the multiscale structures are necessary for a wide range of
other applications in operation research and optimization. In future work, we
aim to apply our model to other NP-hard combinatorial optimization problems
and develop a more general model that can find optimal solutions with minimal
training and inference costs.

## References

  * Anderson et al. (2019) Brandon Anderson, Truong Son Hy, and Risi Kondor.  Cormorant: Covariant molecular neural networks.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/03573b32b2746e6e8ca98b9123f2249b-Paper.pdf.
  * Applegate et al. (2006) David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook.  Concorde tsp solver, 2006.
  * Applegate et al. (2009) David L Applegate, Robert E Bixby, Vašek Chvátal, William Cook, Daniel G Espinoza, Marcos Goycoolea, and Keld Helsgaun.  Certification of an optimal tsp tour through 85,900 cities.  _Operations Research Letters_ , 37(1):11–15, 2009\.
  * Battaglia et al. (2016) Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray kavukcuoglu.  Interaction networks for learning about objects, relations and physics.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , NIPS’16, pp. 4509–4517, Red Hook, NY, USA, 2016. Curran Associates Inc.  ISBN 9781510838819.
  * Bellman (1962) Richard Bellman.  Dynamic programming treatment of the travelling salesman problem.  _Journal of the ACM (JACM)_ , 9(1):61–63, 1962\.
  * Cheng et al. (2023) Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu.  Select and optimize: Learning to solve large-scale tsp instances.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 1219–1231. PMLR, 2023.
  * Clausen (1999) Jens Clausen.  Branch and bound algorithms-principles and examples.  _Department of Computer Science, University of Copenhagen_ , pp. 1–30, 1999.
  * Cohen & Welling (2016) Taco Cohen and Max Welling.  Group equivariant convolutional networks.  In Maria Florina Balcan and Kilian Q. Weinberger (eds.), _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pp. 2990–2999, New York, New York, USA, 20–22 Jun 2016. PMLR.  URL https://proceedings.mlr.press/v48/cohenc16.html.
  * Cohen & Welling (2017) Taco S. Cohen and Max Welling.  Steerable CNNs.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=rJQKYt5ll.
  * Cohen et al. (2018) Taco S. Cohen, Mario Geiger, Jonas Köhler, and Max Welling.  Spherical CNNs.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=Hkbd5xZRb.
  * Croes (1958) Georges A Croes.  A method for solving traveling-salesman problems.  _Operations research_ , 6(6):791–812, 1958.
  * Dai et al. (2017) Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial optimization algorithms over graphs.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, pp. 6351–6361, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Dwivedi et al. (2022) Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini.  Long range graph benchmark.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), _Advances in Neural Information Processing Systems_ , volume 35, pp. 22326–22340. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/8c3c666820ea055a77726d66fc7d447f-Paper-Datasets_and_Benchmarks.pdf.
  * Feillet et al. (2005) Dominique Feillet, Pierre Dejax, and Michel Gendreau.  Traveling salesman problems with profits.  _Transportation science_ , 39(2):188–205, 2005\.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl.  Neural message passing for quantum chemistry.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, pp. 1263–1272. JMLR.org, 2017.
  * Glover & Laguna (1998) Fred Glover and Manuel Laguna.  _Tabu search_.  Springer, 1998.
  * Gurobi Optimization (2021) LLC Gurobi Optimization.  Gurobi optimizer reference manual, 2021.
  * Held & Karp (1962) Michael Held and Richard M Karp.  A dynamic programming approach to sequencing problems.  _Journal of the Society for Industrial and Applied mathematics_ , 10(1):196–210, 1962.
  * Helsgaun (2017) Keld Helsgaun.  An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems.  _Roskilde: Roskilde University_ , 12, 2017.
  * Holland (1992) John H Holland.  Genetic algorithms.  _Scientific american_ , 267(1):66–73, 1992.
  * Hy & Kondor (2023) Truong Son Hy and Risi Kondor.  Multiresolution equivariant graph variational autoencoder.  _Machine Learning: Science and Technology_ , 4(1):015031, mar 2023.  doi: 10.1088/2632-2153/acc0d8.  URL https://dx.doi.org/10.1088/2632-2153/acc0d8.
  * Hy et al. (2018) Truong Son Hy, Shubhendu Trivedi, Horace Pan, Brandon M Anderson, and Risi Kondor.  Predicting molecular properties with covariant compositional networks.  _The Journal of chemical physics_ , 148(24):241745, 2018.
  * Hy et al. (2019) Truong Son Hy, Shubhendu Trivedi, Horace Pan, Brandon M Anderson, and Risi Kondor.  Covariant compositional networks for learning graphs.  In _Proc. International Workshop on Mining and Learning with Graphs (MLG)_ , 2019.
  * 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.
  * Kearnes et al. (2016) Steven M. Kearnes, Kevin McCloskey, Marc Berndl, Vijay S. Pande, and Patrick F. Riley.  Molecular graph convolutions: moving beyond fingerprints.  _Journal of Computer-Aided Molecular Design_ , 30:595–608, 2016.
  * Kim et al. (2022) Minsu Kim, Junyoung Park, and Jinkyoo Park.  Sym-nco: Leveraging symmetricity for neural combinatorial optimization.  _Advances in Neural Information Processing Systems_ , 35:1936–1949, 2022.
  * Kondor et al. (2018) Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi.  Covariant compositional networks for learning graphs.  _arXiv preprint arXiv:1801.02144_ , 2018.
  * Kool et al. (2019) Wouter Kool, Herke van Hoof, and Max Welling.  Attention, learn to solve routing problems!  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=ByxBFsRqYm.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.), _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.  URL https://proceedings.neurips.cc/paper_files/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf.
  * 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.  _Advances in Neural Information Processing Systems_ , 33:21188–21198, 2020.
  * Laporte (1992a) Gilbert Laporte.  The traveling salesman problem: An overview of exact and approximate algorithms.  _European Journal of Operational Research_ , 59(2):231–247, 1992a.
  * Laporte (1992b) Gilbert Laporte.  The vehicle routing problem: An overview of exact and approximate algorithms.  _European journal of operational research_ , 59(3):345–358, 1992b.
  * Laporte (2009) Gilbert Laporte.  Fifty years of vehicle routing.  _Transportation science_ , 43(4):408–416, 2009\.
  * LeCun et al. (1989) Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural Computation_ , 1(4):541–551, 1989.  doi: 10.1162/neco.1989.1.4.541.
  * Li et al. (2021) Sirui Li, Zhongxia Yan, and Cathy Wu.  Learning to delegate for large-scale vehicle routing.  _Advances in Neural Information Processing Systems_ , 34:26198–26211, 2021.
  * Liao & Smidt (2022) Yi-Lun Liao and Tess Smidt.  Equiformer: Equivariant graph attention transformer for 3d atomistic graphs.  _arXiv preprint arXiv:2206.11990_ , 2022.
  * Lin & Kernighan (1973) Shen Lin and Brian W Kernighan.  An effective heuristic algorithm for the traveling-salesman problem.  _Operations research_ , 21(2):498–516, 1973.
  * Lysgaard et al. (2004) Jens Lysgaard, Adam N Letchford, and Richard W Eglese.  A new branch-and-cut algorithm for the capacitated vehicle routing problem.  _Mathematical Programming_ , 100:423–445, 2004.
  * Maron et al. (2019) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=Syx72jC9tm.
  * Ngo et al. (2023) Nhat Khang Ngo, Truong Son Hy, and Risi Kondor.  Multiresolution graph transformers and wavelet positional encoding for learning long-range and hierarchical structures.  _The Journal of Chemical Physics_ , 159(3):034109, 07 2023.  ISSN 0021-9606.  doi: 10.1063/5.0152833.  URL https://doi.org/10.1063/5.0152833.
  * Niepert et al. (2016) Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov.  Learning convolutional neural networks for graphs.  In _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ , ICML’16, pp. 2014–2023. JMLR.org, 2016.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Peng et al. (2020) Bo Peng, Jiahai Wang, and Zizhen Zhang.  A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems.  In _Artificial Intelligence Algorithms and Applications: 11th International Symposium, ISICA 2019, Guangzhou, China, November 16–17, 2019, Revised Selected Papers 11_ , pp. 636–650. Springer, 2020.
  * Prates et al. (2019) Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi.  Learning to solve np-complete problems: A graph neural network for decision tsp.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 4731–4738, 2019.
  * Ravanbakhsh et al. (2017) Siamak Ravanbakhsh, Jeff Schneider, and Barnabás Póczos.  Equivariance through parameter-sharing.  In Doina Precup and Yee Whye Teh (eds.), _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 2892–2901. PMLR, 06–11 Aug 2017.  URL https://proceedings.mlr.press/v70/ravanbakhsh17a.html.
  * Reinelt (1991) Gerhard Reinelt.  Tsplib—a traveling salesman problem library.  _ORSA journal on computing_ , 3(4):376–384, 1991\.
  * Scarselli et al. (2009) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  _IEEE Transactions on Neural Networks_ , 20(1):61–80, 2009.  doi: 10.1109/TNN.2008.2005605.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le.  Sequence to sequence learning with neural networks.  _Advances in neural information processing systems_ , 27, 2014.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Vinyals et al. (2015) Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Weiler et al. (2018) Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen.  3d steerable cnns: Learning rotationally equivariant features in volumetric data.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, pp. 10402–10413, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Williams (1992) Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Reinforcement learning_ , pp. 5–32, 1992.
  * Wu et al. (2020) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ , 32(1):4–24, 2020.
  * Xin et al. (2021) Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang.  Multi-decoder attention model with embedding glimpse for solving vehicle routing problems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 12042–12049, 2021.
  * Zaheer et al. (2017) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/f22e4747da1aa27e363d86d40ff442fe-Paper.pdf.

##  Appendix A More on group and representation theory

######  Definition A.1 (Group).

A set $G$ with a binary operation $\circ:G\times G\rightarrow G$ is called a
group if it satisfies the following properties:

  * •

Closure: $\forall g,g^{\prime}\in G,g\circ g^{\prime}\in G$.

  * •

Associativity: $(g\circ g^{\prime})\circ
g^{\prime\prime}=g\circ(g^{\prime}\circ g^{\prime\prime})$ for any
$g,g^{\prime},g^{\prime\prime}\in G$.

  * •

Identity: $\exists e\in G$ such that $e\circ g=g\circ e=g$ for all $g\in G$.

  * •

Inverse: $\forall g\in G$, there is an element $g^{-1}\in G$ such that $g\circ
g^{-1}=g^{-1}\circ g=e$.

A group $G$ is finite if the number of elements in $G$ is finite. A group $G$
is called Abelian or commutative group if $g\circ g^{\prime}=g^{\prime}\circ
g$ for every pair of $g,g^{\prime}\in G$.

In order to build symmetry-preserving models, we are interested in how groups
act on data. We assume that there is a domain $\Omega$ underlying our data. A
group action of $G$ on a set $\Omega$ is defined as a mapping $(g,x)\mapsto
g\cdot x$ associating a group element $g\in G$ and a point $x\in\Omega$ with
some other point on $\Omega$ in a way that is compatible with the group
operations, i.e.:

  * •

$x=g\circ(g^{-1}\cdot x)=g^{-1}\circ(g\cdot x)$ for all $g\in G$ and
$x\in\Omega$;

  * •

$g\circ(h\cdot x)=(g\circ h)\cdot x$ for all $g,h\in G$ and $x\in\Omega$;

  * •

If $G$ is Abelian then $g\circ(h\cdot x)=h\circ(g\cdot x)$ for all $g,h\in G$
and $x\in\Omega$.

Symmetry of the domain $\Omega$ imposes structure on the function $f$ defined
on the domain. We define invariant and equivariant functions in Def. A.2 and
Def. A.3, respectively.

######  Definition A.2 (Invariance).

A function $f:\Omega\rightarrow\mathcal{X}$ is $G$-invariant if $f(g\cdot
x)=f(x)$ for every $g\in G$, i.e. regardless of how we transform the input by
a group action, the function’s outcome in some space $\mathcal{X}$ is
unchanged.

######  Definition A.3 (Equivariance).

A function $f:\Omega\rightarrow\Omega$ is $G$-equivariant if $f(g\cdot
x)=g\cdot f(x)$ for every $g\in G$, i.e. the group action on the input affects
the output in a completely predictable way222Indeed, $G$-invariant is a
special case of $G$-equivariant..

The most important kind of group actions is linear group actions, also known
as group representation or simply representation. A linear action $g$ on
signals on the domain $\Omega$ is understood in the sense that $g\cdot(\alpha
x+\beta x^{\prime})=\alpha(g\cdot x)+\beta(g\cdot x^{\prime})$ for any scalars
$\alpha,\beta\in\mathbb{C}$ and signals $x,x^{\prime}\in\Omega$. We can
describe linear actions either as maps $(g,x)\mapsto g\cdot x$ that are linear
in $x$, or equivalently, as a map $\rho:G\rightarrow\mathbb{C}^{d\times d}$
that assigns to each group element $g\in G$ a $d\times d$ invertible matrix
$\rho(g)$, satisfying the condition $\rho(g\circ h)=\rho(g)\rho(h)$ for all
$g,h\in G$. Here, the matrix representing a composite group element $g\circ
h$, i.e. $\rho(g\circ h)$, is equal to the matrix product of the
representation of $g$ and $h$, i.e. $\rho(g)\rho(h)$.

Let $M_{d}$ be the set $d\times d$ complex matrices. A matrix group is a set
of matrices in $M_{d}$ which satisfy the properties of a group under matrix
multiplication. Formally, a representation $\rho$ of a group $G$ is defined as
a function which maps $G$ to a matrix group, preserving group multiplication
(see Def. A.4).

######  Definition A.4 (Representation).

Given a group $G$, a $d$-dimensional representation of $G$ is a matrix valued
function $\rho:G\rightarrow\mathbb{C}^{d\times d}$ such that

$\rho(g)\rho(h)=\rho(g\circ h),$

for all $g$ and $h$ in $G$.

A group homomorphism is a map between groups that preserves the group
operation (see Def. A.5). Alternatively, we can also define the representation
based on homomorphism as in Def. A.6.

######  Definition A.5 (Homomorphism).

Let $G$ and $H$ be two groups and let $\circ$ denote the group operation. A
homomorphism $\phi:G\rightarrow H$ is a map satisfying

$\phi(g\circ g^{\prime})=\phi(g)\circ\phi(g^{\prime}),$

for all $g$ and $g^{\prime}$ in $G$.

######  Definition A.6 (Representation).

Let $G$ be a group and $V$ be a vector space over a field $\mathbb{F}$. A
representation of $G$ over $V$ is a homomorphism

$\rho:G\rightarrow\text{GL}(V),$

where $\text{GL}(V)$ is the general linear group on $V$, or the group of
invertible linear maps $\phi:V\rightarrow V$.

Symmetry of the signals’ domain $\Omega$ imposes structure on the function $f$
defined on such signals. Given the help from representation, we can define
invariant and equivariant functions more precisely, as in Def. A.7 and Def.
A.8, respectively. Invariance means that regardless of how we transform the
input by a linear group action (or multiplying with a group representation),
the function’s outcome in some space $\mathcal{X}$ is unchanged.

######  Definition A.7 (Invariant fucntion).

Given a group $G$ and its non-trivial representation $\rho$, a function
$f:\Omega\rightarrow\mathcal{X}$ is $G$-invariant if

$f(\rho(g)x)=f(x),$

for all $g\in G$ and $x\in\Omega$.

######  Definition A.8 (Equivariant fucntion).

Given a group $G$, its non-trivial representation $\rho$ and another
representation $\rho^{\prime}$ (indeed, $\rho$ and $\rho^{\prime}$ can be
identical), a function $f:\Omega\rightarrow\Omega^{\prime}$ is $G$-equivariant
or $G$-covariant if

$f(\rho(g)x)=\rho^{\prime}(g)f(x),$

for all $g\in G$ and $x\in\Omega$.

A neural network $\bm{f}$, in general, can be written as a composition of
multiple functions $\\{f_{1},\ldots,f_{L}\\}$ in which function $f_{\ell}$ is
the $\ell$-th layer out of $L$ layers of the network:

$\bm{f}=f_{L}\circ f_{L-1}\circ\ldots\circ f_{1},$

where $f_{1}$ is the bottom layer directly taking the input data and $f_{L}$
is the top or output layer making the decision. A $G$-equivariant neural
network (or simply equivariant neural network) is the one composing of all
$G$-equivariant layers. If the model outputs scalar values, the top layer
$f_{L}$ is $G$-invariant. For example, Fig. 5 depicts Equivariant Graph
Attention (Liao & Smidt, 2022) model that is equivariant with respect to
permutation and rotation groups.

###  A.1 Symmetricities in COs

Symmetricities are found in various COPs Kwon et al. (2020); Kim et al.
(2022). We conjecture that imposing those symmetricities on $F_{\theta}$
improves the generalization and sample efficiency of $F_{\theta}$. We define
the two identified symmetricities that are commonly found in various COPs:

######  Definition A.9 (Problem Symmetricity).

Problem $\bm{P}^{i}$ and $\bm{P}^{j}$ are problem symmetric
($\bm{P}^{i}\xleftrightarrow{\text{sym}}\bm{P}^{j}$) if their optimal solution
sets are identical.

######  Definition A.10 (Solution Symmetricity).

Two solutions ${\bm{\pi}}^{i}$ and ${\bm{\pi}}^{j}$ are solution symmetric
(${\bm{\pi}}^{i}\xleftrightarrow{\text{sym}}{\bm{\pi}}^{j}$) on problem
$\bm{P}$ if $R({\bm{\pi}}^{i};\bm{P})=R({\bm{\pi}}^{j};\bm{P})$.

Several problem geometric symmetricity found in various COPs is the rotation,
translation, and reflection:

######  Theorem A.11 (Geometric symmetricity).

For any orthogonal matrix $Q$, the problem $\bm{P}$ and
$Q(\bm{P})\triangleq\\{\\{Qx_{i}\\}_{i=1}^{N},\bm{f}\\}$ are problem
symmetric: i.e., $\bm{P}\xleftrightarrow{\text{sym}}Q(\bm{P})$.

Proof. We prove the Theorem A.11, which states a problem $\bm{P}$ and its’
orthogonal transformed problem $Q(\bm{P})=\\{\\{Qx_{i}\\}_{i=1}^{N},\bm{f}\\}$
have identical optimal solutions if $Q$ is orthogonal matrix:
$QQ^{T}=Q^{T}Q=I$.

As we mentioned in A.1, reward $R$ is a function of $\bm{a}_{1:T}$ (solution
sequences),
$||x_{i}-x_{j}||_{i,j\in\\{1,...N\\}}$ (relative distances) and $\bm{f}$
(nodes features).

For simple notation, let denote $||x_{i}-x_{j}||_{i,j\in\\{1,...N\\}}$ as
$||x_{i}-x_{j}||$. And Let $R^{*}(\bm{P})$ is optimal value of problem
$\bm{P}$: i.e.

$R^{*}(\bm{P})=R({\bm{\pi}}^{*};\bm{P})=R\left({\bm{\pi}}^{*};\\{||x_{i}-x_{j}||,\bm{f}\\}\right)$

Where $\pi^{*}$ is an optimal solution of problem $\bm{P}$. Then the optimal
value of transformed problem $Q(\bm{P})$, $R^{*}(Q(\bm{P}))$ is invariant:

$\displaystyle R^{*}(Q(\bm{P}))$ $\displaystyle=R({\bm{\pi}}^{*};Q(\bm{P}))$
$\displaystyle=R\left({\bm{\pi}}^{*};\\{||Qx_{i}-Qx_{j}||,\bm{f}\\}\right)$
$\displaystyle=R\left({\bm{\pi}}^{*};\\{\sqrt{(Qx_{i}-Qx_{j})^{T}(Qx_{i}-Qx_{j})},\bm{f}\\}\right)$
$\displaystyle=R\left({\bm{\pi}}^{*};\\{\sqrt{(x_{i}-x_{j})^{T}Q^{T}Q(x_{i}-x_{j})},\bm{f}\\}\right)$
$\displaystyle=R\left({\bm{\pi}}^{*};\\{\sqrt{(x_{i}-x_{j})^{T}I(x_{i}-x_{j})},\bm{f}\\}\right)$
$\displaystyle=R\left({\bm{\pi}}^{*};\\{||x_{i}-x_{j}||,\bm{f}\\}\right)=R({\bm{\pi}}^{*};\bm{P})=R^{*}(\bm{P})$

Therefore, the problem transformation of an orthogonal matrix $Q$ does not
change the optimal value.

Then, the remaining proof is to show $Q(\bm{P})$ has an identical solution set
with $\bm{P}$.

Let optimal solution set $\Pi^{*}(P)=\\{{\bm{\pi}}^{i}(\bm{P})\\}_{i=1}^{M}$,
where ${\bm{\pi}}^{i}(\bm{P})$ indicates optimal solution of $\bm{P}$ and $M$
is the number of heterogeneous optimal solution.

For any ${\bm{\pi}}^{i}(Q(\bm{P}))\in\Pi^{*}(Q(\bm{P}))$, they have same
optimal value with $\bm{P}$:

$\displaystyle
R({\bm{\pi}}^{i}(Q(\bm{P}));Q(\bm{P}))=R^{*}(Q(\bm{P}))=R^{*}(\bm{P})$

Thus, ${\bm{\pi}}^{i}(Q(\bm{P}))\in\Pi^{*}(P)$.

Conversely, For any ${\bm{\pi}}^{i}(\bm{P})\in\Pi^{*}(\bm{P})$, they have
sample optimal value with $Q(\bm{P})$:

$\displaystyle
R({\bm{\pi}}^{i}(\bm{P});\bm{P})=R^{*}(\bm{P})=R^{*}(Q(\bm{P}))$

Thus, ${\bm{\pi}}^{i}(\bm{P})\in\Pi^{*}(Q(\bm{P}))$.

Therefore, $\Pi^{*}(\bm{P})=\Pi^{*}(Q(\bm{P}))$, i.e.,
$\bm{P}\xleftrightarrow{\text{sym}}Q(\bm{P})$.

##  Appendix B Methodology

#### Motivation.

Previous works on solving TSP problems for large input sizes usually simplify
the original problem and find solutions for the simplified versions first,
then combine them to obtain the final solution (Li et al., 2021; Cheng et al.,
2023; Kwon et al., 2020). The most common approach is divide and conquer,
which splits the original graph into multiple smaller graphs and solves them
separately. Then, it combines the local optima to generate the global one.
However, this approach tends to get stuck in local optima because it is hard
to design a good merging algorithm that can efficiently combine local paths.
Motivated by this limitation, we propose an architecture that can transform
the original complex graph into a simpler one without losing important
features. After finding a solution for the simpler version, we use this
information to help the original graph learn easier. Along with this, we also
provide a symmetry-preserving graph attention network, which can learn
equivariant solutions.

#### Encoder.

Figure 5: Equivariant Graph Attention based Encoder. Input nodes are embedded
and processed by $N$ sequential layers, each consisting of a Layer Norm,
Equivariant Graph Attention, and node-wise Feed-Forward sublayer. The graph
embedding is computed as the mean of node embeddings. Best viewed in color.

Figure 5 describes the details of our Equivariant Graph Attention Encoder. Our
encoder consists of a linear layer and several equivariant graph attention
layers ($N$ layers), each with four sublayers. Inspired by Transformer
(Vaswani et al., 2017) and AM (Kool et al., 2019), each graph attention layer
consists of two sublayers: Equivariant Graph Attention (EGA) layer and Feed-
forward (FF) layer following the designs of Liao & Smidt (2022). In our
setting, we use 8 attention heads with a dimensionality of 16. A feed-forward
sublayer in each graph attention layer has a dimension of 512. We also use
these settings for both TSP and CVRP.

#### Training via Reinforce with greedy rollout baseline.

We use the Rollout baseline proposed by Kool et al. (2019) as baseline $b(s)$
to train our model. We also compare the performance of our model to AM with
the same Rollout baseline to demonstrate that the overall performance
improvement is due to our multiresolution graph training strategy.

##  Appendix C Experimental Settings

Training and hyperparameters. For fair comparisons, the training
hyperparameters are set the same as POMO (Kwon et al., 2020). Our model was
trained for 2000 epochs (1̃ week) with a batch size of 256 on the generated
dataset on the fly. We use 3 layers in the encoder with 8 heads and set the
hidden dimension to $D=128$. The optimizer is Adam with an initialized
learning rate as $\eta=10^{-4}$ and will be reduced every epoch with a
learning rate decay is $1.0$. We implement our models in Pytorch (Paszke et
al., 2019) and train all models on a machine with server A100 40GPUs. All the
remaining parameters, such as random seed, are set the same as in Kwon et al.
(2020). For clustering, we perform the K-means algorithm on PyTorch and
execute it in parallel on GPUs to speed up training time and select 2D
coordinates of the cities as features. The training time with the various
problem sizes ranges from hours to 1 week. For the baselines, we use the same
hyperparameters similar to the original works Kool et al. (2019); Kwon et al.
(2020) that give the best performance for each problem, i.e. TSP and CVRP.

##  Appendix D Additional Results

###  D.1 Travelling Salesperson Problem

#### Scalability large-scale dataset.

We further investigate the scalability performance of our model by scaling our
trained model on TSP100 datasets to larger instances on the TSPLIB benchmark
with 50 to 400 nodes and 2D Euclidean distances (34 instances). The full
results are shown in Table 3.

Table 3: Generalization performance of our model compared with baseline AM on various real-world TSPs instances in TSPLIB. We report the average results across 10 independent runs per problem instance. The better results are in bold. Model |  | POMO | Sym-NCO | Ours
---|---|---|---|---
Instance | OTP | Obj | Gap (%) | Obj | Gap (%) | Obj | Gap (%)
eil51 | 426 | 429 | 0.70 | 432 | 1.41 | 426 | 0.00
berlin52 | 7542 | 7545 | 0.04 | 7544 | 0.03 | 7544 | 0.03
st70 | 675 | 677 | 0.30 | 677 | 0.30 | 679 | 0.59
rat99 | 1211 | 1270 | 4.87 | 1261 | 4.13 | 1233 | 1.82
kroA100 | 21282 | 21486 | 0.96 | 21397 | 0.54 | 21397 | 0.54
kroB100 | 22141 | 22285 | 0.65 | 22378 | 1.07 | 22285 | 0.65
kroC100 | 20749 | 20755 | 0.03 | 20930 | 0.87 | 20755 | 0.03
kroD100 | 21294 | 21488 | 0.91 | 21696 | 1.89 | 21488 | 0.91
kroE100 | 22068 | 22196 | 0.58 | 22313 | 1.11 | 22196 | 0.58
eil101 | 629 | 641 | 1.91 | 641 | 1.91 | 641 | 1.91
lin105 | 14379 | 14690 | 2.16 | 14558 | 1.24 | 14442 | 0.44
pr107 | 44303 | 47853 | 8.01 | 47853 | 8.01 | 46572 | 5.12
pr124 | 59030 | 59353 | 0.55 | 59202 | 0.29 | 59202 | 0.29
bier127 | 118282 | 125331 | 5.96 | 122664 | 3.70 | 122664 | 3.70
ch130 | 6110 | 6112 | 0.03 | 6118 | 0.13 | 6112 | 0.03
pr136 | 96772 | 97481 | 0.73 | 97579 | 0.83 | 97481 | 0.73
pr144 | 58537 | 59197 | 1.13 | 58930 | 0.67 | 58930 | 0.67
kroA150 | 26524 | 26833 | 1.16 | 26865 | 1.29 | 26822 | 1.12
kroB150 | 26130 | 26596 | 1.78 | 26648 | 1.98 | 26502 | 1.42
pr152 | 73682 | 74372 | 0.94 | 75292 | 2.19 | 74372 | 0.94
u159 | 42080 | 42567 | 1.16 | 42602 | 1.24 | 42567 | 1.16
rat195 | 2323 | 2546 | 9.60 | 2502 | 7.71 | 2403 | 3.44
kroA200 | 29368 | 29937 | 1.94 | 29816 | 1.53 | 29752 | 1.31
ts225 | 126643 | 131811 | 4.08 | 127742 | 0.87 | 127742 | 0.87
pr226 | 80369 | 82428 | 2.56 | 82337 | 2.45 | 82428 | 2.56
Average |  |  | 2.11 % |  | 1.90 % |  | 1.23 %

#### Cross-distribution generalization.

For cluster distribution, we first sample 2D coordinates of $n_{c}$ cluster
centroids and then sample cities around the centroids. For the mixed
distribution, we sample $50\%$ of the cities from a uniform distribution and
the rest from around cluster centers. For each distribution, we generate a
test dataset of instances with a number of cities $n\in\\{20,50,100\\}$ and a
number of clusters $n_{c}\in\\{3,5,10\\}$. Our model is trained on uniform
datasets and tested on these datasets of the same size. More results of our
model on TSP50 and TSP100 on the cluster and mixed distributions of datasets
are shown in Table 4. The obtained results confirm that our model performs
better AM for both distributions in all settings, especially in mixed
distributions.

Table 4: Predicted tour length of our models for TSP50 and TSP100 on clustered and mixed distributions.  | Setting | $n_{c}=3$ | $n_{c}=5$ | $n_{c}=10$
---|---|---|---|---
TSP50 | Cluster | POMO | 3.67 | 3.65 | 4.23
Ours | 3.66 | 3.63 | 4.22
Mixed | POMO | 5.34 | 5.26 | 5.57
Ours | 5.26 | 5.19 | 5.56
TSP100 | Cluster | POMO | 4.97 | 5.08 | 5.68
Ours | 4.94 | 4.90 | 5.54
Mixed | POMO | 7.02 | 7.04 | 7.35
Ours | 6.92 | 6.89 | 7.22

#### Convergence performance analysis.

We validate the training performance of our model through learning curves
compared to the baseline AM (Kool et al., 2019) and the optimal solution
obtained by Concorde (Applegate et al., 2006). Figure 6 illustrates the
learning curves of the models on TSP20 and TSP50. It can be observed that our
model training is more stable and has faster convergence compared to AM with
the same settings, thanks to its ability to parallelize the learning process
across multiple resolutions (low-level and high-level) of the input graph.

(a) TSP20

(b) TSP50

Figure 6: Learning curves of our model trained on 100,000 samples generated on
the fly for TSP20 and TSP50. We compare our model with the baseline AM with
the same settings to validate the convergence performance. The results are
evaluated on a validation set of 10,000 random instances on the fly.

###  D.2 Capacitated Vehicle Routing Problem

We further assess the performance of our model for another well-known routing
problem, e.g., Capacitated Vehicle Routing Problem (CVRP). The CVRP can be
defined as follows. We have a depot node $0$ and a set of $n$ cities node
$\\{v_{1},\ldots,v_{n}\\}$, each city node $v$ has a demand $d_{v}$ to
fulfill. There is a vehicle with capacity $C$ that need to start and end at
the depot and visit a route of cities such that the sum of city demands along
the route does not exceed $C$, i.e. $\sum_{v\in R_{j}}{d_{v}}\leq C$, where
$R_{j}$ is $j$-th route.

Similar to (Kool et al., 2019), we generate instances with $n=20,50,100$
cities, and normalize the demands by the capacities, i.e.
$\hat{d}_{v_{i}}=\frac{d_{v_{i}}}{C}$, $i\in[\\![1,n]\\!]$. The demand
$d_{v_{i}}$ sampled uniformly from $\\{1,2,...,9\\}$ and $C=30,40,50$ for
$n=20,50,100$, respectively.

###  D.3 Visualization

(a) TSP20 by POMO

(b) TSP20 by our model

(c) TSP50 by POMO

(d) TSP50 by our model

(e) TSP100 by POMO

(f) TSP100 by our model

Figure 7: Example results on TSP20, TSP50, and TSP100 obtained by our model
and the baseline AM trained on the same size.

(a) TSP200 by POMO

(b) TSP200 by our model

(c) TSP1000 by POMO

(d) TSP1000 by our model

Figure 8: Example results on larger size TSP instances obtained by our model
and the baseline AM trained on TSP100.

(a) TSP berlin52 by POMO

(b) TSP berlin52 by our model

(c) TSP pr76 by POMO

(d) TSP pr76 by our model

(e) TSP rd100 by POMO

(f) TSP rd100 by our model

Figure 9: Example results obtained by our model and the baseline AM on real-
world TSP instances in TSPLib.

(a) Solution obtained by POMO

(b) Solution obtained by our model

(c) Solution obtained by POMO

(d) Solution obtained by our model

(e) Solution obtained by POMO

(f) Solution obtained by our

(g) Solution obtained by POMO

(h) Solution obtained by our

Figure 10: Example results on CVRP100 instances. The solutions obtained by our
model and the baseline POMO trained on CVRP100.


# An automated testing system for the RD51 VMM hybrid and yield measurement of
the first production batches

Finn Jaekel  Klaus Desch  Jochen Kaminski  Michael Lupberger
<EMAIL_ADDRESS>Lucian Scharenberg  Patrick Schwaebig
Universität Bonn, Bonn, Germany  CERN, Geneva, Switzerland

###### Abstract

We present the development of an automated testing system for the VMM hybrid
of the RD51 collaboration. The VMM hybrid is a new front-end board for the
RD51 common readout system, the Scalable Readout System, and will become the
workhorse for the next decade to read out Micro-Pattern Gaseous Detectors. It
uses the VMM chip developed for the ATLAS New Small Wheel to convert charge
signals from detectors to digital data. Our testing system automatically
characterises the quality of the VMM chips on the hybrid after production
during multiple tests. Results are evaluated to classify the chips and hybrids
and uploaded to a database. We evaluated those results for the first two
production batches to measure the production yield. The yield is better than
the threshold below which chip testing on a wafer level offers financial
benefits. Observations on prominent chip failures were propagated back to the
hybrid production process to further increase the yield for future
productions.

###### keywords:

Front-end electronics for detector readout, Digital electronic circuits,
Performance of High Energy Physics Detectors, ASIC characterisation, SRS, VMM

††journal: Nuclear Instruments and Methods in Physics Research Section A,

##  1 Introduction

The Scalable Readout System (SRS) [1] is the general-purpose readout
electronics developed by the RD51 collaboration. It implements several front-
end Application-Specific Integrated Circuits (ASICs) to read out mainly
gaseous detectors. The scalability is achieved in a star-like architecture.
The computer system with data acquisition and slow control software can be
connected to several Front-End Concentrator (FEC) cards via Gigabit Ethernet.
Those cards are the same for any front-end ASIC and can be interconnected to
an ASIC specific adapter card by PCI express connectors. The adapter card
connects several front-end boards by HDMI cables and the communication is
based on a specific data protocol.

The system was used in a wide range of applications e.g. [2, 3, 4, 5] mainly
with the APV25 [6] as front-end ASIC. To cope with the requirements of the
latest experiments as e.g. high rate and triggerless readout, a new front-end
ASIC, the VMM [7] was implemented in the SRS recently [8]. Within the next
decade, the SRS with the VMM is expected to enable R&D projects and the
instrumentation of upcoming experiments. The system has left its basic
development phase and the first production runs of VMM front-end cards, called
VMM hybrids, have been completed. There is an increasing number of projects,
within which the VMM hybrid of the RD51 collaboration will be applied. Besides
R&D projects mainly in the domain of gaseous detectors, the board will be used
for detectors at the European Spallation Source [9], the MAGIX experiment [10]
and geographic muon tomography [11], to list only a few.

Due to the increasing hybrid production volumes, which have reached quantities
of about one thousand per year, testing by hand is no longer feasible. Two
automated test systems have been developed. The VMM Testing System (VTC) [12]
is indispensable during the production process and can detect severe defects
like short circuits or faulty component soldering as well as major VMM ASICs
issues. The other system, reported in this manuscript, is meant for a complete
characterisation of the signal path from the connector to the detector up to
the data output connector of the hybrid. It classifies in particular the VMM
ASICs by a large variety of testing procedures and is used to determine the
VMM hybrid production yield. By using the standard SRS readout chain, the
hybrids and their VMM chips can be qualified and re-qualified at any time when
being used for experimental studies.

The VMM ASIC and hybrid are introduced in section 2, followed by an
introduction of the test platform in section 3. Results of automated testing
of the latest hybrid production batches, in particular the yields, are
presented in section 4, followed by the impact of the results and an outlook
in section 5. The conclusion is provided in section 6.

##  2 VMM and VMM hybrid

In the scope of the ATLAS New Small Wheel (NSW) upgrade [13] a new ASIC, the
VMM [14], has been designed. It is used as a readout chip for the Micromegas
[15] and small-strip Thin Gap Chamber (sTGC) [16] detectors of the NSW, which
was installed in the ATLAS experiment during the Long Shutdown 2 of the Large
Hadron Collider at the European Organisation for Nuclear Research. The
implementation in the SRS, however, aims at a general application. The VMM,
designed in $130\text{\,}\mathrm{nm}$ CMOS technology by Brookhaven National
Laboratory, is an analogue to digital ASIC with 64 input channels. It
digitises the charge signals from detectors and outputs arrival time,
amplitude and channel number in a data stream of up to
$800\text{\,}\mathrm{M}\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{/}\mathrm{s}$. In
a single channel, hits with an arrival time difference of less than
$500\text{\,}\mathrm{ns}$ can be separated. The analogue part of the VMM can
be tuned by means of shaper peaking times of $25\text{\,}$, $50\text{\,}$,
$100\text{\,}$ and $200\text{\,}\mathrm{ns}$, preamplifier gains from
$0.5\text{\,}$ to
$16\text{\,}\mathrm{m}\mathrm{V}\mathrm{/}\mathrm{f}\mathrm{C}$ and different
time-to-digital precision. The chip is designed for a detector capacitance
from a few pF up to 3 nF.

After the preamplifier and shaper, the analogue signal is digitised if a
configurable threshold is passed. This threshold is set globally for all
channels. For each individual channel, the threshold can be fine adjusted by a
five-bit trim Digital to Analogue Converter (DAC). For each threshold
crossing, the digital part of the ASIC generates hit information. In order to
not saturate the output bandwidth of the VMM, the threshold has to be set well
above the baseline, such that only very few noise signals cross the threshold.
The baseline level includes noise from the VMM internal circuits, sources on
the Printed Circuit Board (PCB) it is mounted on as well as of the capacitance
connected to the input. A block diagram of a VMM ASIC is shown in figure 1.

Figure 1: Block diagram of a single VMM ASIC [17].

In the case of the VMM-based SRS readout, the front-end board, called hybrid,
see figure 2, holds two VMM ASICs to be compatible and exchangeable with the
128 input channel APV25 SRS hybrid. Data of both VMMs are combined in a Xilinx
Spartan-6 Field Programmable Gate Array (FPGA), which also controls the ASICs
and other components on the board. In the future, the FPGA will be upgraded to
a Spartan-7. The board can be either powered externally or through the HDMI
cables used to connect the hybrid to the SRS back-end. Low Drop Out regulators
(LDOs) on the backside of the hybrid assure a stable power supply. The voltage
drop on those components adds about $1\text{\,}\mathrm{W}$ to the
$2\text{\,}\mathrm{W}$ produced by the two VMM AISCs. For this reason, the
hybrid comes with a cooling kit with convection radiators on the top side. An
image of the VMM hybrid is shown in figure 2.

Figure 2: VMM hybrid, from [18]

The hybrid also holds two Analogue to Digital Converters (ADCs) that can be
read out by the I2C protocol. Each one connects to the Monitoring Output (MO),
see figure 1 of one VMM chip and reads the analogue voltage level provided.
The MO can be programmed to output several VMM internal voltage levels e.g.
DAC value of the threshold, the pedestal for a selected channel or the voltage
level of a VMM internal temperature sensor.

##  3 Test platform setup and test procedure

In order to contribute to the production quality assurance and to provide a
system to characterise VMM hybrids in a standardised, fast and automated way,
a test platform was developed. The platform itself as well as the test
procedure is explained in this chapter.

###  3.1 Test platform hardware setup

A schematic of the test setup is shown in figure 3. The VMM hybrid under test
is connected to the SRS, a JTAG programmer for firmware upload and optionally
to a multiplexer PCB. The latter was specifically developed within this
project. In combination with a remotely controllable signal generator, it
allows the application of external test pulses to individual channels of the
hybrid. Using an optional remote controllable power supply the supply current
and voltages can be monitored. Powering through an HDMI connection directly
from the FEC of the SRS is also possible. All components are connected and
controlled by a PC running the VMM slow control software [19] (see section
3.2). Data between the SRS and the PC are transferred via an Ethernet
connection. Test results are automatically uploaded to a github repository,
where all results are put into a single database file.

Figure 3: Schematic setup of a VMM hybrid testing station.

The power supply, the external test pulse system and the JTAG programmer are
all optional components. A sufficient qualification and classification of the
VMM hybrids can already be achieved using only a PC and the SRS with the
proper adapter card and powering setup.

###  3.2 Test platform software

The VMM hybrid quality test was integrated by extending the VMM slow control
software. Within the Graphical User Interface (GUI) shown in figure 4, all
required settings and the automated test procedures can be selected. It also
displays the test results. The SRS readout chain is used for collecting
information and data about the hybrid. There are two different ways in which
data can be gathered:

  1. 1.

Reading the ADC connected to the VMM MO via I2C (see section 2)

  2. 2.

Evaluating digital VMM hit data as received on the PC (see section 3.1)

Figure 4: Graphical User Interface of the SRS slow control software tab for
the VMM hybrid quality test, example of a hybrid test result. The numbers
indicate the different parts: 1: Setup and test selection, 2: Hybrid status,
3: Temperature and power monitor, 4: VMM status, 5: Test log, 6: Plot window,
7: VMM channel status matrices.

###  3.3 Test procedure

The hybrid to be characterised is connected to the FEC adapter card via HDMI,
the external, remotely controlled power supply (optional), the multiplexer PCB
(optional) and the JTAG programmer (optional). In case no external power
supply is used, the hybrid is powered via the HDMI cable by the adapter card.
Depending on the available setup, different options have to be selected in the
slow control. E.g. in case an external, remotely controlled power supply is
used, the power consumption test can be enabled (Autoread current in figure
4). The physical location or institute the hybrids belongs to also needs to be
entered there. All options can also be set in a configuration file which is
automatically loaded at startup. The software automatically connects to the
SRS and checks if an HDMI connection to a hybrid can be established. If no
HDMI connection is found the software can, in case this option has been
enabled and the JTAG programmer is connected, try to automatically load the
hybrid firmware onto the FPGA and connect again. After reprogramming the FPGA,
the programmer has to be disconnected, as for some VMM hybrids problems would
occur otherwise. Afterwards, the hybrid ID111Only the least significant 64
bits of the 128-bit long hybrid ID, as these already uniquely classify a
certain hybrid is read from the EEPROM on the hybrid via the I2C protocol. A
measurement ID is generated consisting of the hybrid ID and the datetime in
the format yyyyMMddhhmm. Afterwards, the following tests are performed:

  1. 1.

Monitoring ADC Calibration: Increases the global VMM threshold DAC and reads
out the monitoring output MO configured to the threshold via the monitoring
ADC.

  2. 2.

Pedestal and Pedestal Noise: Measures for each channel ten times the baseline
and calculates the average, as well as the fluctuation of the baseline value.

  3. 3.

Threshold: Measures the threshold of every channel

  4. 4.

Threshold Trimability: Checks the functionality of the trimming threshold DAC
for each individual channel

  5. 5.

External Test Pulses: Evaluates the functionality of the channels using
external test pulses

  6. 6.

Internal Test Pulses: Evaluates the functionality of the channels using
internal test pulses

The first four tests in the list are using the monitoring ADC, the two test
pulse tests use the SRS data acquisition chain. For both internal and external
test pulses, there are subtests performed on the recorded data, such as the
number of pulses recorded during the test, as well as the average ADC of all
hits for each channel. Together with the pedestal, these are defined as
critical tests.

After each test is completed, test specific quality criteria are evaluated for
each channel222Except for the monitoring ADC Calibration, as this measurement
is not channel but VMM specific.. E.g. for the pedestal test, the average
pedestal is checked to agree with the range of defined good and ok intervals.
According to these criteria each channel is given an error score of either 0,
1 or 2 where 0 is given for good channels (pedestal value inside in the good
interval), 1 for ok channels (pedestal value is outside the good interval, but
within the ok interval) and 2 for bad channels (pedestal value is outside the
ok interval).

After all tests are finished, channels are classified as broken if they
received an error score of 2 in one of the critical tests (see above). If the
channels receive an error score of 2 or 1 in any other test, they are
classified as ok, otherwise as good.

It should be noted, that if the Monitoring ADC Calibration test fails for a
VMM, the whole VMM is classified as bad, as in this case, no monitoring is
possible. As during the production the hybrids are tested with the VTC, which
filters out VMM with these problems, this problem should not occur.

Testing a single hybrid with all optional tests takes about two minutes. The
data is automatically stored in the database.

##  4 Results

###  4.1 VMM and hybrid classification

Depending on the total number of broken channels, the VMMs and hybrids are
classified according to the classification as outlined in tables 1 and 2.
Instead of a simple “working/broken” classification scheme, this slightly more
detailed classification was chosen to allow to place hybrids of not perfect
quality in less critical areas of a detector or use them for test purposes.
The classification also accounts for the variety of problems which may occur
on a hybrid.

VMM Class | Number of broken Channels
---|---
A | 0
B | 1
C | 2-3
D | 4-32
E |  $>$32
Table 1: Classification table for the single VMM ASICs on a hybrid. Hybrid class |  VMM 1 class |  VMM 2 class |  Total Number of broken Channels
---|---|---|---
a | A | A | 0
b | A/B | B/C/B | 1-3
c | A/B/C/D | D/E | 4-61
c | B/C | C | 4-61
d | A/B/C/D/E | E | $>$61
Table 2: Classification for a VMM hybrid.

###  4.2 Pedestal problem

A known error of the VMM3a can result in a malfunction of channels, which
manifests in a high level of the channel baseline (pedestal) [14]. The
baseline level settles down too slow after configuration and can last for a
few $\text{\,}\mathrm{ms}$. Identification is only possible if the pedestal is
measured rapidly after changing the channel settings. The problem is more
prominent at high preamplifier gains and can be circumvented by setting the
configuration bits stlc or sbip, where the latter is recommended as it has a
larger effect. The default configuration has sbip enabled. However, it was
observed during the testing that some VMM chips still have channels with high
baselines at high gains down to
$6\text{\,}\mathrm{mV}\text{\,}{\mathrm{fC}}^{-1}$. For a gain of
$3\text{\,}\mathrm{mV}\text{\,}{\mathrm{fC}}^{-1}$, the baseline of all
channels on all those chips showed a normal behaviour. Depending on the
application’s needs, those chips can be applied the same way as chips without
this behaviour. However, a pedestal problem at high gains despite the enabling
of sbip could indicate a general chip issue. It was decided to introduce a
dedicated marking for this behaviour. A ”-” sign is added to the VMM and
hybrid class, indicating the pedestal problem (e.g. VMM Class ”A” becomes
”A-”). This requires to measure the pedestals at two different gains, once at
$3\text{\,}\mathrm{mV}\text{\,}{\mathrm{fC}}^{-1}$ and once at
$16\text{\,}\mathrm{mV}\text{\,}{\mathrm{fC}}^{-1}$. Figure 5 shows the result
of a pedestal measurement at the highest gain for a hybrid, on which one of
the two VMM chips (VMM1, red curve) has the pedestal problem.

Figure 5: Example of for pedestal problem: Some VMM 1 (red) channels have a
high baseline level, when the highest gain is used. VMM 0 shows a typical
baseline at about $160\text{\,}\mathrm{mV}$ for comparison.

###  4.3 Production yields

A total of 176 hybrids, of which 42 were produced in 06/2020 (batch 1) and 134
in 02/2021 (batch 2), were tested with the test system presented in this work.
Using a database browser, the results of all tested hybrids can be evaluated.
The tool offers a variety of filtering options, e.g. for the location the test
was performed. For each hybrid, the full history of tests is accessible. The
VMM and hybrid class distributions for both production batches are shown in
figures 6 and 7. The numbers above the histogram bars indicate the percentage
of VMMs or hybrids in the respective class including those with pedestal
problems (white box) and excluding those with pedestal problems (green). The
yellow bars and numbers indicate the percentage of hybrids with pedestal
problems.

Figure 6: VMM and hybrid class distribution of 42 hybrids from production
batch 1 (06/2020)

Figure 7: VMM and hybrid class distribution of 134 hybrids from production
batch 2 (02/2021)

For the single VMM chip class A,B and C are considered to be acceptable (up to
three not perfect channels per chip) and the sum of these classes make up the
total yield. For the hybrids class a and b are acceptable (up to three not
perfect channels per hybrid). With this the yields are determined to be for
the 06/2020 production:

$\displaystyle Y_{\text{VMM}}$ $\displaystyle=$97.6\text{\,}\mathrm{\char
37\relax}$$ $\displaystyle Y_{\text{Hybrid}}=$95.2\text{\,}\mathrm{\char
37\relax}$$

and for the 02/2021 production

$\displaystyle Y_{\text{VMM}}$ $\displaystyle=$93.6\text{\,}\mathrm{\char
37\relax}$$ $\displaystyle Y_{\text{Hybrid}}=$88.0\text{\,}\mathrm{\char
37\relax}$$

If the pedestal problem would not be treated separately and all chips with
these issues were rated as class E, the yields would drop e.g. for the batch 2
hybrids to $77.4\text{\,}\mathrm{\char 37\relax}$.

##  5 Impact and outlook

Comparing both production batches, some differences in the class distributions
can be observed. However, due to the low number of chips in batch 1, they are
statistically not significant assuming a random hybrid selection and
$\sqrt{N}$ errors. A reason why the yields in batch 1 are better compared to
those in batch 2 could be the lower number of hybrids and the fact that for
the first production, every single hybrid was taken care of manually, which
has to be automatised for larger productions.

An option to increase the yield would be to test all VMM chips already on the
wafer and only use good chips for production, as was done for the ATLAS NSW
project. However, this system only monitors the analogue behaviour of the chip
and therefore would not detect all issues. The effort and cost to develop,
maintain and operate such a system was elaborated by some developers in the
RD51 Collaboration electronics group. Considering all these additional
efforts, a limit for the hybrid yield of $85\text{\,}\mathrm{\char 37\relax}$
was deduced, below which the strategy of wafer testing would have been
beneficial. Based on the results of this study, wafer testing is not
necessary.

With the automated testing system as described in this manuscript, several
modes of failure for the VMM ASIC were found. Not all of those could be
detected by the first VTC version during production. As a result, the VTC was
further developed to detect e.g. problems with the VMM ADC, which primarily
contributes to the E classification of chips without pedestal problems. It was
decided to use the improved VTC during several steps of production to replace
VMM chips with defects. With these improvements, a production yield of
$95\text{\,}\mathrm{\char 37\relax}$ for the hybrids should be achievable.

##  6 Conclusion

An automated testing system for the RD51 VMM hybrid was developed. It uses the
standard SRS readout chain for the principle tests to qualify the hybrids.
Optional extensions allow for additional tests e.g. on the power consumption
or connectivity to a detector. The system is implemented in the VMM slow
control and allows simple testing with graphical support. Test results are
uploaded to a general database. Based on measurements on the first two VMM
hybrid production batches, the respective yields have been measured. From the
first production batch of 06/2020, $95.2\text{\,}\mathrm{\char 37\relax}$ of
the hybrid were rated acceptable (class a and b, see section 4.3). For the
second production batch, $88.0\text{\,}\mathrm{\char 37\relax}$ of the hybrids
were rate acceptable. With these results, an ASIC testing on the wafer, for
which a yield below $85\text{\,}\mathrm{\char 37\relax}$ was considered worth
the additional efforts by the RD51 Collaboration, was discarded. Taking into
account a pedestal problem only occurring for high VMM internal preamplifier
gains, the yield would drop to $77.4\text{\,}\mathrm{\char 37\relax}$ for the
second production. A detailed analysis of the VMM failures lead to improved
testing during the production with another testing system. It is expected that
the yield of future productions will further increase.

##  7 Acknowledgements

We would like to thank SRS Technology and the RD51 community, especially the
Working Group 5.1 members, for the fruitful discussions. We also recognise the
assistance by Stefano Caiazza and Pepe Gülker from Mainz University and
Ignacio Lázaro Roche from the LSBB for allowing us to test their hybrids to
increase statistics. We would like to acknowledge the assistance by Dorothea
Pfeiffer in answering questions on the VMM and developing human experience-
based quality criteria. Parts of this work have received funding from the
European Union’s Horizon 2020 research and innovation programme under the
Marie Sklodowska-Curie grant agreement no. 846674 as well as from the German
Federal Ministry of Education and Research under grant no. 05K19PD1 and no.
13E18CHA (Wolfgang Gentner Programme).

## References

  * [1] S. Martoiu, H. Muller, A. Tarazona, J. Toledo, Development of the scalable readout system for micro-pattern gas detectors and other applications, Journal of Instrumentation 8 (03) (2013) C03015.
URL http://stacks.iop.org/1748-0221/8/i=03/a=C03015

  * [2] K. Gnanvo, B. Benson, W. Bittner, F. Costa, L. Grasso, M. Hohlmann, J. B. Locke, S. Martoiu, H. Muller, M. Staib, A. Tarazona, J. Toledo, Detection and imaging of high-z materials with a muon tomography station using gem detectors, in: IEEE Nuclear Science Symposuim Medical Imaging Conference, 2010, pp. 552–559.  doi:10.1109/NSSMIC.2010.5873822.
  * [3] M. Alexeev, R. Birsa, F. Bradamante, A. Bressan, M. Chiosso, P. Ciliberti, S. Dalla Torre, S. Dasgupta, O. Denisov, M. Finger, et al., Status of COMPASS RICH-1 upgrade with MPGD-based photon detectors, in: EPJ Web of Conferences, Vol. 174, EDP Sciences, 2018, p. 01004.  doi:https://doi.org/10.1051/epjconf/201817401004.
  * [4] B. Brickwedde, A. Düdder, M. Schott, E. Yildirim, Design, construction and performance tests of a prototype micromegas chamber with two readout planes in a common gas volume, Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 864 (2017) 1 – 6.  doi:https://doi.org/10.1016/j.nima.2017.04.010.
URL http://www.sciencedirect.com/science/article/pii/S0168900217304448

  * [5] R. Venditti, Characterization of triple-gem detectors for the phase i muon system upgrade of the cms experiment at lhc, in: 2017 7th IEEE International Workshop on Advances in Sensors and Interfaces (IWASI), 2017, pp. 95–100.  doi:10.1109/IWASI.2017.7974225.
  * [6] M. Raymond, et al., The CMS tracker 0.25 $\mu m$ CMOS readout chip, in: CERN CDS, 2000, p. 5.
URL http://cds.cern.ch/record/478270/files/raymond.pdf

  * [7] G. D. Geronimo, J. Fried, S. Li, J. Metcalfe, N. Nambiar, E. Vernon, V. Polychronakos, VMM1 - An ASIC for micropattern detectors, in: 2012 IEEE Nuclear Science Symposium and Medical Imaging Conference Record (NSS/MIC), 2012, pp. 633–639.  doi:10.1109/NSSMIC.2012.6551184.
  * [8] M. Lupberger, L. Bartels, F. Brunbauer, M. Guth, S. Martoiu, H. Müller, E. Oliveri, D. Pfeiffer, L. Ropelewski, A. Rusu, P. Thuiner, Implementation of the vmm asic in the scalable readout system, Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 903 (2018) 91 – 98.  doi:https://doi.org/10.1016/j.nima.2018.06.046.
URL http://www.sciencedirect.com/science/article/pii/S016890021830768X

  * [9] M. Lindroos, S. Bousson, R. Calaga, H. Danared, G. Devanz, R. Duperrier, J. Eguia, M. Eshraqi, S. Gammino, H. Hahn, et al., The European spallation source, Nuclear Instruments and Methods in Physics Research Section B: Beam Interactions with Materials and Atoms 269 (24) (2011) 3258–3260.
  * [10] S. Aulenbacher, Design and Simulation of the Internal Gas-Target for MAGIX, Diploma thesis, Johannes Gutenberg-Universität Mainz, Mainz Germany (2014).
  * [11] I. Lázaro, F. Hivert, J.-B. Decitre, R. D. Oliveira, O. Pizzirusso, H. Muller, F. Jeanneau, I. Giomataris, S. Gaffet, Muon telescope based on micromegas detectors: From design to data acquisition, E3S Web of Conferences 4 (2014) 01002.  doi:10.1051/e3sconf/20140401002.
URL https://doi.org/10.1051/e3sconf/20140401002

  * [12] M. Hracek, H. Muller, S. Popescu, VTC test - software demo, in: Presentation given at the RD51 Collaboration Meeting at CERN, 2020, p. 13.
URL https://indico.cern.ch/event/911950/timetable/#20200622.detailed

  * [13] T. Kawamoto, S. Vlachos, L. Pontecorvo, J. Dubbert, G. Mikenberg, P. Iengo, C. Dallapiccola, C. Amelung, L. Levinson, R. Richter, D. Lellouch, New Small Wheel Technical Design Report, Tech. Rep. CERN-LHCC-2013-006. ATLAS-TDR-020, ATLAS, aTLAS New Small Wheel Technical Design Report (Jun 2013).
URL https://cds.cern.ch/record/1552862

  * [14] G. de Geronimo, G. Iakovidis, S. Martoiu, V. Polychronakos, The vmm3a asic, IEEE Transactions on Nuclear Science 69 (4) (2022) 976–985.  doi:10.1109/TNS.2022.3155818.
  * [15] Y. Giomataris, P. Rebourgeard, J. Robert, G. Charpak, Micromegas: a high-granularity position-sensitive gaseous detector for high particle-flux environments, Nuclear Instruments and Methods in Physics Research Section A 376 (1) (1996) 29 – 35.  doi:10.1016/0168-9002(96)00175-1.
URL http://www.sciencedirect.com/science/article/pii/0168900296001751

  * [16] E. Perez Codina, Small-strip Thin Gap Chambers for the muon spectrometer upgrade of the ATLAS experiment, Nucl. Instrum. Meth. A824 (2016) 559–561.  doi:10.1016/j.nima.2015.11.095.
  * [17] V. Polychronakos, G. Iakovidis, G. D. Geronimo, ATLAS NSW Electronics Specifications, Component: VMM, ATLAS internal document (2017).
  * [18] F. Jaekel, Development of an automated quality control test system for the vmm hybrid, Master thesis, Mathematisch-Naturwissenschaftlichen Fakultät der Rheinischen-Friedrich-Wilhelms–Universität Bonn, Bonn Germany (2021).
  * [19] M. Guth, SOFTWARE Manual for VMM3 Slow Control, Tech. rep., CERN, repository at https://gitlab.cern.ch/rd51-slow-control/vmmsc (2017).
URL https://gitlab.cern.ch/rd51-slow-
control/vmmsc/-/raw/main/VMM3_Slow_Control_Software_Guide-2.pdf