Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization
Authors: Minsu Kim
Junyoung Park
Jinkyoo Park
Venue: NeurIPS 2022 Accept (2022)
Keywords: Symmetricity
Equivariant
Combinatorial Optimization
Reinforcement Learning

Abstract: Deep reinforcement learning (DRL)-based combinatorial optimization (CO) methods (i.e., DRL-NCO) have shown significant merit over the conventional CO solvers as DRL-NCO is capable of learning CO solvers less relying on problem-specific expert domain knowledge (heuristic method) and supervised labeled data (supervised learning method). This paper presents a novel training scheme, Sym-NCO, which is a regularizer-based training scheme that leverages universal symmetricities in various CO problems and solutions. Leveraging symmetricities such as rotational and reflectional invariance can greatly improve the generalization capability of DRL-NCO because it allows the learned solver to exploit the commonly shared symmetricities in the same CO problem class. Our experimental results verify that our Sym-NCO greatly improves the performance of DRL-NCO methods in four CO tasks, including the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize collecting TSP (PCTSP), and orienteering problem (OP), without utilizing problem-specific expert domain knowledge. Remarkably, Sym-NCO outperformed not only the existing DRL-NCO methods but also a competitive conventional solver, the iterative local search (ILS), in PCTSP at 240$\times$ faster speed. Our source code is available at https://github.com/alstn12088/Sym-NCO. 

Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization
Minsu Kim
Junyoung Park
Jinkyoo Park
Korea Advanced Institute of Science and Technology (KAIST)
Dept. Industrial & Systems Engineering
{min-su, Junyoungpark, jinkyoo parkkOkaist. ac..astttc.... ac.kr
Abstract
Deep reinforcement learning (DRL)-based combinatorial optimization (CO) meth- ods (i.e., DRL-NCO) have shown significant merit over the conventional CO solvers DRL-NCO is capable of learning CO solvers less relying on problem-specific ex- pert domain knowledge (heuristic method) and supervised labeled data (supervised learning method). This paper presents novel training scheme, Sym-NCO, which is a regularizer-based training scheme that leverages universal symmetricities various CO problems and solutions. Leveraging symmetricities such rotational and reflectional invariance can greatly improve the generalization capability of DRL-NCO because it allows the learned solver exploit the commonly shared symmetricities in the same CO problem class. Our experimental results verify that our Sym-NCO greatly improves the performance of DRL-NCO methods four CO tasks, including the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize collecting TSP (PCTSP), and orienteering problem (OP), without utilizing problem -obecfi- expert domain knowledge. Remarkably, Sym- NCO outperformed not only the existing DRL-NCO methods also competitive conventional solver, the iterative local search (ILSS, in PCTSP at x40x faster speed. Our source code available https : //gi thub. com/ aalstalstnnnn 1208/ SSeesSSymmnat NCO.
Introduction
Combinatorial optimization problems (COPs), mathematical optimization problems on discrete input space, have been used to solve numerous valuable applications, including vehicle routing problems (VRPs) [1, 2], drug discovery [3, 4], and semi-conductor design [5, 6, 7, 9]. However, finding an optimal solution to COP is difficult due to its NP-hardness. Therefore, computing near-optimal solutions fast essential from a practical point of view.
Conventionally, COPs are solved by integer program (IP) solvers or hand-crafted (meta) heuris- tics. Recent advances computing infrastructures and deep learning have conceived the field of neural combinatorial optimization (NCO), a deep learning-basee pending on the training scheme, NCO methods are generally classified into supervised learning
COP solving strategy. De-
[10, 11, 12, 13, 14] and reinforcement learning (RL) [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]. Depending on the solution generation scheme, NCO methods are also classified into improve- ment [17, 16, 15, 28, 18, 19, 25] and constructive heuristics [20, 21, 22, 23, 24, 26, 27]. Among the NCO approaches, deep RL (DRL)-based constructive heuristics (i.e.. DRL-NCO) are favored over conventional approaches for two major reasons. First, RL can be applied to train the NCO model in less explorered CO tasks because training RI. does not require domain expert knowl- edge and supervised labels from verified solver. Second, it is easy to produce qualified feasi- ble solutions because the constructive process can easily avoid constraint-violatee actions [21]. Despite the strength of DRL-NCO, there exists performance gap between the state-of-the-art
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(x)
(x(x)
W [12233445]
[2.34111]
n = (5.1231
Inibal Visited
(a) Problem symmetricity
(b) Solution symmetricity
Figure 2: Illustration of symmetricities in CO (exampled in TSP)
conventional heuristics and DRL-NCO. In an effort close the gap, there have been attempts to employ problem-specific heuristics to existing DRL-NCO methods [23, 29]. However, devising a general training scheme improve the performance of DRL-NCO still remains challenging.
In this study, we propose the Symmetric Neural Combinatorial Optimization (Sym-NCO), gen- eral training scheme applicable to universal CO problems. Sym-NCO a regularization based training scheme that leverages the symmetrici- ties commonly found in COPs to increase the performance of existing DRL-NCO methods, Sym-NCO leverages two types of symmetrici-- ties innate in COP that are defined on the Eu- clidean graph. First, the problem symmetricity is derived from the rotational invariance of the solution; the rotated graph must exhibit the same optimal solution the original graph shown in Fig. 2a. Second, the solution symmetricity refers to the property that solutions have identi- cal output values (See Fig. 2b).
Symmetric Space
Optimal Parameter
Previous DRL-NCO
Sym-Nco
Figure 1: Illustration that describes advantage of Sym-NCO. An optimal training parameter is in symmetric space. Sym-NCO makes more compact training space compared with previous DRL-NCO and supports the NCO model efficiently converges in near-optimal parameters.
To train effective NCO solver while lever- aging the symmetricities, we employ REIN- FORCE algorithm with the baselines terms spe- cially designed to impart solution and problem symmetricities. REINFORCE algorithm is used because the well-knowe effective NCO solvers are trained by REINFORCE; thus, we can improve such solvers by just modifying their baseline with symmetricity-conse considered baseline terms. Specifically, we sample multiple solutions from the transformed problems and use the average return of them. Then, REINFORCE pushes each solution sampled by the solver excel this baseline during training, thus improving the policy and making all the solutions the same, i.e., the problem and solution symmetricities are realized.
Motivation for learning symmetricity. Leveraging symmetricity is important to train CO models for two major reasons. Firstly, symmetricity is strong inductive bias that support the training process of DRL by making compact training space as shown in Fig. 1. Secondly, learning symmetricity is beneficial to inereasing generalization capability for unseen CO problems because symmetricity induces the invariant representation that every COP contains.
Novelty. The major novelty of the proposed learning strategy is that it can easily improve existing powerful CO models; existing equivariant neural network schemes must re-designed at the architecture level for adapting to CO.
2 Symmetricity in Combinatorial Optimization Markov Decision Process
This section presents several symmetric characteristics found in combinatorial optimization, which is formulated in the Markov decision process. The objective of NCO is to train the 0-parameterized solver Fø by solving the following problem:
0" arg max Ep~p ( [E) [ [R[T;
where P (z, is problem instance with the N node coordinates L and corresponding N features f M. The is problem generating distribution. The π Fi is solution

---

where each element is index value R; {1, }} for coordinates = (2 The R(TT; P) is objective value for π on problem P.
For example, assume that we solve TSP with five cities (i.e. N
5). Then the problem instance {x,);= ]==1 where the salesman must visit. The solution is
P contains five city coordinates sequence of city indices; if π = (1,3, 2, 5, 4), the salesman visits city coordinates as æ1 + + 22 + 25 + 24 - 21 (the salesman must go back first visited city complete a tour). In TSP, each city contains the homogeneous features f. Thus, objective Rt of the TSP is defined as the negative of tour length: R(T; P) = (EEn
In, + I| - Iz Il). This combinatorial decision process can be expressed as Markov decision process, and the solver (TT P) can be expressed instance conditioned policy. To this end, we can utilize deep reinforcement learning for training solver FO TT| P). We formally define the Markov decision process for CO in the below chapter.
2.1 Combinatorial optimization Markov decision process
We define the combinatorial optimization Markov decision process (CO-MDP) as the sequential construction of a solution of COP. For a given P, the components of the corresponding CO-MDP are defined as follows:
State. The state 8, (an:r, æ, f) is the t-th (partially complete) solution, where ai represents the previously selected nodes. The initial and terminal states 8o and 8T are equivalent to the empty and completed solution, respectively. In this paper, we denote the solution (PP) as the completed solution.
Action, The action a, is the selection of node from the un-visited nodes (i.e., at E A. {f1,.., N} {a1=-1)1).
Reward. The reward function R(T;; P) maps the objective value from given æ of problem We assume that the reward is function of a1.7 (solution sequences), ||=; (jl...)e(1.....)) (relative distances) and f (nodes features). In TSP, capacitated VRP (CVRP), and prize collecting TSPs (PCTSP), the reward is the negative of the tour length. In orienteering problem (OP), the reward is the sum of the prizes.
Having defined CO-MDP, define the solution mapping as follows: where (4g 52) is the policy that produces at 8t, and T is the maximum number of states in the solution construction process.
Po(-P) -I" po pa 8x)
2.2 Symmetricities in CO-MDP
Symmetricities are found in various COPs. We conjecture that imposing those symmetricities on Fş improves the generalization and sample efficiency of Fg. We define the two identified symmetricities that are commonly found in various COPs:
Definition 2.1 (Problem Symmetricity). Problem P and pl are problem symmetric (Pi if their optimal solution sets identical.
sym
PJ)
Definition 2.2 (Solution Symmetricity). Two solutions T' and π are solution symmetric (T² A T²) on problem P if R(T'; P) = P).
An exemplary problem symmetricity found in various COPs is the rotational symmetricity: Theorem 2.1 (Rotational symmetricity). For any orthogoanl matrix Q, the problem P and Q(P) &
(1 f} are problem symmetric: i.e., P sym Q()). See Appendix A for the proof.
Rotational problem symmetricity is identified in every Euclidean COPs. On the other hand, solution symmetricity cannot be identified easily as the properties of the solutions are distinct for every COP.
Symmetric Neural Combinatorial Optimization
This section presents Sym-NCO, an effective training scheme that leverages the symmetricities of COPs. Sym-NCO learns solve Fg by minimizing the total loss function:
Liotal = Lsym-RL + aLiv Lps + BLss + a aLinv
(2)
3

---

Solution Symmctricty
Prebian
Encoder
Decader
Symmericlty.
R(2(0))
#(KO))
Mesimize Simileriyy Eave
(((Q0)))
Projection Heed
Figure 3: An overview of Sym-NCO
where LI is REINFORCE loss term supported by symmetricity and Lim the regularization loss to induce that invariant representation. The Lsym-RL is composed with Ls. the REINFORCE loss term of Eq. (1) with solution symmetricity regularizing mechanism, and Cps. the REINFORCE loss term of Eq. (1) with both solution and problem symmetricity regularization. 8 E [0, 1] are the weight coefficients. In the following subsections, we explain each loss detail.
3.1 Regularizing REINFORCE with problem and solution symmetricities via Lsym-RL.
As discussed in Section 2.2, COPs have problem and solution symmetricities. We explain how to learn solver I's using REINFORCE with the specially designed baseline to approximately impose symmetricities. We provide the policy gradients to Lus (P)) and Lps (T(P) in the context of the REINFORCE algorithm [30] with the proposed baseline schemes.
Leveraging solution symmetricity. As defined in Definition 2.2, the symmetric solutions must have the same objective values. We propose the REINFORCE loss Las with the baseline specially designed to exploit the solution symmetricity CO as follows:
Ls - EE Fol (PP)
R(TT; P)]
(3)
VoLus - Fol-
[R((T; P) b(P)) Vo log log
K
[R(T* P)
Σ
R(T
P)] V log Fà
(5)
K
K
where [ =k=1 are the solutions of P sampled from Fo(T P), log Fo is the log-likelihood of Fo. K
the number of sampled solutions, b( P)) is shared baseline which is the average reward from K solutions for the identical problem P.
The Las approximately imposes solution symmetricity using REINFORCE algorithm with novel baseline b(P). The sum of advantage in the solution group {x * #1
jk=1 is always zero:
K
K R(T
R n P
P)] =0
(6)
K
K
The Los induces competition among the rewards, R(T P),.., R(T P) which can be seen as zero-sum game. Therefore, Lu improves the overall reward quality of the solution group using the proposed competitive REINFORCE scheme, making the solver generate high-rewarded solutions but small reward deviation between solutions. The small reward-deviation indicates Lss approximately imposes solution symmetricity to solver Fe.
The POMO [23] employed similar training technique with our C... that finds symmetric solutions by forcing Fg to visit all possible initial cities when solving TSP and CVRP. However, the reward of COPs, including CVRP, PCTSP, and OP, is usually sensitive to first-city selection. Therefore, POMO can be an excellent standalone method for TSP but can be further improved using our C,, loss term in other tasks including CVRP.
Leveraging problem symmetricity. discussed in Section 2.2, the rotational problem symmetricity common in various COPs. We propose the REINFORCE loss Cps which is equipped with problem

---

symmetricity:
Cps = -E [[(T; P)] P)]
(7)
V Lps = -IQiin
E B
[[(T; P) -(P V log Po
(8)
1
K
R(T 1R P)
: Vo log
P)
LK
L.
where Q is the distribution of random orthogonal matrices, Q' is the 7th sampled rotation matrix, and 1. is the hthh sample solution of the t rotated problem. We construct L problem symmetric problems, (P). ..., (P), by using the sampled rotation matrices, and smaple K symmetric solutions from each of the L problems. Then, the shared baseline b(P, Q) is constructed by averaging K solutions.
Similar to the regularization scheme of Las the advantage term of Cps also induces competition between solutions sampled from rotationally symmetric problems. Since the rotational symmetricity defined such that x and Qr(z) have the same solution, the negative advantage value forces the solver to find better solution. As mentioned in Section 2.2, problem symmetricity in COPs is usually pre-identified (i.e. there provable guaranteed symmetricity such as rotational symmetricity Theorem 2); pps are applicable to general COPs. Moreover, multiple solutions are sampled for each symmetric problem so that Cps can also identify and exploit the solution symmetricity with similar approach taken for Lax. We provide detailed implementation and design guides regarding the integration strategy of Las and Cps in Appendix C.2.
3.2 Learning invariant representation with Pre-identified Symmetricity: Liwv-
By Theorem 2.1, the original problem x and its rotated problem Q(x) have identical solutions. Therefore the encoder F& can be enforced to have invariant representation by leveraging the pre-identified symmetricity: rotation symmetricity.
denote h(()) and h (Q(x)) as the hidden representations of x and Q(x), respectively. To impose the rotational invariant property on h(x), we train solver Fe with an additional regularization loss term Linv defined as:
Soos (s(M(s)).
Lim
(10)
where Scos (a, b) the cosine similarity between a and g is the MLP-parameterrized projection head.
For learning the invariant representation on rotational symmetricity, we penalize the difference between the projected representation g(h(z)) and g(h(Q(z))), instead of directly penalizing the difference between h(z) and h(Q())). This penalizing scheme allows the use of arbitrary encoder network architecture while maintaining the diversity [31]. We empirically verified that this approach attains stronger solvers described in Section 6.1.
4 Related Works
Deep construction heuristics. Bello et al. [20] propose one of the earliest DRL-NCO methods, based on pointer network (PointerNet) [10], and trained it with an actor-critic method. Attention model (AM) [21] successfully extends [20] by swapping PointerNet with Transformer [32], and it is currently the de-facto standard method for NCO. Notably, AM verifies its problem agnosticism by solving several classical routing problems and their practical extensions [7, 19]. The multi-decoder AM (MDAM) [26] extends AM by employing an ensemble of decoders. However, such an extension is inapplicable for stochastic routing problems. The policy optimization for multiple optimal (POMO) [23] extends AM by exploiting the solution symmetricities in TSP and CVRP. Even though POMO shows significant improvements from AM, it relies problem-specific solution symmetricities for TSP. Our method can seen as general-purpon symmetric learning scheme, extended from POMO, which can be applied in more general CO tasks.
5

---

Equivariant deep learning. In deep learning, symmetricities are often enforced by employing spe- cific network architectures. Niu et al. [33] proposes a permutation equivariant graph neural network (GNN) that produces equivariant outputs to the input order permutations. The
[34] restricts the Transformer so that is equivariant to (F)(3 group input transformation. Similarly, equivariant GNN (EGNN) [35] proposes GNN architecture that produces ((n) group equivariant output. These network architectures can dramatically reduce the search space of the model parameters. Some research applies equivariant neural networks to RL tasks to improve sample efficiency [36]. Also, there are several works that exploited the symmetric nature of CO. Ouyang et al. [37] proposed equivariant encoding scheme by giving rule-based input transformation to input graph. Hudson et al. [38] suggested a line- line-graph embedding scheme, which is beneficial to process CO graphs with rotational equivariant. Our Sym-NCO is regularization method that is capable of learning existing powerful CO models without giving rule-based hard constraints to the structure. We empirically study the benefit of Sym-NCO over other symmetricity-basee approaches in Section 6.1 and Appendix D.5.
Experiments
This section provides the experimental results of Sym-NCO for TSP, CVRP, PCTSP, and OP. Focusing on the fact that Sym-NCO can be applied to any encoder-decooder-base NCO method, we implement Sym-NCO on top of POMO [23] to solve TSP and CVRP, and AM [21] to solve PCTSP and OP, respectively. We additionally validate the effectiveness of Sym-NCO on PointerNet [10] at TSP (N 100).
5.1 Tasks and baseline selections
TSP aims to find the Hamiltonian cycle with a minimum tour length. We employ Concorde [39] and LKH-3 [40] the non-learnable baselines, and PointerNet [10], the structured-to- teetor deep- Q-network (S2V-DQN) [41], AM [21], POMO [23] and MDAM [26] as the neural constructive baselines.
CVRP is an extension TSP that aims to find a set of tours with minimal total tour lengths while satisfying the capacity limits of the vehicles. We employ LKH-3 [40] as the non-learnable baselines, and Nazari et al. [22], AM [21], POMO [23] and MDAM [26] as the constructive neural baselines.
PCTSP is variant of TSP that aims to find tour with minimal tour length while satisfying the prize constraints. We employ the iterative local search (ILS) [21] as the non-learnable baseline, and AM [21] and MDAM [26] as the constructive neural baselines.
OP a variant of TSP that aims to find the tour with maximal total prizes while satisfying the tour length constraint. We employ compass [42] as the non-learnable baseline, and AM [21] and MDAM [26] as the constructive neural baselines.
5.2 Experimental setting
Problem size. We provide the results of problems with N = 100 for the four problem classes, and real-world TSP problems with 50 N < 250 from TSPLIB.
Hyperparameters. We apply Sym-NCO to POMO, AM, and PointerNet. To make fair comparisons, we use the same network architectures and training-relate hyperparameters from their original papers to train their Sym-NCOOaugmennte models. Please refer to Appendix Appendix C. for more details.
Dataset and Computing Resources. We use the benchmark dataset [21] to evaluate the perfor- mance of the solvers. To train the neural solvers, use Nvidia A100 GPU, To evaluate the inference speed, we use an Intel Xeon E5-2630 CPU and Nvidia RTX2080Ti GPU to make fair comparisons with the existing methods proposed in [26].
5.3 Performance metrics
This section provides detailed performance metrics:
Average cost. We report average cost of 10,000 benchmark instances which is proposed by [21].

---

Table Performance evaluation results for TSP and CVRP. Bold represents the best performances in each task. indicates that the solver does not support the problem. 's' indicates multi-start sampling, 'bs' indicates the beam search. "x for the MDAM indicates the decoder ensemble.
TSP (N 100)
CVRP (N 100)
Method
Cost
Gap
Time
Cost
Gap
Time
Handcrafted Hewristic-baxee based Classical Methods
Concorde
Heuristic [39]
7.76
0.00%%
3m 21m
LKH3
Heuristic [40]
7.76
0.00%
15.65
0.00%
13h
RL-baased Deep Constructive Heuristic methods with greedy rollout
PointerNet (greedy.)
NIPS' 5 [10. 20]
8.60
6.90
S2V-DQN (greedy.)
N7PS'17 [41]
8.31
7.03
RL {greedy.)
NeurIPS 18 [22]
17.23
10.12%
AM (greedy.)
ICLR [21]
8.12
4,53%
2s
16.80
7.34%
38
MDAM Igreddy, x 5)
AA [25]
7.93
2.19%
368
16.40
4.86%
458
POMO [greedy.)
NeurIPS '0 [23]
1.04%
16.26
3.93%
38
Sym-NCO {greedy.}
This work
7.84
0.94%
2s
16.10
2.88%
38
Rl.-based Deep Constructive Heuristic methods with multi-start rollout
Nazari al. {bs.
NeurlPS 18 [22]
16.96
8.39%
AM {2.)) POMO {s. 100)
ICLR'T [21]
7.94
2.26%
41m
16.23
3.72%
54m
NeurlPS [23]
7.80
0.44%
138
15.90
1.67%
16s
MDAM [bs. 30
AAAI'21 [25]
7.80
0.48%
20m
16.03
2.49%
1h
Sym-NCO {s.100}
This work
7.79
0.39%
13s
15.87
1.46%
16s
Table 2: Performance evaluation results for PCTSP and OP. Notations are the same with Table
PCTSP (N 100)
OP (N 100)
Method
Cost
Gap
Time
Obj f
Gap
Time
Handcrafted Heuristic-based Clossical Methods
ILS C++
Heuristic [21]
5.98
0.00%
12h
Compass
Heuristic [42]
33.19
0.00%
15m
RL-based Deep Constructive Heuristic methods with greedy rollout shot inference)
AM (greedy.) MDAM Agreedy.x 5)
ICLR' 19 [21] AAAI'21 [25]
6,25
4.46%
2s
31.62
4.75%
2s
6.17
3.13%
34s
32.32
2.61%
32s
Sym-NCO (greedy.)
This work
6.05
1.23%
2s
32.51
2.03%
2s
RL-based Deep Constructive Heuristic methods with multi-start rollout (Post-processing)
AM (s. 1280)
ICLR'19 19 [21]
6.08
1.67%
27m
32.68
1.55%
25m
MDAM [bs. 30x 5)
AAAI'21 [25]
6.07
1.46%
16m
32.91
0.84%
14m
Sym-NCO (s. 200)
This work
5.98
-0.02%
3m
33.04
0.45%
3m
Evaluation speed. We report the evaluation speeds of solvers in a out-of-the-box manner as they are used in practice. In that regard, the execution time of non-neural and neural methods measured on CPU and GPU, respectively.
Greedy/Multi-starr performance. For neural solvers, it is common practice to measure multi-start performance as final performance. However, when those are employed in practice, such resource consuming multi-start may not be possible. Hence, we discuss greedy and multi-start separately.
5.4 Experimental results
Results of TSP and CVRP. As shown in Table 1, Sym-NCO outperforms the NCO baselines in both the greedy rollout and multi-start settings with the fastest inference speed. Remarkably, Sym-NCO achieves a 0.95% gap in TSP using the greedy rollout. the TSP greedy setting, it solves TSP 10,000 instances in a few seconds.
Results of PCTSP and OP. As shown in Table 2, Sym-NCO outperforms the NCO baselines in both the greedy rollout and multi-start settings. In the multi-start setting, Sym-NCO outperforms the classical PCTSP baseline (i.e., ILS) with the 43200 x 240 faster speed.
180

---

9.00
X000 20W0
Valication Cost
11.0
Validattoon Cort
Willdation Cool
8.75
10.5
9.0
10.0-
8:25
8.5
35,000
50,000
20,000
40,00
20,000
40,000
Step
Stop
Stop
(a) PointerNet
(b)
(c) POMO
Figure 4: The applications of Sym-NCO to DRL-NCO methods in TSP (N 100)
1644
7.00
1622
62
7.55
Inc
c 6.
Paae
AM
7.50
MIAMM
SpmrNCO
(a) TSP (N- 100)
(b) CVRP (N 100)
(c) PCTSP (N
100)
(d) OP (N 100)
Figure 5: Time vs. cost plots. Green, orange, and blue colored lines visualize the results of hand-craft heuristics, neural baselines, and Sym-NCO, respectively, For OP (d), higher y-axis values are better.
Results of the real-world TSP. We evaluate POMO and Sym-NCO on TSPLib [43]. Table 3 shows that Sym-NCO outperforms POMO. Please refer to Appendix D.2 for the full benchmark results.
Gap
POMO
1.87%
Sym-NCO
1.62%
Application to various DRL-NCO methods. As discussed in Section 3, Sym-NCO can applied to various various DRL-NCO methods. We validate that Sym-NCO significantly improves the existing DRL-NCO methods as shown in Fig. 4.
Table 3: Optimality gap on TSPLIB
Time- performance analysis for multi-starts. Multi-starts is common method that improves the solution qualities while requiring a longer time budget. We use the rotation augments [23] to produce multiple inputs (i.e., starts). As shown in Fig. 5, Sym-NCO achieves the Pareto frontier for all benchmark datasets. In other words, Sym-NCO exhibits the best solution quality among the baselines within the given time consumption.
6 Discussion
6.1 Discussion of Regularization based Symmetricity Learning
Ablation Study of Lim- As shown Fig. 6b, Linv increases the cosine similarity of the projected representation (i.e., g(h)). We can conclude that Linv contributes to the performance improvements (see Fig. 6a). We further verify that imposing similarity on h degrades the performance as demon- strated in Fig. 6c. This proves the importance of maintaining the expression power of the encoder as we mentioned Section 3.2.
Comparison with EGNN. EGNN [35] provably guarantees to process coordinate graph with rotational equivalency. Also, EGNN empirically verified its' high performance in point cloud tasks. Therefore, implemented simple EGNN-based CO policy (simply termed EGNN in this paper), to check the feasibility CO. We leverage six EGNN layers with 128 hidden dimensions, to replace the POMO encoder where the POMO decoder is unchanged.
In the experimental results, we observed that EGNN significantly underperforms Sym-NCO and fails to converge as shown Fig. 7b. This is because the euclidian CO has fully connected input graph containing informative coordinates, and we believe the equivariant neural network should be carefully crafted to consider such unique input graph structures of CO tasks. On the other hand, Sym-NCO could leverage the existing powerful NCO model without fine modification of the neural network. These numerical results conform well with hypothesis that equivariance is necessary but not

---

1.0
Lips Eye
fun (Ours)
w/ prof, head
Cosine Sunillrity
0.8
Validation Cost.
w/o proj. head
Objedtive
8.4
(POMO)
9.0
0.5
free
8.0
Cum
8,5
0.2
200,000
400,000
600,000
5001,000
1,000,000
1,500,000
0
20,000
40,000
60,000
Step
Step
(a) Cost curves the loss designs
(b) Cosine similarity curves
(c) Projection head ablation results
Figure 6: Loss design ablation results (a) Effect of loss components to the costs, (b) Cosine similarity curves of the models with and with Lav, (c) Costs of the models with and without g(-).
Cosire Simllrrity
1.0
Validation Cost
25
5ym-NNC
EGNN
20
0.8
15
0.6
RGNN
10-
500,000
1,000,000
1,500,000
20,000
40,000
60,000
Step
Step
(a) Cosine similarity curves
(b) Cost curves
Figure 7: Comparisons of Sym-NCO and EGNN
sufficient for obtaining the optimal parameters for the solver. Therefore, expect approach can be simply extended to other domains requiring symmetricity and geometricity as positioned to leverage the existing legacy of powerful non-equivariant neural networks.
6.2 Limitations & future directions
Extended problem symmetricities. this work, we employ the rotational symmetricity (Theo- rem 2.1) as the problem symmetricity. However, for some COPs, different problem symmetricities, such as scaling and translating P, can also considered. Employing these additional symmetricities may further enhance the performance of Sym-NCO, We leave this for future research.
Large scale adaptation. Large scale applicability is essential to NCO. In this work we simply present scale adaptation capability of Sym-NCO using the effective active search (EAS) [44]; see Appendix D.3. We expect curriculum- [45], and meta-learning approaches may improve the general- izability of NCO to larger-sized problems.
Extension to the graph COP. This work finds the problem symmetricity that is universally applicable Euclidean COPs. However, some COPs are defined in non-Euulidean spaces such as asymmetric TSP. Furthermore, there are also bunch of existing neural combinatorial optimization models that can solve graph COP [46, 47, 48, 49, 50, 51], where we can improve with a symmetricity regularization scheme. We also leave finding the universal symmetricities of non- non-Euclidean COPs and applying them existing graph COP models for future research.
6.3 Social Impacts
Design automation through NCO research affects various industries including logistics and trans- portation industries. From a negative perspective, this automation process may have some concerns to lead to unemployment in certain jobs. However, automation of logistics, transportation, and design automation can increase the efficiency industries, reducing CO2 emissions (by reducing total tour length) and creating industries and jobs.

---

Acknowledgments and Disclosure of Funding
We thank Jiwoo Son, Hyeonah Kim, Haeyeon Rachel Kim, Fangying Chen, and anonymous reviews for proving helpful feedback for preparing our manuscripts. This work was supported by grant of the KAIST-KT joint research project through AI2XL. Laboratory, Institute of convergence Technology. funded by KT [Project No. G01210696, Development of Multi-Agent Reinforcement Learning Algorithm for Efficient Operation of Complex Distributed Systems].
References
[1] Stefan Irnich, Paolo Toth, and Daniele Vigo. Chapter 1: The Family of Vehicle Routing Problems, pages 1-33.
[2] Matthew Veres and Medhat Moussa. Deep learning for intelligent transportation systems: A sur- vey of emerging trends. IEEE Transactions on Intelligent Transportation Systems, 21(8):3152- 3 3168, 2020.
[3] Sungsoo Ahn, Junsu Kim, Hankook Lee, and Jinwoo Shin. Guiding deep molecular optimization with genetic exploration. Advances in neural information processing systems, 33:12008 120211, 2020.
[4] Sungsoo Ahn, Binghong Chen, Tianzhe Wang, and Le Song. Spanning tree-based graph generation for molecules. In International Conference Learning Representations, 2021.
[5] Azalia Mirhoseini, Hieu Pham, Quoe V. Le, Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean. Device placement optimiza- tion with reinforcement learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2430-2439, PMLR, 06-11 Aug 2017.
[6] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim M. Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Anand Babu, Quoc V. Le, James Laudon, Richard C. Ho, Roger Carpenter, and Jeff Dean. Chip placement with deep reinforcement learning. CoRR, abs/2004. 10746, 2020.
[7] Haiguang Liao, Qingyi Dong, Xuliang Dong, Wentai Zhang, Wangyang Zhang, Weiyi Qi, Elias Fallon, and Levent Burak Kara. Attention routing: track-assignment detailed routing using attention-based reinforcement learning. 2020.
[8] Minsu Kim, Hyunwook Park, Seongguk Kim, Keeyoung Son, Subin Kim, Kyunjune Son, Seonguk Choi, Gapycol Park, and Joungho Kim. Reinforcement learning-based auto-router considering signal integrity. In 2020 IEEE 29th Conference on Electrical Performance of Electronic Puckaging and Systems (EPEPS), pages 1-3, 2020.
[9] Minsu Kim, Hyunwook Park, Keeyoung Son, Seongguk Kim, Haeyeon Kim, Jihun Kim, Jinwook Song, Youngmin Ku, Jounggyu Park, and Joungho Kim. Imitation learning for simultaneous escape routing. In 2021 IEEE 30th Conference Electrical Performance of Electronic Packaging and Systems (EPEPS), pages 1-3, 2021.
[10] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks, In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 2692-2700. Curran Associates, Inc., 2015.
[11] Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bresson. Learning tsp requires rethinking generalization, 2020.
[12] Wouter Kool, Herke van Hoof, Joaquim A. S. Gromicho, and Max Welling, Deep policy dynamic programming for vehicle routing problems. CoRR, ab5/2102.11756. 2021.
[13) Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances, 2020.
10

---

[14] André Hottung, Bhanu Bhandari, and Kevin Tiemny. Learning a latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2020.
[15] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. CoRR, abs/1911 1/5/1911.09955 1.09599, 2019.
[16] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems, 2020.
[17] Paulo R O da Costa, Jason Rbuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Sinno Jialin Pan and Masashi Sugiyama, editors, Proceedings of The 12th Asian Conference on Machine Learning, volume 129 of Proceedings of Machine Learning Research, pages 465-480, Bangkok, Thailand, 18-20 20 Nov 2020. PMLR.
[18] Sungsoo Ahn, Younggyo Sco, and Jinwoo Shin. Learning what to defer for maximum inde- pendent sets. Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 144-144. PMLR, 13-18 Jul 2020.
[19] Minsu Kim, Jinkyoo Park, and Joungho Kim. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, 2021.
[20] Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combi- natorial optimization with reinforcement learning, 2017.
[21] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn solve routing problems! In International Conference on Learning Representations, 2019.
[22] Mohammadreza Nazari, Afshin Oroojlooy. Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[23] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188821998, 2020.
[24] Junyoung Park, Jachyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11):3360-337 2021.
[25] Yining Ma. Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances Neural Information Processing Systems, 34, 2021.
[26] Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with em- bedding glimpse for solving vehicle routing problems. In Proceedings of 35th AAAI Conference on Artificial Intelligence, pages 12042-12044 12049, 2021.
[27] Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn to solve multi-agent scheduling problems with reinforcement learning. arXiv preprint arXiv:2106.0300: 2021.
[28] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, 2019.
[29] Hansen Wang, Zefang Zong, Tong Xia, Shuyu Luo, Meng Zheng, Depeng Jin, and Yong Li. Rewriting by generating: Learn heuristics for large-scale vehicle routing problems, 2021.
[30] Ronald J Williams. Simple statistical wrallinn-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229-255 1992.

---

[31] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PMLR, 2020.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, F. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30, pages 5998-6008, Curran Associates, Inc., 2017.
[33] Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics, pages 4474-4484. PMLR, 2020.
[34] Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling, Se ())ttrasfformers: 3d roto-translation equivariant attention networks, Advances in Neural Information Processing Systems, 33:1970-1981, 2020.
[35] Viéctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural networks. In International Conference Machine Learning, pages 22322932. PMLR, 2021.
[36] Elise van der Pol, Daniel Worrall, Herke van Hoof, Frans Olichoek, and Max Welling. Mdp homomorphic networks: Group symmetries in reinforcement learning. Advances in Neural Information Processing Systems, 33:4199-42104 2020.
[37] Wenbin Ouyang, Yisen Wang, Paul Weng, and Shaochen Han. Generalization in deep rl for tsp problems via equivariance and local search. arXiv preprint (..iv:2110000350 2021.
[38] Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110005291, 2021.
[39] Vašek Chvátal David Applegate, Robert Bixby and William Cook. Concorde tsp solver.
[40] Keld Helsgaun. An extension of the lin dermighan-helsgane tsp solver for constrained traveling salesman and vehicle routing problems. 12 2017.
[41] Elias Khalil, Hanjun Dai, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, pages 6348-6358. Curran Associates, Inc., 2017.
[42] Gorka Kobeaga, María Merino, and Jose A Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers & Operations Research, 90:42-59 2018.
[43] Gerhard Reinelt. Tsplib-a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
[44] André Hottung, Yeong- Kwon, and Kevin Tiemey. Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.05126, 2021.
[45] Michal Lisicki, Arash Afkanpour, and Graham W Taylor. Evaluating curriculum learning strategies in neural combinatorial optimization. arXiv preprint 1.XX::20/11.0188. 2020.
[46] Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combina- torial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243-3250 2020.
[47] Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 19-24. IEEF, 2020.
12

---

[48] Thomas D Barrett, Christopher WF Parsonson, and Alexandre Laterre. Learning to solve combi- natorial graph partitioning problems via efficient exploration. arXiv preprint A.V::2205.14105. 2022.
[49] Shenshen Gu and Yue Yang. A deep learning algorithm for the max-cut problem based on pointer network structure with supervised learning and reinforcement learning strategies. Mathematics, 8(2), 2020.
[50] Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving np-hard problems graphs with extended alphago zero. arXiv preprint arXiv: 190:: 1623, 2019.
[51] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search, Advances in neural information processing systems, 31, 2018.
13

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Did you describe the limitations of your work? [Yes] See Section 6.2
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Source code will be available after decision is made.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5.2.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix C.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/]]
14


Reviews:
[{"review_id": "j1rjzzhov7", "reviewer": "Reviewer_186o", "summary": "This work is in the area of learning to approximately solve TSP, CVPR, and the associated class of routing problems using deep reinforcement learning.\n\nThe main methodological contribution is to identify that routing problems and their solutions often contain symmetries such as **rotational symmetry** or the **cyclical nature** of the solutions. The paper proposes **new loss functions** that **softly incorporate symmetries** for the encoder-decoder architecture from AM (Kool-etal) and POMO (Kwon-etal). \n\nTraining models via the proposed loss functions (termed 'Sym-NCO') improve over the models trained via previously proposed loss functions on random routing problem instances as well as on real-world instances from TSPLib.\n\n==========\n\nPost rebuttal: Thank you to the authors for partially addressing my concerns. I have updated my score based on the responses. In particular, I was not fully convinced regarding statements on the (lack of) expressive power of equivariant networks, e.g. “ENN scheme provably guarantees to trained in symmetric space; more expression power is needed for CO tasks”. I apologise that I am unable to engage actively in author discussions at this time as I have fallen ill after traveling.\n\n==========\n\nPost author discussions: Thank you for addressing my concerns regarding the claims on expressive power and hard vs. soft invariant learning. I believe this work demonstrably improves the performance of NCO solvers by leveraging appropriate symmetries, and these empirical findings may be of interest for the broader community working on combinatorial problems beyond routing. I have updated my score with these considerations.", "questions": "Following the **Weaknesses** part of the review, there were several parts of the paper where the writing and presentation were unclear to me:\n- Lines 1-3, Abstract, states that DRL has merits over traditional CO solvers because DRL does not need supervised data. To the best of my knowledge, traditional CO solvers (which include Concorde or LKH) also **do not** need supervised data. Could the authors clarify this statement?\n- I was uncertain what the relationship of Eq. 4 and Eq. 5/6 were to Eq. 1. I understand that they are components of the overall loss L_sym in Eq. 3, however, **how is L_sym used to model Eq. 1**?\n- In the results in Table 1 and 2, it appears as if Sym-NCO is a model by itself. On the other hand, the experimental setting states that Sym-NCO is applied to POMO, AM, and PointerNet. Could the authors clarify which of the **underlying models** were trained for each row of results highlighted as Sym-NCO? \n\nIn addition to the questions on writing/presentation, here are additional questions regarding **approximate vs. exact rotation invariance** in Section 6.1:\n- I found the results in Section 6.1 extremely counterintuitive. The results seem to suggest that provable rotation invariance is **actually undesirable**, and the authors have tried to justify this by saying that nudging the model to be approximately rotationally invariant makes it more **'flexible'** and maintain its 'representation capability'. In my opinion, the justifications are rather hand wave-y. Could the authors be more precise in defining these terms?\n- As a continuation of the previous point, in my opinion, the curves in Fig. 6 show one of two things: (A) rotational symmetry is irrelevant to the problem, so EGNNs are not useful and unable to learn the task well (as seen by their fluctuating performance); or (B) the approximately rotationally invariant models are **overfitting on the data distribution** that is being used for training and validation (both are randomly generated in the same size range). Is this how one should interpret these results, or would the authors disagree? \n- Finally, could the authors provide some implementation details of the EGNN used?\n\nFinally, I had some other minor questions or nitpicks to mention:\n- Titles of Sections 3.1 and 3.2 state that the symmetries are being **'imposed'**. However, in my opinion, this may be **misleading** as the symmetries are only approximated, not imposed. E.g. the encoder model's output features are only approximately invariant to rotations (unless using models which are provably rotation invariant).\n- It was unclear to me why there are no empirical comparisons to the **improvement-style NCO models**. Could the authors justify this decision?", "limitations": "The authors have included several technical limitations of the present work and avenues for future research. They have **not included** any sections on **potential negative social impact**, and this should at least be addressed. Is it likely that this type of research may be put in production in the logistics or transportation industry, and if so, what may be some considerations to make?\n\nIn my opinion, one major limitation of this work is the **lack of justification** or understanding of **approximate vs. exact rotation invariance** in the hidden representations of the encoder. E.g. is rotational symmetry even relevant in real world datasets beyond synthetic and random TSPs/CVPRs? As such, **real world** maps and cities have a **canonical set of coordinates** and **directions** (north, south, east, west). This is to say that, in a city where I may have many locations that I would like to navigate through, I always have an aligned or fixed set of coordinates as inputs - there doesn't seem to be a good reason to arbitrarily rotate them.  \n\nIt is worth considering whether methodological developments on synthetic tasks may be useful for the corresponding real-world applications in routing.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- **Clear motivation**: The paper does a good job at presenting ideas around how routing problems and their solutions often contain symmetries such as rotational symmetry or the cyclical nature of the solutions. The figures are very instructive.\n\nWeaknesses:\n- **Unclear writing and presentation**: There are several aspects of the paper where the writing and presentation was unclear to me. I have listed this down under the **Questions** part of my review.\n- **Counterintuitive results** and **lack of justification**: The results in Section 6.1 around approximate vs. exact rotation invariance are counterintuitive as they suggest to me that rotation invariance is in fact not desirable (because when it is enforced exactly, the model is unable to perform at all). However, these findings are not sufficiently justified or understood (see **Questions** section). I may have misunderstood the results or may be missing something here.\n- **Insufficient discussions on related work**: There are several recent works which as based on incorporating symmetries to improve learning for routing problems, but are not discussed in this paper, e.g. [Hudson et al.](https://arxiv.org/abs/2110.05291) obtained strong results via a **rotationally invariant GNN** via converting graphs to line graphs, [Ma et al.](https://arxiv.org/abs/2110.02544) proposed positional encodings that incorporated the **cyclical nature** of routing problems, [Ouyang et al.](https://arxiv.org/abs/2110.03595) performed **preprocessing** to make the model (approximately?) invariant to rotations. The Related Work section does not do enough to contextualise present work w.r.t. recent advances in the community, which may be doing something similar or tangential to the present approach. In the best case, it would also be good to empirically compare to these techniques.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "czJ_Nqv19cM", "reviewer": "Reviewer_5sgV", "summary": "Combinatorial optimization problems often have numerous symmetries. This work proposes to leverages these symmetries to improve the training of neural networks that have been proposed in other works to solve such combinatorial optimization problems.\nMore specifically, the paper:\n  * precisely defines two types of symmetries it wants to leverage, covering both symmetries that are inherent to the formulation of these problems and symmetries that are intrinsic to the solution spaces of such problems.\n  * Proposes a regularization scheme to help the neural network learn for the symmetries\n  * Evaluate their approach extensively on 4 common combinatorial optimization problems.", "questions": "Can you detail how you came up with equations 5 and 6 ? If needs be, you can add the relevant text to the supplemental material as you did for the proof of theorem 2.1. This would really help convince me of the soundness of your approach.\n\nWhat does gr refers to in table 1?\n\nIn section 5.2 you mention that you applied Sym-NCO to POMO, AM, and PointerNet. Which one did you use to gather the results in Table 1 and 2 ? It would be interesting to be able to compare the 3 versions against their corresponding baselines whenever possible.\n\nWould it be possible to extend your your comparison with EGNN to also train the EGNN model with your loss ? I'd love to see to what extend your approach is complementary to that of EGNN, in which case you should be able to improve on the performance reached by the EGNN model by training it with your loss. \n\n \n", "limitations": "Nothing of note here.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall the paper is well written and fairly easy to follow. However, it's unclear how the authors came up with equation 5 and 6. It looks like the authors don't need to mathematically define Lss and Lps (which is why they never do so in the paper), but instead directly tweak the corresponding gradients in order to build two regularization gradients. The paper would be much easier to follow if that was clearly stated, and the process the authors went through in order to build these 2 gradient terms was spelled out.\n  \nSince I am not sure how the authors came up with equation 5 and 6, I didn't check the correctness of the maths, so at this point I cannot vouch for the theoretical soundness of the approach. That said, the experimental results look good, so I'm optimistic that the maths will check out. I am looking forward to more explanations from the authors in the rebuttal. \n\nThe various graphs in figure 6 are drawn for varying numbers of training steps. Why not use a consistent number of steps ?\n\nPrevious work have proposed to take advantage of symmetries to improve the generalization, mainly by leveraging symmetry invariant neural networks architectures, or by leveraging problem specific symmetries. As far as i know, this is the first work that proposes a solution that can be applied to any neural network, which is a significant innovation.\n\nThe evaluation shows that Sym-NCO results in better quality of results on all 4 benchmarks the approach was evaluated on. Furthermore, it gets these results at least as fast as the fastest other approach it was compared against. This is extremely significant.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Xcz0e2MbDJT", "reviewer": "Reviewer_oKeQ", "summary": "This paper considers the problem of training neural networks to solve NP-hard CO problems. Recent works have sought to apply ML to CO, but often fall short of outperforming the state-of-the-art handcrafted heuristics; methods which neural networks have the potential to surpass in both optimality and solving time. To address this, the authors first identify that CO problems have underlying symmetries in both their problem definition and their corresponding solutions. The authors reason that explicitly learning these symmetries will implicitly aid learning to find near-optimal solutions quickly. To this end, the authors propose a new loss function which guides the network towards finding optimal solutions whilst also learning embeddings which retain these symmetries; an achievement which the authors implicitly reason makes learning to solve such CO problems more tractable for RL. Moreover, the authors claim that their loss function formulation is agnostic to the specific CO problem considered, and that it can be applied to and improve any prior neural CO solver from the literature. The authors demonstrate their proposed loss function's efficacy on four CO problems (TSP, CVRP, PCTSP, and OP), and claim to surpass all ML baselines on all four CO problems.", "questions": "### Introduction & Methodology\n\n* **'Solution symmetricity and shared features' clarification:** In the Introduction when the authors introduce the two types of CO symmetry they consider, they say: ‘Second, the solution symmetricity, which is the shared feature among solutions having identical optimal values.’ I find this sentence difficult to understand - do the authors just mean that solution symmetricity is where solutions have the same value? What is the ‘shared feature’, and why do the values necessarily need to be optimal? In Definition 2.2, the authors state that two solutions are symmetric when their total returns are equal; nothing about optimality is mentioned as far as I can tell.\n\n* **'Pre-identified symmetricites' clarification:** In the Introduction, the authors mention that their novel learning scheme ‘imposes symmetricities by leveraging the pre-identified symmetricities’. Does ‘pre-identified symmetricities’ refer to the problem and solution symmetricities, or some pre-identification method? This jargon should be explicitly defined in my view for clarity.\n\n* **Difficulty of solution symmetricity identification:** In the Introduction, the authors state that problem symmetricity is found in all CO problems in the form of rotational symmetricity, but that solution symmetricity cannot be identified easily as the ‘properties of the solutions are distinct for every CO problem’. What specific properties are distinct? Is solution symmetricity where two solutions result in the same return (as stated in Definition 2.2), in which case why is it not easy to evaluate whether two solutions are symmetric?\n\n* **Overall motivation and intuition:** I think the Introduction and Discussion is missing some motivation for the overall idea. Why do the authors think it is fundamentally beneficial to account for symmetricities in the learning scheme? Are there state-of-the-art solvers which do this, or are the authors relying on some intuition that explicitly learning CO symmetricities will lead to a parameterised network more able to find solutions in fewer steps since it will have learned to find multiple policies which lead to the same near-optimal reward, and therefore have greater chance of generalisation at test time? I think a discussion of what motivated the idea and what the intuition is behind it is currently missing from the paper.  \n\n* **Inconsistent jargon:** In the Sym-NCO Methodology, is the ‘invariant representation symmetry’ just the ‘problem symmetricity’ referred to elsewhere? If so, I think it would be good to keep jargon to a minimum by consistently referring to the various phenomena being discussed by the same names. If not, then I have misunderstood what is being discussed here.\n\n* **Solution sampling methodology:** How exactly are the $K$ and $L$ solutions sampled from the REINFORCE policy? Is this done with some stochastic exploration policy?\n\n* **Advantage function:** \n    * In equation 5, is $R(\\pi(P))$ the greatest rewards attained by policy $\\pi$ for problem $P$ across all $K$ samples? I.e. is $R(\\pi(P))$ a subset of R({\\pi^{k}\\}^{K}{k=1}? If not, what is the difference between how $R(\\pi(P))$ and R(\\{\\pi^{k}\\}^{K}{k=1} are generated?\n\n    * Could the authors please explain how the proposed advantage function means the advantage will be negative if a proposed solution has a worse optimality than the K solutions sampled? Will it not only be negative if it is worse than the mean of the $K$ sampled solutions, since the baseline is just the mean return of $K$ sampled solutions? Same for $L$ in Equation 6.\n\n* **Unclear REINFORCE methodology and integration:** Where is $L_{inv}$ (and by extension $L_{sym}$) actually incorporated into training with REINFORCE? The policy gradient theorem defined in Equations 5 and 6 only seems to include the $L_{ss}$ and $L_{ps}$ terms, so where is $L_{inv}$? Where are the three symmetric loss functions combined? Furthermore, are Equations 5 and 6 separate, or does Equation 6 contain Equation 5 with the $L$ and $K$ summations? I would like to see how all of this is tied together, since at the moment I do not think it is clear.\n\n\n### Related Work\n\n* **Missing related work and context:** This section is missing some important work and fails to introduce some of the baselines considered in the later Experiments section (e.g. S2V-DQN) and the context around them. I do not think it necessary to add all prior works to the set of baseline comparisons, since the authors are showing that the Sym-NCO method can improve a range of different architectures and methods, but I think a discussion in the related work of a few more pieces of literature should be included to put the Sym-NCO work in context. In particular, the related work is missing a discussion of where Sym-NCO fits in the context of some of the key state-of-the-art non-GNN, GNN, supervised learning, and reinforcement learning works (e.g. Bello et al. 2016, Gu and Yang 2020, Dai et al. 2017, Abe et al. 2019, Li et al. 2018, Barrett et al. 2020 and 2022, Drori et al. 2020, Hottung et al. 2022).\n\n\n\n### Experiments\n\n* **Small CO instances:** At $100$ nodes, the CO problems considered are very small compared to those considered by e.g. Gu and Yang 2020 ($300$ nodes), Drori et al. 2020 ($1,000$ nodes), and Barrett et al. 2022 ($10,000$ nodes). Does Sym-NCO scale? Does the requirement to sample $L \\times K$ solutions for the advantage function and to gain enough data to learn the symmetricities hinder scalability? This would be interesting information to include in the paper’s experiments and discussion.\n\n* **Statistical significance of solver performance differences:** On $O(100)$ node problems of the size considered, many of the ML-CO methods in Table 1 seem to obtain similar costs (e.g. AM gets $7.94$, POMO and MDAM get $7.80$, and Sym-NCO gets $7.79$). Is this a statistically significant difference in the optimality gap? It would seem that on such small CO problems there is not much room for differing costs, and that the results of Sym-NCO can be easily made to overfit until the reported result is achieved.\n\n* **Optimality gap calculation:** How were the optimality gaps in Table 1 calculated? E.g. If the optimal solution of TSP is $7.76$ and Sym-NCO finds a solution of $7.84$, does this not mean that Sym-NCO’s solution cost is $1.03$% higher than the optimal solution (the authors have recorded a gap of $0.94$%)?\n\n* **Unclear Sym-NCO integration with existing ML solvers:** Table 1 and Fig 4 do not indicate which ML method(s) Sym-NCO was applied to. They just state Sym-NCO as a standalone method, but is Sym-NCO not applied to at least one of the other baselines to get the results in the table? At the beginning of the Experiments section, the authors state that they apply Sym-NCO ‘on top of POMO, AM, and PointerNet’, but it is not clear from Table 1 and Fig 4 which underlying method was used for Sym-NCO.\n\n* **Missing experimental data:** In Table 1, why are PointerNet and S2V-DQN missing solving time values?\n\n* **Negative optimality gaps:** In Table 1, having a negative 'optimality gap' does not make sense - how can a solution be found which is more optimal than the optimal solution?\n\n* **Unclear and inconsistent results:** Table 1 and Figs 3 and 4 are not consistent in multiple regards:\n    * Fig 3 shows PointerNet getting a minimum validation cost of $\\approx9.50$ for TSP, but Table 1 shows PointerNet to have a cost of $8.30$. Also, none of the Sym-NCO validation curves in Fig 3 reach the $7.84$/$7.79$ TSP costs claimed in Table 1. Why? \n    * Fig 4a: Sym-NCO and POMO get almost exactly the same $\\approx0.79$ result, yet POMO is recorded as having achieved a cost of $0.80$ in Table 1 compared to Sym-NCO’s recorded $0.79$.\n    * What are the stopping criteria to stop running each solver? In Fig 4, it seems that the algorithms were still improving their solutions when they were stopped, and it also seems as though some of the other ML baselines were on track to surpass the optimality of Sym-NCO; it is important to report if Sym-NCO converges faster but to less optimal solutions.\n\n* **Missing sensitivity analysis to the introduced hyperparameters:** What is the sensitivity of Sym-NCO to $\\alpha$, $\\beta$, $L$, and $K$? In the Appendix, the authors only show results for $\\alpha = \\{0.1, 0.2\\}$, but $\\alpha, \\beta \\in [0, 1]$. In proposing a new training scheme which introduces additional hyperparameters, the authors should have a comprehensive study of the influence of these hyperparameters on training and validation performance across different problems, since this is relevant information for practitioners who may wish to use the work.\n\n* **Missing analysis and discussion of Sym-NCO design choices:** Which factors determine the values of $K$ and $L$ in Sym-NCO? Presumably they change as the size and nature of the CO problem changes, since some CO problems will be difficult to sample trajectories for which sufficiently encapsulate the symmetricities (e.g. some CO problems will have a vast number of possible solutions, and only a few of these might have the same objective function value; will this influence the ability with which Sym-NCO can learn the underlying solution symmetry of the problem? Is there a requirement on how many solutions with the same/similar objective value are needed to make learning solution symmetry tractable? Can solution symmetry still be imposed if no solutions with the same objective are found?)\n\n* **Missing analysis of Sym-NCO incurred overhead:** What is the incurred training overhead of sampling the $K \\times L$ solutions needed for the Sym-NCO advantage function baseline?\n\n\n### Other\n\n* **Generality claims:** The paper makes claims (in the title, abstract, and throughout the paper) to be a general neural CO solver training scheme. However, Sym-NCO has been specifically designed for policy-gradient RL and was only applied to REINFORCE. Moreover, it only considers graph-based CO problems which are variants of TSP and, for that matter, only looks at instances which can be projected onto Euclidean space. Do other ML-CO methods consider non-Euclidean problems (e.g. Dai et al. 2017, Barrett et al. 2020 & 2022, Drori et al. 2020) where graphs trained and inferred on can have differing structures? Are the authors claiming that Sym-NCO can be generalised to ML paradigms (supervised and unsupervised learning) and CO problems (non-graph-based and/or non-Euclidean graph-based) other than those considered in the paper? Can the existence of the same symmetries considered in this paper be universally assumed to exist for all CO problems? \n\n* **Euclidean vs. non-Euclidean problem clarification:** Was there a particular reason for only considering Euclidean problems rather than utilising the now commonplace graph neural network architectures such as those used in prior works (mentioned above) which can handle non-Euclidean inputs with varying structures? What are the limitations of only handling Euclidean CO problems in terms of applications and the state-of-the-art literature? Do the authors have to hand-pick problems to meet this Euclidean constraint?\n\n\n### Miscellaneous minor issues\n* Pg. 1 line 2: Introduce DRL-NCO acronym but unclear what the ‘N’ stands for (presumably ‘neural’, but should specify)\n\n* Pg. 4 line 114: Should it not be ‘as the hidden representations of $x$ and $Q(x)$’ rather than ‘$x$ and $P(x)$’?\n\n* Pg. 4 line 119: There seems to be unnecessary extra brackets in the $g(\\cdot)$ term\n\n* Pg. 6 line 197: You list PointerNet without saying which CO problem(s) you applied it to as you did for the other methods.\n\n* Throughout the paper, you introduce many acronyms (e.g. S2V-DQN, AM, POMO, MDAM, etc.) without first stating what the full name of the acronyms are, which you should always give when first introducing a new acronym.\n\n* It seems confusing to refer to the method of Nazari et al. 2018 as ‘RL’ since there are multiple other RL methods such as S2V-DQN.\n\n* Citation [20] seems to be miss-formatted?\n\n### References\n\n1. Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017\n2. Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020\n3. Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. arXiv:2006.03750, 2020\n4. Andre Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. International Conference on Learning Representations, 2022.\n5. Thomas D. Barrett, Christopher W. F. Parsonson, and Alexandre Laterre. Learning to solve combinatorial graph partitioning problems via efficient exploration. arXiv:2205.14105, 2022\n6. Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural Combinatorial Optimization with Reinforcement Learning. arXiv:1611.09940, 2016\n7. Shenshen Gu and Yue Yang. A Deep Learning Algorithm for the Max-Cut Problem Based on Pointer Network Structure with Supervised Learning and Reinforcement Learning Strategies. Mathematics, 2020\n8. Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving NP-Hard Problems on Graphs by Reinforcement Learning without Domain Knowledge. arXiv:1905.11623, 2019\n9. Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. In Advances in Neural Information Processing Systems, 2018\n10. MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, 2018", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong points:\n* Addresses an important and significant application area of ML, namely solving NP-hard CO problems.\n* Proposes a novel and original loss function which guides the network towards learning the underlying symmetries of CO problems in addition to learning to find near-optimal solutions.\n* The proposed approach is seemingly easy to integrate with existing ML-CO solvers and is therefore complimentary to a broad variety of prior work.\n\nWeak points:\n* The paper/writing is unclear in multiple areas (see below).\n* The $100$ node problem sizes considered are significantly smaller than those of prior works.\n* The Experiments section in general has multiple shortcomings and inconsistencies (see below).\n* The Related Work section is incomplete and may not sufficiently place this work in the context of the current literature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept