DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
Authors: Ruizhong Qiu
Zhiqing Sun
Yiming Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Combinatorial Optimization
Graph Neural Network
Meta Learning
Traveling Salesman Problem (TSP)
Minimum Indepedent Set (MIS)

Abstract: Recently, deep reinforcement learning (DRL) models have shown promising results in solving NP-hard Combinatorial Optimization (CO) problems. However, most DRL solvers can only scale to a few hundreds of nodes for combinatorial optimization problems on graphs, such as the Traveling Salesman Problem (TSP).   This paper addresses the scalability challenge in large-scale combinatorial optimization by proposing a novel approach, namely, DIMES. Unlike previous DRL methods which suffer from costly autoregressive decoding or iterative refinements of discrete solutions, DIMES introduces a compact continuous space for parameterizing the underlying distribution of candidate solutions. Such a continuous space allows stable REINFORCE-based training and fine-tuning via massively parallel sampling. We further propose a meta-learning framework to enable the effective initialization of model parameters in the fine-tuning stage. Extensive experiments show that DIMES outperforms recent DRL-based methods on large benchmark datasets for Traveling Salesman Problems and Maximal Independent Set problems.

DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
Ruizhong Qiu Department of Computer Science University Illinois Urbana Champaigg rq5@illinois. edu
Zhiqing Sun;, Yiming Yang
Language Technologies Institute Carnegie Mellon University
iichigingsyymming cmu. edu
Abstract
Recently, deep reinforcement learning (DRL) models have shown promising results in solving NP-hard Combinatorial Optimization (CO) problems. However, most DRL solvers only scale to a few hundreds of nodes for combinatorial opti- mization problems on graphs, such as the Traveling Salesman Problem (TSP). This paper addresses the scalability challenge in large-scale combinatorial optimization by proposing a novel approach, namely, DIMES. Unlike previous DRL. methods which suffer from costly autoregressive decoding iterative refinements of discrete solutions, DIMES introduces compact continuous space for parameterizing the underlying distribution of candidate solutions. Such a continuous space allows stable REINFORCE- b-sse training and fine-tuning via massively parallel sampling. We further propose a meta-learning framework enable effective initialization of model parameters in the fine-tuning stage. Extensive experiments show that DIMES outperforms recent DRL-based methods on large benchmark datasets for Traveling Salesman Problems and Maximal Independent Set problems.
Introduction
Combinatorial Optimization (CO) is fundamental problem in computer science. It has important real-world applications such as shipment planning, transportation, robots routing, biology, circuit design, and more [67]. However, due NP-hardness, significant portion of the CO problems suffer from an exponential computational cost when using traditional algorithms. As a well-known example, the Traveling Salesman Problem (TSP) has been intensively studied [35] 60] for finding the most cost-effective tour over an input graph where each node is visited exactly once before finally returning the start node. Over the past decades, significant effort has been made for designing more efficient heuristic solvers 55 20 to approximate near-optimal solutions reduced search space.
Recent development in deep reinforcement learning (DRL) has shown promises in solving CO problems without manual injection of domain-speccie expert knowledge 7 neural methods is because they can learn useful patterns (such as graph motifs) from data, which might be difficult to discover by hand. A typical category of DRL solvers, namely construction heuristics learners. 7 42 uses Markov decision process (MDP) to grow partial solutions by adding one new node per step. with a trained strategy which assigns higher probabilities to better solutions.
42 45).
The appeal of
Another category of DRL-based solvers, namely improvement heuristics learners [IO 72 iteratively
refines a feasible solution with neural neework-guuide local Operations Research (OR) operations
64 A major limitation of these DRL solvers lies in their scalability large instances. For example, current DRL solvers for TSP can only scale to graphs with up to hundreds of nodes.
"Equal contribution.
Work was done during internship at CMU.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The bad scalability of these DRL methods lies in the fact that they suffer from costly decoding of CO solutions, which is typically linear in the number of nodes in the input graph. Since the reward of reinforcement learning is determined after decoding complete solution (with either a chain rule factorization or iterative refinements), either construction or improvement heuristic learners would encounter the sparse reward problem when dealing with large graphs [42 33 (77. While such an overhead can be partially alleviated by constructing several parts of the solution in parallel [[] for locally decomposable CO problems such for maximum independent set (MIS) problems (54), how to scale up neural solvers for CO problems in general, including the locally non-decomposable ones (such as TSP) is still an open challenge.
Fl
In this paper, we address the scalability challenge by proposing a novel framework, namely DIMES (Differentiable MEta Solver), for solving combinatorial optimization problems. Unlike previous DRI.-based CO solvers that rely on construction or improvement heuristics, we introduce a compact continuous space to parameterize the underlying distribution of candidate solutions, which allows massively parallel on on-policy sampling without the costly decoding process, and effectively reduces the variance of the gradients by the REINFORCE algorithm 771 during both training and fine-tuning phases. We further propose a meta-learning framework for CO over problem instances to enable effective initialization of model parameters in the fine-tuning stage. To our knowledge, we are the first to apply meta-learning over a collection of CO problem instances, where each instance graph is treated as one of collection tasks in unified framework.
We need to point out that the idea of designing a continuous space for combinatorial optimization problems has been tried by the heatmaps approaches in the literature [48] 31, 19 14 44). However, there are major distinctions between the existing methods and our DIMES. For instance, Fu et al. [19 learn to generate heatmaps via supervised learning (i.e., each training instance is paired with its best solution) [4 (21, which is very costly to obtain on large graphs. DIMES is directly optimized with gradients estimated by the REINFORCE algorithm without any supervision, so it can be trained on large graphs directly. As a result, DIMES can scale to large graphs with up to tens of thousands of nodes, and predict (nearly) optimal solutions without the need for costly generation of supervised training data or human specification of problem-specifie heuristics.
In our experiments, we show that DIMES outperforms strong baselines among DRL-based solvers on TSP benchmark datasets, and can successfully scale up to graphs with tens of thousands of nodes. As a sanity check, we also evaluate our framework with locally decomposable combinatorial optimization problems, including Maximal Independent Set (MIS) problem for synthetic graphs and graphs reduced from satisfiability (SAT) problems. Our experimental results show that DIMES achieve competitive performance compared to neural solvers specially designed for locally decomposable CO problems.
2
Related Work
2.1 DRL-Based Construction Heuristics Learners
Construction heuristics methods create solution of CO problem instance in one shot without further modifications. Bello et al. (7] are the first to tackle combinatorial optimization problems using neural networks and reinforcement learning. They used a Pointer Network (PtrNet) [68] as the policy network and used the actor-critic algorithm [41] for training on TSP and KnapSack instances. Further improved models have been developed afterwards [13 42
63 14 46), such as attention models
69 for an extended scope of CO problems such Job Shop Scheduling Problem (JSSP) (76). Maximal Independent Set (MIS) problem [36]] and boolean satisfiability problem (SAT) [75).
(66). better DRL algorithms [36] 52 443
445
59
73
as Capacitated Vehicle Routing Problem (CVRP)
Our proposed method in this paper belongs to the category of construction heuristics learners in the sense of producing a one-shot solution per problem instance. However, there are major distinctions between previous methods and ours. One distinction is how to construct solutions. Unlike previous methods which generate the solutions via a constructive Markov decision process (MDP) with rather costly decoding steps (adding one un-visited node per step to a partial solution), we introduce compact continuous space to parameterize the underlying distribution of discrete candidate solutions, and to allow efficient sampling from that distribution without costly neural network-involver decoding.
'Locally decomposable problem refers to the problem where the feasibility constraint and the objective can be decomposed by locally connected variables (in graph) [I.

---

Another distinction is about the training framework. For instance, Drori et al. 14 proposes a similar solution decoding scheme but employs a DRL framework to train the model. Instead, we propose much more effective meta-learning framework to train our model, enabling DIMES to be trained on large graphs directly.
2.2 DRL-Based Improvement Heuristics Learners
In contrast to construction heuristics, DRL-based improvement heuristics methods train a neural network iteratively improve the quality of the current solution until computational budget runs out. Such DRL-based improvement heuristics methods are usually inspired by classical local search algorithms such 2-opt [11] and the large neighborhood search (LNS) 665 and have been
demonstrated with outstanding results by many previous work 72 51 70 12
10 26 74 53 29 37).
Improvement heuristics methods generally show better performance than construction heuristics methods but are slower in computation in return.
2.3 Supervised Learners for CO Problems
Vinyals et al. 668 trained a Pointer Network to predict TSP solution based on supervision signals from the Keld-Karp algorithm 66] or approximate algorithms. Li et al. [88] and Joshi et al. [31 trained a graph convolutional network to predict the possibility of each node or edge be included in the optimal solutions of MIS and TSP problems, respectively. Recently, Joshi al. [32] showed that unsupervised reinforcement learning leads to better emergent generalization over various sized
graphs than supervised learning. Our work in this paper provides further evidence for the benefits of
the unsupervised training, more specifically, unsupervised generation of heatmaps [48] [] 19 44) for combinatorial optimization problems.
Proposed Method
3.1 Formal Definitions
Following conventional notation 61 define F, as the set of discrete feasible solutions for CO problem instance and : F. + IR as the cost function for feasible solutions f E Fs. The objective is to find the optimal solution for a given instance s:
S argmin c²(s)-
(1)
fEJ.
For the Traveling Salesman Problem (TSP), F. is the set of all the tours that visit each node exactly once and returns to the starting node at the end, and c, calculates the cost for each tour f E F, by summing up the edge weights in the tour. The size of F, for TSP is n! for graph with nodes. For the Maximal Independent Set (MIS) problem, F, is a subset of the power set S. = {0. 1}" and consists of all the independent subsets where each node of a subset has connection to any other node in the same subset, and c, calculates the negation of the size of each independent subset.
We parameterize the solution space with a continuous and differentiable vector 0 E RDV. where V. denotes the variables in the problem instance (c.g., edges in TSP and nodes in MIS), and estimates the probability of each feasible solution f as:
V.l
pf 8) x exp
Σ ft Sc-0.)
subject to fE F..
(2)
where pe is an energy function over the discrete feasible solution space, f is a IV. -dimensionnll vector with element f. E {0, 1} indicating whether the 7thh variable is included in feasible solution f.
and the higher value of 0, means a higher probability for the 2hh variable produced by po(f s).
3.2 Gradient-Base Optimization
When the combinatorial problem is locally decomposable, such MIS, a penalty loss added to suppress the unfeasible solutions, e.g.:
34
can be
E (0 ()s)
Σ FES.
[po(f (s) (co(f) + 1(f & F.)))
3

---

where B > maX Ca(f). The objective function fands can thus be calculated analytically and enable end-to-end training. However, this is not always possible for general structured combinatorial problems such as TSF Therefore, we propose to directly optimize the expected cost over the underlying population of feasible solutions, which is defined as:
( () Eype [f)
Optimizing this objective requires efficient sampling, with which REINFORCE- based 71 gradient estimation be calculate. Nevertheless, common practice to sample from the energy pe functions requires MCMC [47] which is not efficient enough. Hence we propose to design an auxiliary
distribution qo over the feasible solutions Fs, such that the following conditions hold: 1) sampling
from Qo is efficient, and 2) qo and po should convergence to the same optimal 0" Then, we can replace po by go in our objective function as:
( 8) EEn [c,(f)),
(5)
and get the REINFORCE-basse update rule as:
Va (c)( = E ((c b(s)) log (o());:
(6)
where b(s) denotes a baseline function that does not depend on f and estimates the expected cost to reduce the variance of the gradients. In this paper, proposed by Kool et al. (43]
sampling-bass -baed baseline function
Next, we specify the auxiliary distributions for TSP and MIS, respectively. For brevity, we omit the conditional notations of for all probability formulas in the rest of the paper.
3.2.1 Auxiliary Distribution for TSP
For TSP on an n-node graph, each feasible solution f consists of n edges forming tour, which can be specified as a permutation f of n nodes, where (0) f is the start/end node, and n ( # Ty (J) for any i.j with 0 S i,j and / j. Note that for single solution f. n different choices of the start node (0) correspond start node n (0) randomly with uniform distribution:
different permutations rT.. In this paper, we choose
(TSP(TT(() = = for any node j;
(7)
d
TSP
(f)
=
@TSp(Ty (0) = j).
(8)
j=0
Given the start node (0), we factorize the probability via chain rule in the visiting order:
x-1
@TS((T (0)
II
QTSP (T) (5(<5)) i)).
Since the variables in TSP are edges, we let 0i, denote the 0 value of edge from node i to node j for notational simplicity, i.e., use matrix 0 E gnnx n to parameterize the probabilistic distribution of n! discrete feasible solutions. We define:
(xp(Oa)(i-1))
Crsp ( [)(( E cxp(0n
(10)
Here higher valued 0G,, corresponds to higher probability for the edge from node i to node j to be sampled. The compact, continuous and differentiable space of & allows us to leverage gradient- based optimization without costly MDP-based construction of feasible solutions, which has been bottleneck for scaling up in representative DRL solvers so far. In other words, we also no longer need costly MCMC-based sampling for optimizing our model due the chain-rule decomposition. Instead, we use autoregressive factorization for sampling from the auxiliary distribution, which is faster than sampling with MCMC from the distribution defined by the energy function.
*TSP has global constraint of forming Hamiltonian cycle.

---

3.2.2 Auxiliary Distribution for MIS
For the Maximal Independent Set (MIS) problem, the feasible solution is a set of independent nodes, which means that none of the node has any link to any other node in the same set. To ease the analysis, we further impose constraint to the MIS solutions such that each set is not proper subset of any other independent set in the feasible domain.
To enable the chain-rule decomposition in probability estimation, we introduce a as an ordering of the independent nodes in solution f. and {a}s as the set of all possible orderings of the nodes in The chain rule applied to a can thus be defined as:
MIS 90
(f)
Σ aEfaht
(M)s(a),
(11)
[a|
|a
qais(a; aci) II exp(Oa:)
MMIS (a) = II
Σ L)e((a))) (xp((e)))))()) exp(0,)
where ((azs) denotes the of available nodes for growing partial solution (a1,.... 0;-1), i.e. the nodes that have no edge to any nodes in (a1..... 04-1). J. Notice again that the parameterization space for MIS 0 E R² (where n denotes the number of nodes in the graph) compact, continuous and differentiable, which allows efficient gradient-driven optimization.
Due to the space limit, we leave the proof of the convergence between po and go (i.e., TSP and do MiS) to the appendix.
3.3 Meta-Learning Framework
Model-Agnostic Meta-Learning (MAML) 18 is originally proposed for few-shot learning. In the MAML framework, a model is first trained on collection of tasks simultaneously, and then adapts its model parameters to each task. The standard MAML uses second-order derivatives in training, which are costly to compute. To reduce computation burden, the authors also propose first-order approximation that does not require second-order derivatives.
Inspired by MAMI,, we train graph neural network (GNN) over collection of problem instances in way that the it can capture the common nature across all the instances, and adapt its distribution parameters effectively to each instance based on the features/structure of each input graph. Let F& be the graph neural network with parameter $, and denote by K, the input features of an instance graph collection C, by A, the adjacency matrix of the input graph, and by 0, = F& (x.. A.) the instancesspecife initialization of distribution parameters. The vanilla loss function is defined as the expected cost of the solution for any graph in the collection as:
C( + C) = Eg
Ey (Ks. A.)).
(12)
The gradient-based updates can thus be written
V C( C) = EFEC [ Vo, (0,)) EvEC FoF A.) (0,))(00))
(13)
where Vo, Eg (0,) is estimated using the REINFORCE algorithm (Equation 6 Since E, does not depend on the ground-truth labels, test instance with REINFORCE-based updates, which is referred to as active search 7
further fine-tune neural network parameters each single
Specifically, the fine-tuned parameters Φ is computed using one or more gradient updates for each graph instance For example, when adapting to a problem instance using T gradient updates with learning rate a, we have:
(0)
(1))
(t--1) a
t L(D!!
(1)))
{s))
for 151ST,
(14)
0 Fn (K, A.).
(15)
Here we use AdamW [50] in our experiments. Next, we optimize the performance of the graph neural network with updated parameters (i.e., ((T)) with respect to $ with a meta-objective:
Lmeta (C) = Esece, ( 8),
(16)
5

---

Algorithm MAML in DIMES
Input: p(C): distribution over CO problem instances
Input: step size hyperparameiers
1: randomly initialize +b
2: while not done
3: Sample batch of graph instances c; p(C)
4: for all do
5: Sample K solutions D; (f1, f2.......... fx) using QR. (K, for Cj
6: Evaluate (FL A.)) using D in Equation 13
7: Compute adapted parameters with Equation 14
$ CradDescent Sample K solutions D' = f'.......... f2..... ... using OF (T) (M..A.) for c;
8:
9:
end for Update - Addmm Eneene Volg( ae (K.. Ak))) using each Di in Equation
end while
and calculate the meta- meta- updates as:
V mmeta +
C)
Esec
V V o
(17)
Bsec
V V (m) A.) V o &
Notice that we adopt the first-order approximation to optimize this objective, which ignores the update via the gradient term of V&C($ {s}). We defer the derivation of the approximation formula to the appendix. Algorithm| | illustrates the full training process of our meta-learning framework.
3.4 Per-Instance Search
Given fine-tuned (i.c., after active search) continuous parameterization of the solution space !!7) the per-instance search decoding aims to search for feasible solution that minimizes the cost function In this paper, adotp three decoding strategies, i.e., greedy decoding, sampling, and Monte Carlo tree search. Due to the space limit, the detailed description three decoding strategies can be found in the appendix.
3.5 Graph Neural Networks
Based the shape of the differentiable variable 0 required by each problem (i.e., R=** for TSP and R" for MIS), we use Anisotropic Graph Neural Networks [9] and Graph Convolutional Networks 40 the backbone network for TSP and MIS tasks, respectively. Due to the space limit, the detailed neural architecture design can be found in the appendix.
Experiments
4.1
Experiments for Traveling Salesman Problem
4.1.1
Experimental Settings
Data Sets The training instances are generated on the fly. We closely follow the data generation procedure of previous works, e.g., 42 We generate 2-D Euclidean TSP instances by sampling each node independently from a uniform distribution over the unit square. The TSP problems different scales named TSP-500/ SPP-500010000 1000000000000000000000 respectively, where TSP-n indicates the TSP instance on nodes. For testing, we use the test instances generated by Fu et al. [9]. There are 128 test instances in each of TSP-500/1000, and 16 test instances in 10001
Evaluation Metrics For model comparison, we report the average length (Length), average per- formance drop (Drop) and averaged inference latency time (Time), respectively, where Length (the shorter, the better) the average length the system-predicted tour for each test-set graph, Drop (the smaller, the better) is the average of relative performance drop in terms of the solution length compared to baseline method, and Time (the smaller, the better) is the total clock time for generating solutions for all test instance, in seconds (s), minutes (m), or hours (h).

---

Table 1: Results of TSP. See Section 4.1.2 for detailed descriptions. iidicctess the baseline for computing the performance drop. Results of baselines (except those of EAS and the running time of LKH-3, POMO, and AttGGNN) are taken from Fu al. [9]
TSP 500
TSP 1000
10000 TSP TSP-10000
Method
Type
I Length 4
Drop
Time
Length
Drop
Time
Length
Drop-
Time
Concorde
(exact)
37.66m
23.12
6.65h
N/A
N/A
Gurobi
OR (exact)
16.55
0.00%
45.63h
NIA
NIA
NIA
N/A
N/A
N/A
LK11-3 (default)
OR
16.55
0.00%
46.28m
23.12
0.00%
2.57h
71.77
8.8h
I.KH.3 (less trails)
OR
16.55
0.00%
3.03m
23.12
0.00%
7.73m
71.79
51.27m
Ncarest Insertion
OR
20.62
24.59%
Os
28.96
25.20%
Os
90,51
26.11%
66
Insertion
12.98%
Farthest Insertion
OR
18.30
10.57%
Os
25.72
11.25%
Os
80.59
12.29%
65
EAN
RL4S
28.63
73.03%
20. 18m
50.30
117.59%:
37.07m
N/A
N/A
N/A
EAN
RLAS++-OPT
23.75
43.57%
57.76m
47.73
106.469%
5,39h
N/A
N/A
NA
501.27%
AM
RI.G
20.02
20.99%
1.51m
31. 15
34.75%
3.18m
141.68
97.39%
5.99m
RL+BS
19.53
18.03%
21.99m
29.90
29.23%
1.64h
129.40
80.28%
18th
GCN
SL+G
29.72
79.61%
6.67m
48.62
110,29%
28.52m
N/A
N/
N/A
GCN
SL+BS
30.37
83.55%
38 38.02m
$1.26
121.73%.
51.67m
N/A
NA
N/A
POMO#EAS Fimm
REAAS
19.24
16.25%
12,80h
NIA
NIA
NIA
N/A
N/A
N/A
POMO+EAS-Lay
RL+AS
19.35
16.92%
16.19h
N/A
N/A
NIA
N/A
N/A
N/A
POMOHEAS Tah
49.56
Att-GCN
SL+MCTS
16.97
2.54%
2.20m
23.86
3.22%
4.10m
74.93
4.39%
21 49m
RL+G
18.93
14.38%
0.97m
26.58
14.97%
2.08m
86.44
20.44%
4.65m
RL+AS=G
17.81
7.61%
2.10h
24.91
7.74%
4,49h
80.45
12.09%
3.07h
DIMES (ours)
RI
17.80
7.55%
2.1
24.89
7.70%
4,53h
80.42
12.05%
3.12h
RLAMCTS
16.87
1.93%
2.92m
23.73
2.64%
6.87m
74.63
3.98%
19.83m
RL+AS-MCTS
16.84
1.76%
2.15h
23.69
2.46% %
4.62h
74.06
3,19%
3.57h
Table 2: Ablation study TSP-1000.
(a) On meta-lcarning (T 10).
(b) On fine-tuning parts (T 5).
Inner updates
Fine Fine-tuning
Length
Part
Length
27.11
Cont. Param.
27.73
26.58
MLP
26.75
GNNOut-MLP
24.91
GNN+MLP
26.81
(d) On heatmaps for MCTS.
(c) On inner update steps T'.
Heatmap
Longth
T
10
12
14
Unif(O, 1)
25.52
1/(r: +1)
24.14
Length
25.79
25.28
25.08
25.08
24.97
24.91
At-GCN
23.86
DIMES (ours)
23.69
Training and Hardware
Due to the space limit, please refer the appendix.
4.1.2 Main Results
Our main results are summarized in Table D with 15 for TSP-500, 14 for T0P- and T' 12 for TSP-10000. We use a GNN followed by MLP the backbone, whose detailed architecture is defered to the appendix. Note that we fine-tune the GNN output and the MLP only. For the evaluation of DIMES, we fine-tune the DIMES on each instance for 100 steps (TSP-500 TSP-1000) or for 50 steps (TSP-10000). For the sampling in DIMES, we use the temperature for DIMES+AS+S. We compare DIMES with 14 other
parameter 0.01 for DIMES+S and TSP solvers on the same test sets. We divide those methods into two categories: traditional OR methods and learning- based methods.
Traditional operations research methods include two exact solvers, i.e., Concorde [4] and Gurobi 21), and a strong heuristic solver named L.KH-3 (23.. For LKH-3, we consider two settings: (i) defaulr: following previous work [4], we perform runs with maximum of 10000 trials (the

---

Table 3: Results of various methods on MIS problems. Notice that we disable graph reduction and 2-opt local search in all models for a fair comparison, since it is pointed out by [8] that all models would perform similarly with a local search post-processing. See Section 4.2.2 for detailed descriptions. indicates the baseline for computing the performance drop.
SATLIB Drop 4
ER 1700 800]
ER 19000 11000]
Mathod
Type
Size
Time
Size f
Dmo 4
Time
Size
Drop 4
Time
KaMIS
OR
425.96"
37.58m
44.87
52.13m
381.31
7.6h
Gurobi
425.95
26.00m
41.38
7.78%
50.00m
N/A
Intel
SL+TS
N/A
N/A
N/A
38.80
13.43%
20.00m
N/A
NIA
N/A
Intel
SL+G
420.66
1.48%
23.05m
34,86
22.31%
6.06m
284.63
25.35%
5.02m
DGL
SL+TS
N/A
N/A
N/A
37.26
16.96%
22.71m
NIA
N/A
N/A
LwD
RL+S
422.22
0.88%
18.83m
41.17
8.25%
6.33m
345.88
9.29%
7.56m
DIMES (ours)
RL+G
421.24
1.11%
24. 17m
38.24
14.78%
6.12m
320.50
15.95%
5.21m
DIMES (ours)
RL+S
423,28
0.63%
20.26m
42,06
6.26%
12.01m
332,80
12.72%
12.51m
default configuration of LKH-3); (ii) less trials: we perform 1 run with maximum of 500 trials and 250 trials for TSP-10000, so that the running times of LKH-3 match those of DIMES+MCTS. Besides, also compare DIMES against simple heuristics, including Nearest, Random, and Farthest Insertion.
for
Learning-basee methods include 8 variants of the 4 methods with the strongest results in recent benchmark evaluations, namely EAN (13), AM 44.. GCN [31, POMO+EAS (28), and Att-GCN [9], respectively. Those methods can be further divided into the reinforcement learning (RL) sub-category and the supervised learning (SL) sub-category. Some reinforcement learning methods can further adopt an Active Search (AS) stage to fine-tune on each instance. The results of the baselines except the running time of Att-GCN are taken from Fu et al. [19]. Note that baselines are trained on small graphs and evaluated on large graphs, while DIMES can be trained directly on large graphs. We re-run the publicly available code of Att-GCN our hardware to ensure fair comparison of time.
The decoding schemes in each method (if applicable) are further specified Greedy decoding (G), Sampling (S), Beam Search (BS), and Monte Carlo Tree Search (MCTS). The 2-OPT improvements 11 can be optionally used to further improve the neural network-gent generrteeeee solution via heuristic local search. See Section 3.4 for a more detailed descriptions of the various decoding techniques.
As is shown in the table, DIMES significantly outperforms many previous learning- based methods. Notably, although DIMES is trained without any ground truth solutions, it is able to outperform the supervised method. DIMES also consistently outperforms simple traditional heuristics. The best performance is achieved by RL+AS+MCTS, which requires considerably more time. RL+AS+G/S faster than RL+AS+MCTS and are competitive to the simple heuristics. Removing AS in DIMES shortens the rumning time and leads to only a slight, acceptable performance drop. Moreover, they still better than many previous learning-based methods in terms of solution quality and inference time.
4.1.3 Ablation Study
To study the efficacy of meta-learning, we consider two dimensions of ablations: (i) with without inner gradient updates: whether to use f A.) or O!T)) in the objective function; (ii) with or without fine-tuning in the inference phase. The results on TSP- 1000 with training phase
On Meta-Learning
T = 10 and greedy decoding are summarized in Table Both inner updates and fine-tuning are
crucial to the performance of our method. That is because meta- meta-learning helps the model generalize across problem instances, and fine-tuning helps the trained model adapt to each specific problem instance.
On Fine- Tonne-Tningg Parts We study the effect of fine-tuning parts during both training and testing. In general, the neural architecture we used is a GNN appended with an MLP, whose output is the continuous parameterization
We consider the following fine-tuning parts: (i) the continuous parameterization (Cont. Param.); (ii) the parameter of MIP: (iii) the output of GNN and the parameters of MI.: (iv) the parameters of GNN and MI.. Table 2b summarizes the results with various fine-tuning parts for TSP-1000 with training phase T = 5 and greedy decoding. The result
8

---

demonstrates that (iii) works best. We conjecture that (iii) makes nice trade-off between universality and variance reduction.
On Inner Gradient Update Steps We also study the effect of the number T of inner gradient update steps during training. Table shows the test performance on TSP-1000 by greedy decoding with various T's. As the number of inner gradient updates increases, the test performance improves accordingly. Meanwhile, more inner gradient update steps consumes more training time. Hence, there is trade-off between performance and training time in practice.
shows
On Heatmaps for MCTS To study where continuous parameterization of DIMES is essential to good performance in MCTS, we replace it with the following heatmaps: (i) each value is independently sampled from (0, 1): (ii) 1/(r, + 1), where r; denotes the rank of the length of the i-th edge among those edges that share the source node with it. This can be regarded as an approximation to the nearest neighbor heuristics. We also compare with the Att-GCN heatmap [9]. Comparison of continuous parameterizations for TSP-1000 by MCTS is shown in Table 2 The result confirms that
the DIMES continuous parameterization does not simply learn nearest neighbor heuristics, but can identify non-trivial good candidate edges.
4.2 Experiments For Maximal Independent Set
4.2.1 Experimental Settings
Data Sets We mainly focus on two types of graphs that recent work [48] 1| shows struggles against, i.c., Erdōs-Róng Rényi (ER) graphs (16) and SATLIB (25), where the latter is a set of graphs reduced from SAT instances in CNF. The ER graphs of different scales are named and ER-[9000-1 1000J, where [R-[n-N] indicates the graph contains n to N nodes. The pairwise connection probability p is set 0.15 and 0.02 for ER-[700-800] and ER-[9000- 11000, respectively. The 4,096 training and 5,00 test ER graphs are randomly generated. For SATLIB, which consists of 40,000 instances, of which we train on 39,500 and test on 500. Each SAT instance has between 403 to 449 clauses. Since we cannot find the standard train-test splits for both SAT and ER graphs datasets, we randomly split the datasets and re-run all the baseline methods.
(RR-[70--000
To compare the solving ability of various methods, we report the average size of the independent set (Size), average performance drop (Drop) and latency time (Time), respectively, where Size (the larger, the better) is the average size of the rystem-predictee maximal independent set for each test-set graph, Drop and Time are defined similarly as in Section 4.1.1
Evaluation Metrics
Training and Hardware
Due to the space limit, please refer to the appendix.
4.2.2 Main Results
Our main results are summarized in Table 3, where our method (last line) is compared 6 other MIS solvers on the same test sets, including two traditional OR methods (i.e., Gurobi and KaMIS) and four learning-based methods. The active search is not used for MIS evaluation since our preliminary experiments only show insignificant improvements. For Gurobi, we formulate the MIS problem as integer linear program. For KaMIS, we use the code unmodified from the official repository The four learning-basse based methods can be divided into the reinforcement learning (RL) category, i.e..
S2V-DQN [36] and LwD (I] and the supervised learning (SL) category, i.e., Intel [48 and DGL [8]
We produced the results for all the learning- baased methods by running integrated implementation
provided by Böther et al. [8. Notice that as pointed out by Böther et al. [8]. the graph reduction
and local 2-opt search 3 can find near-optimal solutions even starting from a randomly generated
solution, so we disable the local search or graph reduction techniques during the evaluation for all
learning based methods to reveal their real CO-solving ability. The methods that cannot produce results in the 10x time limit of DIMES are labeled as N/A.
As is shown in Table 3 our DIMES model outperforms previous baseline methods on the medium- scale SATLIB and ER (00--000 datasets, and significantly outperforms the supervised baseline (i.e.,
httpp://ggtaah.ccccaa/arrerreres (MIT License)
(No License)

---

Intel) on the large-scale ER-[9000- 1000] setting. This shows that supervised neural CO solvers cannot well solve large-scale CO problem due the expensive annotation problem and generalization problem. In contrast, reinforcement-lerrning methods are a better choice for large-scale CO problems. We also find that LwD outperforms DIMES on the large-scale ER-[9900-- 1000] setting. We believe this is because LwD is specially designed for locally decomposable CO problems such as MIS and thus can use parallel prediction, but DIMES are designed for general CO problems and only uses autoregressive factorization. How to better utilize the fact of local decomposability of MIS-like problems is one of our future work.
Conclusion & Discussion
Scalability without significantly scarifying the approximation accuracy is critical challenge in combinatorial optimization. In this work we proposed DIMES, differentiable meta solver that is able to solve large-scale combinatorial optimization problems effectively and efficiently, including TSP and MIS. The novel parts of DIMES include the compact continuous parameterization and the meta-learning strategy. Notably, although our method is trained without any ground truth solutions, is able to outperform several supervised methods. In comparison with other strong DRL solvers on TSP and MIS problems, DIMES can scale up graphs with ten thousand nodes while the others either fail to scale up, or can only produce significantly worse solutions instead in most cases.
Our unified framework is not limited to TSP and MIS. Its generality is based on the assumption that each feasible solution of the CO problem on hand can be represented with 0/1 valued variables (typically corresponding the selection of subset of nodes or edges), which is fairly mild and generally applicable to many CO problems beyond TSP and MIS (see Karp's s 21 NP-complete problems (35)) with few modifications. The design principle of auxiliary distributions is to design autoregressive model that can sequentially grow valid partial solution toward valid complete solution. This design principle also proven be general enough for many problems neural learning, including CO solvers. There do exist problems beyond this assumption, e.g., Mixed Integer Programming (MIP), where variables can take multiple integer values instead of binary values. Nevertheless, Nair et al. (56) showed that this issue can be addressed by reducing each integer value within range [U] to sequence of [log2 U] bits and by predicting the bits from the most to the least significant bits. In this way, multi-valued MIP problem can be reduced to a ettary-valued MIP problem with more variables.
One limitation of DIMES is that the continuous parameterization is generated in one-shot without intermediate steps, which could potentially limit the reasoning power of method, is shown in the MIS task. Another limitation is that applying DIMES to a broader ranges of NP-complete problems that variables can take multiple values, such as Mixed Integer Programming (MIP), is non-trivial and needs further understanding of the nature of the problems.
10

---

References
[1] Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum in- dependent sets. In International Conference Machine Learning, pages 134-144. PMLR, 2020.
[2] Ismail R Alkhouri, George K Atia, and Alvaro Velasquez. A differenniable approach to combinatorial optimization using dataless neural networks. arXiv preprint arXiv:2203.08209 2022.
[3] Diogo V Andrade, Mauricio GC Resende, and Renato F Werneck. Fast local search for the maximum independent set problem. Journal of Heuristies, 18(4):525-547 2012.
[4] David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver. https://www math.
html 2006.
[5] Sanjeev Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of 37th Conference on Foundations of Computer Science, pages 2-11.
IEEE, 1996.
[6] Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), 91))61163, 1962.
[7] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv: /61 1et:::1111900000 1.09940, 2016.
[8] Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning tree search for combinatorial optimization. In International Conference on Learning Representations, 2022. URL htttps://openneview..ng. net/forum?
id=mkOHzdgY771
[9] Xavier Bresson and Thomas Laurent. experimental study neural networks for variable graphs. In ICLR 2018 Workshop, 2018
[10] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 6281-6292, 2019.
[11] Georges A Croes. method for solving traveling-salennn salesman problems. Operations research, 10)799-811,, 1958.
[12] Paulo R de O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-OPT heuristics for the traveling salesman problem via deep reinforcement learning. arXiv preprint arXiv:2004.01 01000 2020.
[13] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the TSP by policy gradient. In International conference on the integration of constraint programming, artificial intelligence, and operations research, pages 170-181. Springer, 2018.
[14] 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. IEEE, 2020.
[15] Stefan Elfwing, Eiji Uchibe, and Kenji Doya. higmoid-weighenn linear units for neural network function approximation in reinforcement learning. Newral Networks, 107:3-11, 2018.
[16] Paul Erdós, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1): 1960.
[17] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning Graphs and Manifolds, 2019.

---

[18] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnoste meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning. pages 1126-11 126--133. PMLR, 2017.
[19] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large TSP instances. arXiv preprint arXiv:2012.10658, 2020.
[20] Teofilo F Gonzalez. Handbook of approximation algorithms and metaheuristics. CRC Press, 2007.
[21] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2018.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[23] K. Helsgaun. An extension of the Hin-Keemighan-HHllgaam TSP solver for constrained traveling salesman and vehicle routing problems. Technical report, Roskilde University, 2017.
[24] Keld Helsgaun. An effective implementation of the Kernigann traveling salesman heuristic. European journal of operational research, 126(1):106-130) 2000.
[25] Holger H Hoos and Thomas Stützle. SATLIB: An online resource for research on SAT. Sat, 2000:283-291 2000.
[26] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. arXiv preprint arXiv: 2019.
[27] 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.
[28] André Hottung, Yeong-Dae Kwon, and Kevin Tiemney Efficient active search for combinatorial optimization problems. arXiv preprint 20V:22266051266 2021.
(29) Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint a 10.05291, 2021.
[30] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448 456. PMLR, 2015.
[31] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint (xXiv:1906.01220 2019.
[32] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. On learning paradigms for the travelling salesman problem. arXiv preprint arXiv: /9/0.00//0.22//// 2019.
[33] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bresson. Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.0777 07054, 2020.
[34] Nikolaos Karalias and Andreas Loukas. Erdōs goes neural: An unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33:6659 6672, 2020.
[35] Richard M Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85 103, 1972.
[36] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, 30: 2017.
12

---

[37] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve NP-hard routing problems. Advances in Neural Information Processing Systems, 34, 2021.
[38] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint urXiv:/412.690 2014.
[39] Diederik P Kingma and Max Welling. Auto-encoding variational Bayes. arXiv preprint arXiv:1312.6114, 2013.
[40] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1oXi::/60000290) 2016.
[41] Vijay R Konda and John N Tsissiklis. Actor-critic algorithms. In Advances in neural information processing systems, pages 1008-1014, 2000.
[42] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn solve routing problems! In International Conference on Learning Representations, 2019.
[43] Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 REINFORCE samples, get baseline for free! In Deep Reinforcement Learning Meets Structured Prediction, ICLR 2019 Workshop, 2019.
[44] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. arXiv preprint arXiv:2102.11756, 2021.
[45] Yeong-Dac Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. arXiv preprint arXiv:2010. /60/ 2020.
[46] Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- tion Processing Systems, 34, 2021.
[47] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and F Huang. A tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
[48] 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.
[49] Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling-salesmar problem. Operations research, 21(2):498-516, 1973.
[50] llya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[51] Hao Lu, Xingwen Zhang, and Shuang Yang. A bearning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
[52] Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial opti- mization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv:191i.04936. 2019.
[53] 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 in Neural Information Processing Systems, 34, 2021.
[54] John W Moon and Leo Moser. On cliques in graphs. Israel journal of Mahhemtics, 3(1):23-28, 1965.
[55] Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted Boltzmann machines. In Icml, 2010.
13

---

[56] Vinod Nair. Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja. Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.133: 13349, 2020.
[57] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V Snyder, and Martin Takáč. Rein- forcement learning for solving the vehicle routing problem. arXiv preprint 1rXiv:180.004240. 2018.
[58] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv: (803,02900009999 2018.
[59] Wenbin Ouyang, Yisen Wang, Shaochen Han, Zhejian Jin, and Paul Weng. Improving gener- alization of deep reinforcement learning-basee tsp solvers, arXiv preprint arXiv:2 10.00244,, 2021.
[60] Christos H Papadimitriou. The Euclidean travelling salesman problem is NP-complete. Theo- retical computer science, 4(3):237 244, 1977.
[61] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[62] 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 Vitooo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Py PyTorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[63] Bo Peng. Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dy- namic attention model for vehicle routing problems. In International Symposium on Intelligence Computation and Applications, pages 636-650. Springer, 2019.
[64] Colin Reeves. Modern heuristics techniques for combinatorial problems. Nikkan Kogyo Shimbun, 1997.
[65] Paul Shaw. A new local search algorithm providing high quality solutions to vehicle routing problems. APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scorland, UK, 46, 1997.
[66] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
[67] Natalia Vesselinova, Rebecca Steinert, Daniel F Serez-Ramirez, and Magnus Boman. Learning combinatorial optimization graphs: A survey with applications to networking. IEEE Access, 8:120388- 1720388-120416, 2020.
[68] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems, 28:2692-2700, 2015.
[69] Chenguang Wang, Yaodong Yang, Oliver Slumbers, Congying Han, Tiande Guo, Haifeng Zhang, and Jun Wang. A game-the approach for improving generalization ability of TSP solvers. arXiv preprint arXiv:2110.15105 2021.
[70] Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang, Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization on graphs. arXiv preprint arXiv:2106.04922 2021.
[71] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229 2566, 1992.
[72] Yaoxin Wu, Wen Song. Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems.. IEEE Transactions on Neural Networks and Learning Systems, 2021.
14

---

[73] 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, 2021.
[74] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with Lin- Kenn-Kennghan Heliaauu heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34, 2021.
[75] Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. In NeurlPS, pages 7990-8001, 2019.
[76] Cong Zhang, Wen Song, Zhiguang Cao. Jie Zhang, Puay Siew Tan, and Chi Xu. Learning to dis- patch for job shop scheduling via deep reinforcement learning. arXiv preprint arXiv:2010.125: 2020.
[77] Jiongzhi Zheng. Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Combining reinforcement learning with Lin- Hrriighann-Hlsgaunn algorithm for the traveling salesman problem. arXiv preprint arXiv:2012.04461, 2020.
15

---

Checklist
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) Did you describe the limitations of your work? [Yes] See Section S
(c) Did you discuss any potential negative societal impacts of your work? [N/A] No obvious negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
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] See Appendix C.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] No previous work reports error bars.
(d) Did you include the total amount compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix C.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
No new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] They are publicly available.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] No such content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "H2NQ-lK9GmK", "reviewer": "Reviewer_fe3B", "summary": "The paper proposed DIMES, a framework for tackling graph-based combinatorial optimisation problems with reinforcement learning.  DIMES runs a graph neural network to produce a heatmap over the candidate variables (edges for TSP, nodes for MIS) which corresponds to a policy for which variable to select next from any given position.  This approach seeks to provide more scalable CO solvers as solutions can be efficiently sampled from a generated heatmap with minimal additional overhead.  Compared to prior works, DIMES primary claims of novelty are (i) the process does not require supervised data to generate the heatmaps and (ii) that DIMES can be trained, using meta-learning, on a distribution of instances such that it can quickly and efficiently specialise during active search on a singe instance.  In experiments on TSP and MIS, DIMES is shown to perform competitively or better than the considered RL/SL baselines and remain efficient even on large problem sizes.\n", "questions": "- Regarding the fine-tuning of DIMES in table 1: (i) Is the fine-tuning time included in the run time (I would have expected so, but then I am surprised how, for example, DIMES is faster the AM with equivalent settings if it has to be fine-tuned first)? (ii) Which elements of the model are fine-tuned (as four variants are show in Table 2(b) it is clear there is some choice to be made)?\n- If all baselines were taken from Fu et al, can you comment on whether the training of these was a fair comparison to DIMES?  For example, DIMES is trained on the target problem sizes but it is common to present results on larger TSP instances of models trained on smaller problems.\n- In the meta-learning ablations, why would training the network using meta-learning (targeted to give good performance after T steps of fine-tuning on a specific instance), give better performance when T=10 during training and T=0 at inference (i.e why is row 2 of Table 2a better than row 1?)\n- Why is S2V-DQN not used as a baseline in Table 3, when it is stated to be a baseline on line 297?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\nThe problem tacked — scalable RL approaches for CO — is significant and well motivated.  Improvements in performance and scalability of are of interest to the community.\n\nAs it is typically intractable to produce optimal solutions to NP-hard CO problems, the efficient sampling of candidate solutions and active search on a target instance at test time important components of many approaches.  In this context, the demonstrated efficacy meta-learning good starting points for the agent from which to fine-tune is interesting.  Whilst it was also novel to my knowledge, a quick search did show that the authors might want to consider softening their claim (line 51) that \"we are the first to apply meta-learning over a collection of CO problem instances” (e.g. https://arxiv.org/abs/2105.02741).\n\nThe experimental results appear impressive, though I have some points of concern or that require clarification (see below) before I can fairly judge these.\n\n*Weaknesses*\n\nI am not convinced by the authors claim that DIMES “introduces a compact continuous space for parameterizing the underlying distribution of candidate solutions” is novel or significant, nor that this new approach “addresses the scalability challenge in large-scale combinatorial optimization” more so than previous works.  Ultimately, DIMES is predicting a heatmap with a single pre-processing step of the entire problem instance (graph), which then guides some search process (greedy, sampling, MCTS etc).  Whilst the paper contrasts DIMES to previous works with “we introduce a compact continuous space for parameterizing the underlying distribution of candidate solutions” — it seems to me that this is just different language for talking about a heatmap which, by the authors admission, many previous works have already used.  The authors note that previous heatmap approaches were not pure RL (relying on some labelled data), however applying RL for TSP well established and having that agent output a heatmap instead of, say, embeddings that implicitly define a heatmap via attention, or running a full inference at each step is a straightforward modification that doesn’t appear to rely on any architectural or theoretical insights.\n\nWhilst the paper is well written from a linguistic perspective, I do feel it loses clarity in the way it presents DIMES and draws contrasts with prior work where they may not be justified.  For example, “Instead of previous DIR-based CO sovles which rely on construction or improvement heuristics, we introduce a compact continuous space for parameterizing the underlying distribution of candidate solutions which allows massively parallel on-policy sampling”.  To me, DIMES is a construction heuristic (it starts at a node/edge, and then iteratively picks the next until a solution is found).  Moreover, the scalability does not come from any breakthrough regarding the compact continuous parameterisation space, but in essence because as much processing as possible (e.g. the expensive GNN) is restricted to single preprocessing step.  However, this is not a novel idea - even the authors own RL baselines for TSP - Joshi et al [24] and Kool et al [34] - use an expensive preprocessing step followed by fast action decoding.  In this vein, another work the authors may consider relevant is that of Driori et al (https://arxiv.org/pdf/2006.03750) who use dot-product attention between graph embeddings as an alternative parameterisation of a heatmap and demonstrate impressive performance on TSP (outperforming Farthest/2-opt heuristics on most “real world” graphs of up to ~125k nodes).\n\nI am concerned that certain more recent baselines may be missing, and that certain results may be missing from the experimental section.  Some points are listed here, but others are left as questions below where I feel I need more clarity.\n\n- The attention model of Kool et al [34] is used as an RL baseline.  However, this approach has been significantly improved in POMO (https://arxiv.org/abs/2010.16011) and then subsequently adapted for active search at test time (https://arxiv.org/abs/2106.05126).  Driori et al (above) is also a significantly scalable RL TSP solver that would seem to be an important baseline if DIMES is justify claims that they are contributing with regards to scalability.\n\n- The authors only rerun one of the presented baselines (Att-GCN) on their hardware, so timing results for other baselines taken from Fu et al are potentially misleading.\n\n- In Table 3, why is LwD with sampling (RL+S) not included?  As LwD is better than DIMES in greedy mode, but DIMES is better with sampling, would LwD with sampling not be expected to be best of all?", "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": "DtfZJx_gy-c", "reviewer": "Reviewer_dJ85", "summary": "This work proposes a novel DIMES framework (stands for differentiable meta solver) to tackle large-scale learning-based combinatorial optimization problems. The key novelties and contributions are 1) an RL-based approach to train the widely-used GCN model to generate probability heatmap, and 2) a meta-learning approach to further finetune the solutions at inference. Experimental results show that the proposed DIMES can achieve promising performance for large-scale TSP and MIS problems with up to 10,000 nodes.\n", "questions": "- DIMES needs to use RL to directly train deep GNN for large-scale problem instances with up to 100,000 nodes. Is there any challenge for such training? How long will DIMES take to converge for TSP500/1000/10000 (#training instances and wall-clock time)? \n\n- TSP/MIS is a good testbed for neural combinatorial optimization. But the real-world applications will typically have problems with various structures that can not be solved by classical solvers. This is an important motivation for learning-based solvers without domain knowledge. Can DIMES generalize to other routing problems such as those in the AM paper?\n\n- Citation [42] and [43] in the paper are for the same AM paper but with two different years (the 2019 one is correct). \n", "limitations": "Yes, the limitations have been adequately addressed in Section 5 Concluding Remarks. I do not see any potential negative societal impact of this work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n+ Learning to solve large-scale combinatorial optimization problems is crucial for many real-world applications. This work is a timely contribution to an important research topic.\n\n+ To my understanding, the proposed RL-based approach for training GCN to obtain the probability heatmap is novel. It is quite promising to see a pure end-to-end RL-based approach can tackle TSP with up to 10,000 nodes.\n\n+ The meta-learning based fine-tuning strategy is also new for neural combinatorial optimization.\n\n+ The experimental results on large-scale TSP are good.\n\n**Weaknesses:**\n\nI cannot give a clear acceptance to the current manuscript due to the following concerns:\n\n**1. Inaccurate Contribution:** One claimed contribution of this work is the compact continuous parameterization of the solution space. However, as discussed in the paper, DIMES directly uses the widely-used GNN models to generate the solution heatmap for TSP[1,2] and MIS[3] problems, respectively. The credit for compact continuous parameterization should be given to the previous work [1,2,3] but not this work.\n\nFor TSP, Joshi et al.[1] have systemactilly studied the effect of different solution decoding (e.g., Autoregressive Decoding (AR) v.s. Non-autoregressive decoding (NAR, the heatmap approach) and learning methods ( supversied learning (SL) v.s. reinforcement learning (RL)). To my understanding, the combination of AR + SL, AR + RL and NAR(heatmap) + SL have been investigated in Joshi et.al. and other work (e.g., PtrNet-SL, PtrNet-RL/AM, GCN), but I am not aware of othe work on NAR(heatmap) + RL. The NAR + RL combination could be the novel contribution of this work.\n\n**2. Actual Cost of Meta-Learning:** The meta-learning (meta-update/fine-tuning) approach is crucial for the proposed method's promising performance. However, its actual cost has not been clearly discussed in the main paper. For example, Table 1 reports that DIMES only needs a few minutes to solve 128 TSP500/TSP1000 and 16 TSP10000 instances. However, at inference, DIMES actually needs extra meta-gradient update steps to adapt its model parameters to each problem instance. The costs of the meta-gradient steps are 1.5h - 10h for TSP500 to TSP10000 as reported in Appendix C.1. Since all the other heuristic/learning methods do not require such meta update step, it is unfair to report that the runtime of DIMES is only a few minutes (which should be a few hours) in Table 1.\n\n**3. Generalization v.s. Testing Performance:** To my understanding, all the other learning-based methods in Table 1 are trained on TSP100 instances but not TSP500-TSP10000 as for DIMES. Therefore, the results reported in Table 1 are actually their out-of-distribution generalization performance. There are two important generalization gaps compared with DIMES: 1) generalization from TSP100 to TSP10000, 2) generalization to the specific TSP instances (the fine-tuning step in DIMES). I do see it is DIMES's own advantages (direct RL training for large-scale problems + meta fine-tuning) to overcome these two generalization gaps, but the difference should be clearly clarified in the paper. \n\nIn addition, it is also interesting to see a comparison of DIMES with other methods on TSP100 (in-distribution testing performance) with/without meta-learning.\n\n**4. Advantage of NAR(heatmap) + RL + Meta-Learning:** From Table 1&2, for TSP1000, the generalization performance of AM (G: 31.15, BS: 29.90) trained on TSP100 is not very far from the testing performance of DIMES without meta-learning (27.11) directly trained on TSP1000. It could be helpful to check whether the more powerful POMO approach[4] can have a smaller performance gap. Reporting the results for POMO and DIMES without meta-learning for all instances in Table 1 could make the advantage of the NAR(heatmap) + RL approach in DIMES much clearer.\n\nHottung et al.[5] shows that POMO + Efficient Active Search (EAS) can achieve promising generalization performance for larger TSP instances on TSP and CVRP. The comparison with POMO + EAS could be important to better evaluate the advantage of meta-learning in DIMES.\n\n[1] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bresson. Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.07054,2020.\n\n[2] 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.\n\n[3] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. NeurIPS 2018.\n\n[4] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. NeurIPS 2020.\n\n[5] André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. ICLR 2022.\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": "2J0haKZfP9v", "reviewer": "Reviewer_LJJE", "summary": "This paper studies a differential meta solver for CO problems and its performance is demonstrated by using TSP instances (size 500, 1000, and 10000). The difference between the proposed method in this paper and existing DRL-based methods is from the fact that DIMES focuses on a parameterized continuous space to represent solutions of CO problems. Experimental results indicate that DIMES show better performance than DRL-based solvers. Ablation studies on DIMES show that the proposed components work effectively.", "questions": "- I feel that the proposed concept is interesting to investigate, and I'm interested in how to design auxiliary functions (this is also noted in sec.5 by the authors). I also read proofs in the supplemental material. I wonder if we can design such functions for various CO problems. The paper proposed the answer for TSP and MIS, but defining such functions (with proofs) seems to be challenging (as many variations on objective functions and constraints). If this is not straightforward (or this requires some hand-crafted works like parameter tuning), I feel that DIMES requires us to design such functions (this is similar to us designing good encoding-decoding scheme for DRL-based methods, good heuristics in OR, better algorithms, etc.).\n\n- In Table 1, LKH-3 with TSP-1000 requires 38.09[m] (this may be from Fu et al. [16] https://arxiv.org/pdf/2012.10658.pdf). Thus, it seems that the DIMES outperforms the famous heuristic solver. However, for example in Table 1 [https://arxiv.org/pdf/1402.4699.pdf] (Note that I do not want to say like `this paper is good/bad`, I just cite experimental results from this.), LKH-3 seems to solve TSP instances (size from 9847 to 16862) efficiently (from 381[s] to 976[s]). I wonder what is the differences between such traditional benchmark TSP instances (like ja9847) and those generated by Fu et al. [16] (TSP-1000/TSP-10000). This behavior is also seen in existing papers like AM's paper (LKH3 requires 21[m] to solve TSP-100). Such results (often reported in papers proposing learning-based solvers) seem to be strange to me. Could you please explain them?\n\n- For datasets, the authors mentioned two sources from [35] (train) and [16] (test). The difference and similarities of datasets among them should be explained.\n\n- Related to the previous question, I'm interested in the learned results that can be generalized to other instances. For example, TSP-1000 with MAML requires 1.7[h] learning times + 4.47[m] to generate solution (1.7[h] from supp mat and 4.47[m] from Table 1.), but LKH-3 requires 38.09[m]. So, if the learning results are not shareable with other kinds of datasets, the learning process is a bit resource-consuming trial. Do you have any ideas or findings?\n\n- The dimension T (of MAML) is fixed. Is this tunable? (or need to be tuned to get better solutions?). In the ablation study (c), it seems that learning more by MAML produces better solutions. Is this interpretation true?\n\n- (L.45) Instead of previous DIR-based CO sovles; what is DIR-based? sovles => solves. Some other english errors should be updated for readability.\n", "limitations": "After reading the main paper and appendix, I feel that the authors carefully discuss the negative impacts.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strength]\n- Focusing on the continuous space (Eq.2) could widen this research field (rather than the encoding-decoding scheme in DRL-based methods).\n- Large instances (e.g., TSP-10000) are tackled by DIMES (Note that such scalability could be hard for DRL-based methods in the current status).\n\n[Weakness]\n- The generalization ability when designing auxiliary distributions is unclear.\n- The discussion and background of MAML (e.g., the idea of T gradient updates) are a bit hard to follow.\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": "0dxK52_x6w_", "reviewer": "Reviewer_fQdp", "summary": "This paper improves existing DRL-based CO methods in two terms. Firstly, the authors leverage a continuous probabilistic space for the solutions, leading to a REINFORCEMENT-based training method which is more efficient than previous Q-learning or Actor-Critic methods. Besides, a MAML-based meta-learning framework is proposed.", "questions": "1.  How many trials are configured for LKH-3? Can you decrease the number of trials so that LKH-3 can be comparatively faster than DIMES, and report the time and tour lengths?\n2. In L149 the authors write: \"we also no longer need costly MCMC-based sampling for optimizing our model\". If sampling is not needed, how do you estimate the expected cost value after the neural network predicts q?\n3. What is the application scope of the proposed method? Beyond routing and independent set, can you list some other types of problems that the proposed method can tackle and some that may be hard to handle?\n4. Is there an ablation study for with/without meta-learning? ", "limitations": "The limitations are addressed.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. This paper is well-motivated by several important issues in existing DRL-based CO methods.\n2. The proposed REINFORCEMENT-based method and the MAML-based meta-learning method seem sound.\n3. The proposed method can handle larger-sized problems than existing DRL-based CO methods.\n\n**Weaknesses**\n1. This paper aims for developing a new general framework, but the current evaluation is only for two problems. Evaluating more problems of different natures (such as covering/matching problems) will make this paper more concrete and convincing.\n2. There are certain implementation details that seem unclear to me and I am expecting the authors to answer (see \"Questions\").\n\n**Typos**\n1. Line 45: What is \"DIR\"-based CO solver?\n2. Repeated citations: 29/30, 34/35", "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