UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems
Authors: Zhi Zheng
Changliang Zhou
Tong Xialiang
Mingxuan Yuan
Zhenkun Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Neural Combinatorial Optimization
Large-Scale Combinatorial Optimization Problem
Neural Divide-and-Conquer
Vehicle Routing Problem
Unified Framework
Primary area: machine_learning_for_other_sciences_and_fields

Abstract: Single-stage neural combinatorial optimization solvers have achieved near-optimal results on various small-scale combinatorial optimization (CO) problems without requiring expert knowledge. However, these solvers exhibit significant performance degradation when applied to large-scale CO problems. Recently, two-stage neural methods motivated by divide-and-conquer strategies have shown efficiency in addressing large-scale CO problems. Nevertheless, the performance of these methods highly relies on problem-specific heuristics in either the dividing or the conquering procedure, which limits their applicability to general CO problems. Moreover, these methods employ separate training schemes and ignore the interdependencies between the dividing and conquering strategies, often leading to sub-optimal solutions. To tackle these drawbacks, this article develops a unified neural divide-and-conquer framework (i.e., UDC) for solving general large-scale CO problems. UDC offers a Divide-Conquer-Reunion (DCR) training method to eliminate the negative impact of a sub-optimal dividing policy. Employing a high-efficiency Graph Neural Network (GNN) for global instance dividing and a fixed-length sub-path solver for conquering divided sub-problems, the proposed UDC framework demonstrates extensive applicability, achieving superior performance in 10 representative large-scale CO problems. The code is available at https://github.com/CIAM-Group/NCO_code/tree/main/single_objective/UDC-Large-scale-CO-master

UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems
Zhi Zheng'
Changliang Zhou' Xialiang Tong² Mingxuan Yuan² Zhenkun Wang
School of System Design and Intelligent Manufacturing. Southern University of Science and Technology. Shenzhen, China
2 Huawei Noah's Ark Lab, Shenzhen, China.
zhi zhengbu. nus edu, zhouc12022@mail wustech...shhhh..eeaao edu. cn,
(tongxialiang, yuan. ) (hhaavann com, vangzhenkknnS0@gmall. com
Abstract
Single-stage neural combinatorial optimization solvers have achieved near-optimal results on various small-scale combinatorial optimization (CO) problems without requiring expert knowledge. However, these solvers exhibit significant perfor- mance degradation when applied to large-scale CO problems. Recently, two-stage neural methods motivated by divide-and-conque strategies have shown efficiency in addressing large-scale CO problems. Nevertheless, the performance of these methods highly relies on problem-spechee the conquering procedure, which limits their applicability general CO prob- lems. Moreover, these methods employ separate training schemes and ignore the interdependencies between the dividing and conquering strategies, often lead- ing to sub-optimal solutions. To tackle these drawbacks, this article develops a unified neural -oiide- framework (i.e.. UDC) for solving general large-scale CO problems. UDC offers Divide Divide-Conquer Conquer-Reunion (DCR) training method to climinate the negative impact of a sub-optimal dividing policy. Employ- ing high-efficiency Graph Neural Network (GNN) for global instance dividing and a fixed-length sub-path solver for conquering divided sub-problems, the pro- posed UDC framework demonstrates extensive applicability, achieving superior performance in 10 representative large-scale CO problems. The code is avail- able at htttps://github http://hwww..aco/IMM/o/oor////// objective/UDCC-arree 1ttp:///DD---aaaaaa--l----------
heuristics in either the dividing
Introduction
Combinatorial optimization (CO) ① has numerous practical applications including route planning ( circuit design (3), biology 4. etc. Over the past few years, neural combinatorial optimization (NCO) methods are developed to efficiently solve typical CO problems such as the Travelling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP). Among them, reinforcement learning (RL)-based constructive NCO methods
can generate near-optimal solutions for small-scale instances (e.g.. TSP instances with more than 200 nodes) without the requirement of expert knowledge 77 These solvers usually adopt single-stage solution generation process. constructing the solution of CO problems node-by-node in an end-to-end manner. However, hindered by the disability training on larger-size instances directly (8] [0, these methods exhibit limited performance when generalizing to solve large-scale CO problems.
[5]
6
"Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison between our UDC and the other existing neural divide-and-come methods. The proposed UDC utilizes learning-bass -aaed policies in both the dividing and conquering stages. Moreover, UDC is the first to achieve a superior unified training scheme by considering the negative impact of sub-optimal dividing policies on solution generation.
Neural Divide and Conquers
Dividing Policy
Conquering Policy
Impact of Divide Consider / Agnnre x
Train the Two- policies Unified /Seperate
Methods
Prohlem
Neural /Heuristic
x
LCP
24
ISPCVRP
X
L2D
CVRP
H-TSP
20
TSP
RBG
CVRP & variants
TAM
CVRP
SO
21
TSP
GL.OP
[k]
(A)TSP, CVRP, PCTSP
x
UDC(Ours)
General CO Problems
To meet the demands of larger-scale CO applications, researchers have increasingly focused on
extending NCO methods to larger-scale instances (e.g., 1,000-node ones) [11]. Existing NCO methods for large-scale problems primarily involve modified single-stage solvers [6] and neural divide-and-conquer methods [12 [3). BQ-NCO [14] and LEHD [8] develop sub-path construction process [15] and employ models with heavy-decoder to learn the process. Nevertheless, training such a heavyweight model necessitates supervised learning (SL), which limits their applicability to problems where high-quality solutions are not available as labels. ELG O.. ICAM [16], and DAR [17] integrate auxiliary information guide the learning of RL-based single-stage constructive solvers designs, and the O complexity
[3]. However, the auxiliary information needs problem-spesr caused by the self-attention mechanism also poses challenges for large-scale (NV (onoode) problems. As another category of large-scale NCO, neural divide-and andide-e methods have attracted increasing attention. Inspired by the common divide-and-conque idea in traditional heuristics [88] 19), these methods execute a two-stage solving process, including dividing stage for overall instance partition and a conquering stage for sub-problem solving. By employing neural network for one or both stages, TAM [12]. H-TSP (20], and GLOP [3 have demonstrated superior efficiency in large-scale TSP and CVRP.
Despite acknowledging the prospect, these neural divide-and-conee and-conquer approaches still suffer from shortcomings in applicability and solution quality. Some neural divide-and-conge conquer methods rely on moblem-sppecing heuristics in either dividing (e.g.. GLOP [13 and SO [2]) or conquering stages
(e.g., L.2D [22 and RBG (3 ), which limits their generalizability across various CO problems. methods adopt a separate training process, training the dividing policy after a pre-trained conquering policy [3] 12 20). However, the separate training scheme overlooks the interdependencies between the dividing and conquering policies and may lead to unsolvable antagonisms. Once the pre-trained conquering policy is sub-optimal for some sub-problems, such training scheme might guide the dividing policy to adapt the pre-trained sub-optimal conquering policy, thus converging to local optima.
Moreover, all the existing neural divide-and-conguee
As shown in Table [] this paper finds that considering the negative impact of sub-optimal dividing results is essential in generating high-quality propose novel RL--based training method termed Seffe-Coonuer-Reenneee DCR in unified training scheme, we propose the unified neural devidd-anddconquee (UDC) for wide range of large-scale CO problems. UDC employs a fast and lightweight GNN to decompose a large-scale CO instance into several fixed-length sub-problems and utilizes constructive solvers to solve these sub-problems. We conduct extensive experiments on 10 different CO problems. Experimental results indicate that UDC can significantly outperform existing large-scale NCO solvers in both efficiency and applicability without relying on any heuristic design.
-onadd--nn--onu----baee based solutions. To this aim, we (DCR). Enabling the
framework
The contributions of this paper are as follows: 1) We propose a novel method DCR to enhance training by alleviating the negative impact of sub-optimal dividing policies. 2) Leveraging DCR in training. the proposed UDC achieves a unified training scheme with significantly superior performance. 3) UDC demonstrates extensive applicability and can be applied to general CO problems with similar settings.
'GLOP 13 utilizes heuristic dividing policy for TSP and Asymmetric TSP (ATSP) and neural dividing policy for CVRP and Prize Collecting TSP (PCTSP).

---

2 Preliminaries: Neural Divide-and-Conquer
2.1 Divide-and-Conquee
CO problem with N decision variables is defined to minimize the objective function f of a solution
(21,22, 22 .NN as follows:
minimize f(x 9)
#E
where G represents the CO instance and 52 is set consisting of all feasible solutions.
Leveraging the divide-and-conquer idea in solving CO problems is promising in traditional nweighhorrhoo--sarch------
(meta)heuristic algorithms (25), especially
algorithms 126] 22].
These methods achieve gradual performance improvement from an initial solution through iterative sub-problem selection (i.e., the dividing stage) and sub- uub-problem repair (i.e., the conquering stage). Recent neural divide-and-conquer methods conduct similar solving process and employ efficient deep-learning techniques to model the policies of both stages [33. The dividing policy Ta(G) decom- poses the instance G to mutually unaffected sub-problems (91, G2, .2,................. 99 and the conquering policy ne generates sub-solutions
for k (1...., K] by 8%. (9 to minimize the objective function f (sk, 9x) of corresponding sub-probie problems. Finally, a total solution æ G is merged as Concat ,8,...,,8K7 8K).
2.2 Constructive Neural Solver
The (single-stagee stage) constructive NCO solvers are promising solving general small-scale CO prob- lems with time efficiency. These constructive solvers typically employ an attention-basse encoder- decoder network structure, where multi-layer encoder processes CO instances into embeddings in hidden spaces and lightweight decoder handles dynamic constraints while constructing feasi- ble solutions [5]. With the solving process modeled as Markov Decision Processes (MDPs) (28), constructive solvers can be trained using deep reinforcement learning (DRL) techniques without requiring expert experience. In the solution generation process, constructive solvers with parameter process the policy of r-length solution (II,.... 2r) as follows:
[ 2,
II po 114-1, 1,
where æ1:--1 represents the partial solution before the selection of x,, DRL-based constructive NCO solvers demonstrate outstanding solution qualities in small-scale CO problems. So existing neural divide-and-conge conquer methods [33 21 also generally employ a pre-trained constructive neural solver (e.g., Attention Model (28) for their conquering policy Te.
2.3 Heatmap-based Neural Solver
Advanced constructive NCO solvers rely on the self-attention layers 29 for node representation,
whose quadratic time and space complexity related problem scales 30 hinders the direct training on large-scale instances. So, heatmap- based solvers [2 are proposed to solve large-scale CO problems efficiently by lighter-weight GNN [33] In heatmap-based solvers for vehicle routing problems (VRPs), a GNN with parameter & first generates a heatmap H E NNNN within linear time
34 and feasible solution is then constructed based on this heatmap with the policy 35 follows:
क (m 2, 0) = po (HG M)p(p))))))))))))))))))(())))3)
N (Xp(()
However, the non-autoreereessiell generated heatmap (36 excludes the information about the order of the constructed partial solution #1:--1, so the greedy decoding policy heatmap- solvers
becomes low-quality and these solvers rely on search algorithms 37 38
for higher-quality solutions.
3 Methodology: Unified Divide-and-Conuuer
As shown Figure I] UDC follows the general framework of neural divide-and-conquee methods [3] solving CO problems through two distinct stages: the dividing stage and the conquering stage. The

---

General CO problems
Dividing Stage
Conquering Stage
VRP solver
Normaloc
Merged VRP Soltion
Large-scale VRP
Initial VKP Soltion
Sub-VRR
Sub-VRP Solution
Heatnap
Sal-
Prgerssue
I
KP solver
Large scallalleeeee KP
Anisatropic
Griph
Heamup
Initial KP Soltion
Sub KP Solution
Mergol KP Soltion
Hestwap
Large scalle MIS
Initial
MIS salver
Sub MIS Solution
Merged
Instances
Lineleteed lecu
Sclecied
Unsclettd oodes in MIS
Selacsed uodes MIS
Nodes reaticted
Nodo restriced to staciiu or coding undes VRP
Rom La KP
urocleted is sab-MiS
Figure I: The solving process of the proposed UDC on large-scale VRP, 0-1 Knapsack Problem (KP), and Maximum Independent Set (MIS).
dividing stage of UDC expected generate feasible initial solution with similar overall shape compared to the optimal solution, so the subsequent conquering stage can obtain more high-quality solutions solving local sub-problems. For all the involved CO problems, UDC first constructs sparse graph to represent the instance and then employs heatmap-bart basudd solver with Anisotropic Graph Neural Network (AGNN) as the dividing policy [39 40 to generate initial solutions. The
following conquering stage first decomposes the original CO instance into multiple sub-problems based on the initial solution while integrating the necessary constraints for sub-problems. Then, towards minimizing the decomposed objective function of the sub-problem, UDC uses constructive neural solvers the conquering policy to generate sub-solutions. There is no single universal constructive neural solver that can handle all types of CO problems
[1 42) so we employ suitable
solvers for each sub-CO-problem (e.g., AGNN 33 for MIS, POMO or ICAM [66 for VRPs).
3.1 Pipeline: Dividing Stage & Conquering Stage
Heatmap-based solvers require less time and space consumption compared constructive solvers, so they are more suitable for learning global dividing policies on large-scale instances. The dividing stage first constructs sparse graph GD {V, ΣE} (i.e., linking K-nearest neighbors (KNN) in TSP, original edges in G for MIS) for the original CO instance G. Then, we utilize Anisotropic Graph Neural Networks (AGNN) with parameter & to generate the heatmap H. For N-node VRPs, the heatmap 7 E NNN and a r-length initial solutions Zo = (Fo,1..... Fu,r) is generated based on the policy ad as follows:
Dividing Stage: Heatmap-based Neural Dividing:
II 1=2 Σn exp H (Hza.e-1
if To Ω
9D, T 0)
(4)
0.
otherwise
Conquering Stage: Sub-problem Preparation: The conquering stage first generates pending sub- problems along with their specific constraints. For VRPs, the nodes in sub-VRPs and the constraints of sub-VRPs are built based continuous sub-sequences in the initial solution æo. In generating n-node sub-problems, UDC divides the original N-node instance G into N. sub-problems (G,,.... 9
according x", temporarily excluding nub-problems with fewer than n nodes. The constraints {S)..... Ω x } of sub- sub-problems include not only the cobblem-specfii constraints (e.g., no self- loop in sub- TSPs) but also additional constraints to ensure the legality of the merged solution after

---

Divide
Conquer
Reunion
CO instance
Starting
Sub-problems
Sub-problems
New sturting rode
Initial Solution
From Strating node
Divide
original
Divide
DAGNNE 0
=
Solution X
Solution X2
every modes
nodes
Dividing Policy on Sparse Graph $0o
M
Starting node by 2 node Conquering Stage
Illmn Consuciien Paliay
Poliey
Dividing Stage
Conquering Stage
Solution: Local perspective
Sub-problem of Sub-problem &b
Sub-problem gi
:.o D Conquer i
I Conqueer
A segment of initial solution
Sub-solution sf Sub-solution L
conne connection
Conquer
Sub-solution 5
The proposed DCR training method. The upper part shows the pipeline of a single DCR- enabled training step, including Divide step, a Conquer step, and Reunion step. The lower part provides a local view of a solution fragment demonstrate our motivation, the additional Reunion step can repair the wrong connections from sub-optimal sub-problem dividing results. DCR has the potential to correct sub-optimal dividing results by repairing the connection part in the additional Reunion step.
Figure 2:
integrating the sub-probee uub-problem solution to the original solution (e.g., maintaining the first and last node sub-VRPa Similar to previous works [3] 43,, we also normalize the coordinate of sub-problems and some numerical constraints to enhance the homogeneity of pending sub-problem instances. Due to the need to handle different constraints, the sub-problem preparation processes vary for different CO problems, which is presented in detail in the Appendix B
Conquering Stage: Constructive Neural Conquering: After the preparation of sub-problems the conquering policy is utilized to generate solutions to these instances {9....., G 인 J. We utilize constructive solvers with parameter 0 for most involved sub-CO problems. Their sub-solution E {I...., N }} are sampled from the conquering policy te as follows:
8y =
p( -1, Sg, 0), if 8k E.p
Te (e 24.
(5)
0.
otherwise
where $k,1:t-1 represents the partial solution before the selection of 8k,1. Finally, the last step in conquering stage, sub-solutions with improvements on the objective function will replace the original solution fragment in æ6 and the merged solution becomes 21 It's worth noting that the conquering stage can execute repeatedly on the new merged solution for a gradually better solution quality and note the solution after conquering stages Er.
3.2 Training Method: Divide- Divide-Conquer-Remnie (DCR)
Both the dividing and conquering stages in neural divide-and-conquer methods can be modeled as MDPs [12] (shown in Appendix C.7 The reward for the conquering policy is derived from the
objective function of the sub-solutions, while the reward for the dividing policies calculated based on the objective function of the final merged solution. Existing neural divide-and-conquer methods cannot train both policies simultaneously with RL [20]. Therefore, they generally employ a separate training scheme, pre-training conquering policy specific datasets before training the dividing policy [3]. However, this separate training process not only requires additional
dataset designs 13] but also undermines the collaborative optimization of the dividing and conquering policies (further discussed in Section (..I).
In this paper, we imply that considering the negative impact of sub-optimal sub-problems decom- position is essential to implement the unified training of both policies. Sub-problems generated by sub-optimal dividing policies will probably not match any continuous segments in the optimal
5

---

solution so as shown in Figure 2 despite obtaining high-quality sub-solutions, there may be error connections emerging the linking regions of these sub-problems. The naive solving procedure of neural divide-and-conquer
methods ignores these inevitable errors in solution generation, thus utilizing biased rewards to assess the dividing policy. To tackle this drawback, we propose the Conquer--euninee (DCR) process to eliminate the impact much as possible. DCR designs an additional Reunion step to treat the connection between the original two adjacent sub-problems as a new sub-problem and conduct another conquering stage on Φ with new sub-problem decompositions. The Reunion step can be formulated as rolling the original start point 11,0 along the solution æ by I times (i.e., to 21,i) and conquering again. To ensure equal focus the adjacent two sub-problems, we set = 2 in training all the DCR-enabled UDC models. DCR provides a better estimation for the 2
reward of dividing policies, thereby increasing the stability and convergence speed in unified training.
UDC adopts the REINFORCE algorithm [44] in training both the dividing policy (with Loss La) and the conquering policy (with Loss La1 for the Conquer step and La for the Reunion step). The baseline in training dividing policy is the average reward over a initial solutions zy. í (1.....a) and the baseline for conquering policy is calculated over 3 sampled sub-solutions. The gradients of loss functions on a single instance G are calculated as follows:
VLa(9)
1
2
9)
1
f(2 ()) log 2.)
a
a
9
(9)
1
(f (.))
1
, V (s. 2. 0)
a.3
c=1
j=1
al
(9)
(f (.)))
1 Σ
(s
23 (.) V Te (s 22 0)
N a
3
m
where {a), 22 represents the a sampled solutios. There are al I sub-problems Go E (I....,, J ...., a ] generated based on {=}..... , in the first conquering stage with con- straints 2 al N can be regarded as the batch size of sub-problems. and G. Q6 c (1,..., a: }] is the sub-problems and constraints in the second conquering stage. The B sampled sub-solutions for sub-problem Gh2 G2, [l,...,,a _ }} are noted {s ..... s1.91 ( ,..., 22.0)
3.3 Application: Applicability in General CO Problems
This subsection discusses the applicability of UDC to various CO problems. Most existing neural divide-and-conquer methods rely on problem-specific designs, they are only applicable limited CO problems. UDC uses no heuristics algorithms or problem-specific designs in the whole solving process, thus can be applied general offline CO problems that satisfy the following three conditions:
The objective function contains only decomposable aggregate functions (i.e., no functions like Rank or Top-k).
The legality initial solutions and sub-solutions can be ensured with feasibility masks.
The solution of the divided sub-problem not always unique.
For the second condition, the proposed UDC is disabled on complex CO problems whose solution cannot be guaranteed to be legal through an autoregressive solution process (e.g.. TSPTW). For the third condition, on certain CO problems such as the MIS problem dense graphs job scheduling problems, the solution of sub-problems has already been uniquely determined, so the conquering stages become ineffective.
Experiment
To verify the applicability of UDC in the general CO problem, we evaluate the UDC on 10 combi- natorial optimization problems that satisfy the conditions proposed in Section 3.3 including TSP, CVRP, KP, MIS, ATSP, Orienteering Problem (OP), PCTSP, Stochastic PCTSP (SPCTSP), Open

---

Table 2: Objective function (Obj., Gap to the best algorithm (Gap), and solving time (Time) on 500-node. 1,000-node, and 2,000-node TSP and CVRP. All TSP test sets and CVRP500 test sets contain 128 instances. CVRPI, 1,00 and CVRP2,000 contain 100 instances (following the generation settings in [3). The overall best performance in bold and the best learning- based method is marked by shade.
N =500
N =1,000
N =2,000
Methods
Obj-
Gap
Time
Obj-J
Gap
Time
Obj-4
Gap
Time
LKH3
16.52
5.5m
23.12
24m
32.45
Attn-MCTS*
16.97
2.69%
6m
23,86
3.20%
12m
33.42
2.99%
DIMES*
16.84
1.93%
2.2h
23.69
2.47%
4.6h
DIFUSCO+Search
17.48
5.80%
19m
25.11
8.61%
59.2m
BQ
16.72
1.18%
46s
23.65
2.27%
1.9m
34.03
4.86%
3m
LEHD
16.78
1.56%
16s
23.85
3.17%
1.6m
34.71
6.98%
12m
TSP
POMO
20.19
22.19%
Im
32.50
40.57%
8m
50.89
56.85%
10m
ELG
17.18
4.00%
2.2m
24.78
7.18%
13.7m
36.14
11.37%
14.2m
ICAM
16.65
0.77%
23.49
1.58%
1m
34.37
5.93%
3.8m
GLOP revisions)
16.88
2.19%
1.5m
23.84
3.12%
3.5m
33.71
3.89%
9m
SO-mixed*
16.94
2.55%
32m
23.77
2.79%
32m
33.35
2.76%
14m
H-TSP
17.55
6.22%
20s
24.72
6.91%
40s
34.88
7.49%
48s
UDC- greedy)
16.94
2.53%
20s
23.79
2.92%
32s
34.14
5.19%
23s
UDC-as0(u=50)
16.78
1.58%
4m
23.53
1.78%
33.26
2.49%
15m
LKH3
37.23
7.1h
46.40
7.90%
14m
64.90
8. 8.14%
40m
BQ
38.44
3.25%
47s
44.17
2.72%
55s
62.59
4.29%
3m
LEHD
38.41
3.18%
17s
43.96
2.24%
1.3m
61.58
2.62%
9.5m
ELG
38.34
2.99%
2.6m
43.58
1.33%
15.6m
CVRP
ICAM
37.49
0.69%
42s
43.07
0.16%
26s
61.34
2.21
3.7m
L2D
46.3
7.67%
3m
65.2
8.64%
1.4h
TAM(LKH3)*
46.3
7.67%
4m
64.8
7.97%
9.6m
GLOP-G (LKH-3)
42.45
11.73%
2.4m
45.90
6.74%
63.02
5.01%
2.5m
UDC- greedy)
40.04
7.57%
1m
46.09
7.18%
2. 2.1m
65.26
8.75%
5m
UDC=z:0(a==0)
38.34
3.01%
7.7m
43.48
1.11%
14m
60.94
1.55%
23m
UDC=#25a(e=50)
37.99
2.06%
35m
43.00
1.2h
60.01
2.15h
VRP (OVRP), and min-max multi-agent TSP (min-max mTSP). Detailed formulations of these problems are provided in the Appendix [
Implementation By employing lightweight networks for dividing policies, UDC can be directly trained on large-scale CO instances (e.g., TSP500 and 1,000). To learn more scale-independent features, follow the varying- size training scheme 45 46) in training and train only one UDC model for each CO problem. The Adam optimizer [47 is used for all involved CO problems and the detailed hyperparameters for each CO problem provided in Appendix D.I Most training tasks can be completed within 10 days on a single NVIDIA Tesla V100S GPU.
Baselines This paper compares the proposed UDC to advanced heuristic algorithms and existing neural solvers for large-scale scale CO problems, including classical solvers (LKH [48]. EA4OP 49 OR-
Tools (50), single-stage SL-based sub-path solvers (BQ [14], LEHD (8). single-stage RL-based constructive solvers (AM (51), 50MO(5, ELG (6), ICAM [6), MDAM (52) et al.), heatmap-
based solvers (DIMES 35) DIFUSCO (3], et al.) and neural divide-and-conque
methods (GLOP [3). TAM 12). 2-TSP et al.). The implementation details and settings of all the
baseline methods are described in Appendix G
Results on 500-node 2,000-node Instances. We first examine the performance of UDC models on large-scale CO problems ranging from 500-node to 2,000-node. Both single-stage SL-based constructive methods [66] and single-stage sub-path solvers { cannot be directly trained on this scale, so we report the results of models trained on the maximum available scale for these baselines. For UDC, we provide not only the greedy results (UDC-&2) but also the results after conducting more conquering stages (i.e., 50 and 250 stages, labeled as UDC-250. UDC-#250). In the following conquering stages after a greedy solution, the starting point of sub-problem dividing is no longer fixed at /h but is sampled from Uniform(0, n).. For better performances, we sample 50 initial
7

---

Table 3: Experiment results on 500-node to 2,000-node OP and PCTSP and SPCTSP. The 500- scale, 100-scale, and 2,000-scale problems contain 128, 128, and 16 instances, respectively. "bs-k" represents k-width beam search [5I]. The overall best performance is in bold and the best learning- based method is marked by shade.
N =500
N =1,000
N =2,000
Methods
Obj.12
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
EA4OP
81.70
7.4m
117.70
63.4m
167.74
38.4m
BQ-bs16*
4.10%
10m
10.68%
17m
AM
64,45
21.11%
2s
79.28
32.64%
5s
99.37
40.76%
2s
OP (dist)
AM-bs1024
68.59
16.04%
1.2m
79.65
32.32%
4m
95.48
43.08%
1.6m
MDAM-bs50
65.78
19.49%
2.6m
81.35
30.88%
12m
105.43
37.15%
7m
Sym-NCO
73.22
10.38%
27s
95.36
18.98%
1.5m
121.37
27.64%
20s
UDC-æa(u=l)
75.28
7.86%
17s
109.42
7.03%
135.34
19.32%
UDC=ms0(o=l)
78.02
4.51%
23s
111.72
5.08%
33s
139.25
16.99%
8s
(DC-a2so(a=1)
79.27
2.98%
48s
113.27
3.76%
1.1m
144.10
14.09%
21s
OR-Tools*
14.40
9.38%
16h
20.60
12.66%
AM-bs1024
19.37
47.13%
14m
34.82
90.42%
23m
87.53
249.60%
10m
PCTSP
MDAM--s500
14.80
13.30%
6.5m
22.21
21.43%
53m
36.63
46.30%
43m
Sym-NCO
19.46
47.81%
1.3m
29.44
61.01%
7m
36.95
47.58%
2m
GL.P
14,30
9.03%
1.5m
19.80
8.08%
2.5m
27.25
8.84%
1m
UDC=x=(a=I)
13.95
5.99%
34s
19.50
6.65%
27.22
8.73%
18s
(DC-==3(o=1)
13.25
0.64%
42s
18.46
0.97%
1.3m
25.46
1.68%
23s
UDC=225((a=I)
13.17
80s
18.29
1.5m
25.04
53s
AM-bs1024
33.91
156. 11% %
1.2m
47.55
156.42%
76.02
199.48%
14m
SPCTSP
MDAM
14.80
11.80%
6.5m
21.96
18.42%
53m
35.15
38.48%
43m
(D==
14.21
7.32%
42s
20.01
7.92%
1.1m
28.15
10.91%
20s
UDC-xsa(a=l)
13.40
1.12%
1m
18.93
2.06%
1.4m
26.24
3.38%
29s
UDC=#250(a=1)
13.24
2.3m
18.54
2.6m
25.38
1.1m
solutions Ty for TSP and CVRP. The comparison results of TSP and CVRP are shown in Table and the results of OP, PCTSP, and SPCTSP are exhibited in Tabel 4 UDC demonstrates the general applicability, exhibiting consistent competitive performances in all the five involved CO problems. After multiple conquering stages, UDC can achieve significantly better results.
UDC variants demonstrate the best results in PCTSP, SPCTSP, CVRP1,00 1,000, and CVRP2,000, together with the best leamning-bsse based method in most involved CO problems. The 22C- showcases extensive efficiency in OP, PCTSP, and PCTSP. Compared sub- path solvers BQ [14] and LEHD (8] UDC variants exhibit more competitive results on ISP1,00 ,000, TSP2,000, CVRP, and OP. RL-bdsed constructive solver ICAM [16] with 8 augmentation [5] is outstanding performance TSP1,000, and CVRP500 (i.e., relatively smaller scale) but UDC variants demonstrates better effect and efficiency in other test sets. Moreover, compared to existing neural divide-and -nd-uuque methods GLOP 13 H-TSP 200, and TAM(LKH3) [12), UDC achieves significant advantages performance with heuristic design, which preliminarily implies the significance of unified training scheme for neural divide-and-conquer methods.
TSP500,
Results on Benchmark Datasets. We also evaluate the proposed UDC on benchmark datasets TSPLib 53 and CVRPLib (54]55). We adopt the instances with 500-node to 5,000-node in TSPLib, CVRP Set-X [54), and very large-scale CVRP dataset Set-XXL as test sets. Instances in these datasets often with special distributions and can better represent real-world applications. As shown in Table UDC variant UDC-2250 exhibits competitive benchmark results, demonstrating the best learning-basse based result on CVRPLib. The proposed UDC can also demonstrate superiority in the other 5 involved CO problems, very large-scale instances. Results of these experiments shown in Appendix D.2 and Appendix D.5] respectively. And as to AppendixD.3 AppendixD.4l UDC can also exhibit outstanding out-of-domain generalization ability on TSP, CVRP, and MIS instances with different distributions.
OP aims to maximize the objective function, while PCTSP and SPCTSP aim to minimize the objective function.

---

Table 4: TSPLib and CVRPLib results, the best learning-basse bastd result is marked by shade
TSPLib, Gap to Best Known Solution
Dataset, N E
LEHD
ELG augx8
GKO3 TAM(LKH3)
UDC-az
UDC-2250
(SPLib,(500,1,00))
4.1%
8.7%
4.0%
9.5%
6.0%
TSPL.b.(1,000,5,000)
11.3%
15.5%
6.9%
12.8%
7.6%
CVRPLib, Cap to Best Known Solution
(ttxX.(500.1000)
17.4%
7.8%
16.8%
9.9%
16.5%
7.1%
Set [0.XXXXX.1000000000000
22.2%
15.2%
19.1%
20.4%
31.3%
13.2%
Discussion
The experimental results have preliminarily proven that the proposed UDC method achieves excellent results wide range of large-scale CO problems with outstanding efficiency. In this section, we conduct ablation experiments to verify the necessity of components in training UDC models. Appendix Enncuuess the ablation experiments the testing procedure of UDC, including the ablation on the number of conquering stages r and the number of sampled solutions a.
5.1 Unified Training Scheme versus Separate Training Scheme
For neural divide-and-conquee methods, the unified training process does require special designs for pre-training conquering policies, thus being easier to implement compared to separate training processes. Moreover, unified training conquering policies. To validate this, we pre-train a conquering policy (i.e.. ICAM) on uniform TSP100 data and then train two ablation variants of the original UDC (separate training scheme): one variant uses the pre-trained conquering policy in the subsequent joint training (i.e., Pre-train + Joint Training, similar to H-TSP (20)), and the other variant only train the dividing policy afterward (i.e.. Pre-train Train Dividing, similar to TAM [12] & GLOP [3). According to the training curves of UDC and the two variants in Figure the unified training scheme demonstrates superiority, while the
also avoid the antagonism between the dividing and
Pre-train step leads the training into local optima, which significantly harms the convergence of UDC.
TS P 1SP0000-Trainng
Unified Training
Unified Training JUDC)
1/8
Pre train +joint Training
Pre-train oint Tranningg
Pre-train + Train Dividing
Pre-train + Train Dividing
1/8
2112
172
173
Epochs
Epochs
(a) TSP500
(b) TSP1,000
Figure Training curves of UDC variants with different training schemes.
5.2 Ablation study: Conquering Policy
UDC adopts the state-of-the-are constructive solver ICAM [16] for conquering sub-TSP. However, the se- lection of constructive solvers for the conquering policy is not limited. We employ POMO B3 for the conquer- ing policy, with experiment results of this version (i.e., UDC(PMMO) on TSP500 and TSP1,000 shown in Ta- 5.1 (a 50 for all variants). The UDC framework demonstrates conquering-pel aaaguering-poliy-aggeee policy-agnosttcism, as it does not show significant performance degradation when the conquering policy becomes POMO.
Table 5: Results of UDC variants with var- ious conquering policies.
Optimality Gap
TSP500
TSP1.000
UDCTICAM)
2.54%
2.92%
UDC(ICAM)-ae -
1.58%
1.78%
UDC(POMO)
2.64%
3.41%
UDC(POMO -2750
1.64%
1.82%

---

In Appendix E.4 we further validate the conquering- policy-agm agnoostinos of UDC on KP. We also conduct other ablation studies demonstrate the necessity of other components of the proposed UDC, including the Reunion step in the DCR training method and the coordinate transformation the conquering stage.
6 Conclusion, Limitation, and Future Work
This paper focuses on neural divide-and and---uu solvers and develops novel training method DCR for neural divide-and-comee ann-conquer methods by alleviating the negative impact of sub-optimal dividing results. By using DCR in training, this paper enables superior unified training scheme and proposes a novel unified neural divide-and-conquee framework UDC. UDC exhibits not only outstanding performances but also extensive applicability, achieving significant performance advantages in 10 representative large-scale CO problems.
Limitation and Future Work. Although UDC has achieved outstanding performance improvements, we believe that UDC can achieve better results through designing better loss functions. the future, we will focus on a more suitable loss for the UDC framework to further improve training efficiency, Moreover, we will attempt extend the applicability UDC CO problems mentioned in Section 3.3 that are not applicable in the current version.
Acknowledge
This work was supported by the National Natural Science Foundation of China (Grant No. 62106096 and Grant No. 624761 the Natural Science Foundation of Guangdong Province (Grant No. 2024A1515011759), the National Natural Science Foundation of Shenzhen (Grant No. JCYI20020533111311333),,
References
[1] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[2] Matthew Veres and Medhat Moussa. Deep learning for intelligent transportation systems: survey of emerging trends. IEEE Transactions on Intelligent transportation systems, 21(8):3152 111111222228,,,, 2019.
[3] Stephan Held, Bernhard Korte, Dieter Rautenbach, and Jens Vygen. Combinatorial optimization in vlsi design. Combinatorial Optimization, pages 33-96, 2011.
[4] Gita Naseri and Mattheos AG Koffas. Application of combinatorial optimization strategies in synthetic biology. Nature communications, 11(1):2446, 2020.
[5] Yeong-Des -Da Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances Neural Information Processing Systems, 33:21 188-21 198, 2020.
[6] Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy, 2023.
[7] Shengcai Liu, Yu Zhang, Ke Tang, and Xin Yao. How good is neural combinatorial optimization? arXiv preprint ar 22v: 10913, 2022.
[8] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Teirth- Conference on Neurul Information Processing Systems, 2023.
[9] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointer- forner: Deep reinforced multi multi-pointer transformer for the traveling salesman problem. arXiv preprint arXiv:2304.09Mm 094077, 2023.
[10] Dongxiang Zhang. Ziyang Xiao, Yuan Wang, Mingli Song, and Gang Chen. Neural tsp solver with progressive distillation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 22147-12154 2023.
[11] Chaitanya K Joshi, Quentin Cappart, Louis Martin Rousseau, and Thomas Laurent, Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1-2):70-9 2022.
10

---

[12] Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang. and Yuming Deng. Generalize learned heuristics solve large-scale vehicle routing problems in real-time. In The Eleventh International Conference on Learning Representations, 2023.
[13] Haoran Ye, Jiarui Wang, Helan Liang. Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing prohlems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[14] Darko Drakulic, Sofia Michel, Florian Mai, Amaud Sors, and Jean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. In Thirty-seventh Conference on Neurul Information Processing Systems, 2023.
[15] Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems, IEEE Transactions on Industrial Informatics, 17(7):8661443 18744444487, 2020.
[16] Changliang Zhou, Xi Lin, Zhenkun Wang. Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Instance- conditioned adaptation for large-scale generalization of neural combinatorial optimization. arXiv preprint arXiv:2405.00 00906 2024.
[17] Yang Wang. Ya-Hui Jia, Wei-Neng Chen, and Yi Mei. Distance-aware attention reshaping: Enhance generalization of neural solver for large-scale vehicle routing problems. arXiv preprint arXiv:2401.0697 2024.
[18] Danial Yazdani, Mohammad Nabi Omidvar, Jürgen Branke, Trung Thanh Nguyen, and Xin Yao. Sealing up dynamic optimization problems: A divide-and-conquer approach. IEEE Transactions on Evolutionary Computation, 24(1):1-15, 2019.
[19] Oleg S Zaikin and SE Kochemazov. On black-box optimization in divide-and-conguer sat solving. Optimization Methods and Software, 36(4):672-696, 2021.
[20] Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, and Jiang Bian. H-tsp: Hierarchically solving the large-scale traveling salesman problem. In AAAI 2023, February 2023.
[21] Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to aolve large-scale tsp instances. International Conference on Artificial Intelligence and Statistics,, pages 1219-1231. PMLR, 2023.
[22] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198- 220888226611111111 2021.
[23] Zefang Zong, Hansen Wang, Jingwei Wang, Meng Zheng, and Yong Li. Rbg: Hicrarchically solving large-scale routing problems in logistic systems via reinforcement learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648 4658, 2022.
[24] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34: 10418-104300 2021.
[25] Yuzhou Zhang. Yi Mei. Shihua Huang, Xin Zheng. and Cuijuan Zhang. route clustering and search heuristic for large-scale multidepot-capciitae are routing problem. IEEE Transactions on Cybernetics, 52(8):8286-82) 2021.
[26] David Pisinger and Stefan Ropke. Large neighborhood search. Handbook of metaheuristies, pages 99 09-127, 2019.
[27] Setyo Tri Windras Mara, Rachmadi Norcahyo. Panca Jodiawan, Luluk Lusiantoro, and Achmad Pratama Rifai. A survey of adaptive large neighborhood search algorithms and applications. Computers & Operations Research, 146:10 2022.
[28] Irwan Bello, Hicu Pham, Quoe V Lc, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforeement learning. arXiv preprint arXiv: (tf:::/111.09900000 1,09940, 2016.
[29] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[30] Luo, Xi Lin, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Self-improved Iearning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403. 19561, 2024.
[31] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 199600002.72. 2019.
[32] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33:6659-6672,
2020.
[33] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang. Changcheng Li. and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
11

---

[34] 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. 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 19 19-24, IEEE, 2020.
[35] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems 35, 2022.
[36] Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang, Xuan Wu, Changliang Zhou, and You Zhou. Distilling autoregressive models to obtain perfo-eeffrmncc aon-eutoreeeesivve solvers for vehicle routing problems with faster inference speed. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38,
pages 20274-20283, 2024.
[37] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings the AAAI conference on artificial intelligence, volume 35, pages 7474-7482, 2021.
[38] Yifan Xia, Xianliang Yang. Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoe scarch-based neural approaches for solving large-scalc traveling salesman problems. arXiv preprint arXiv:2406. 03503, 2024.
[39] Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization.
In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[40] Xavier Bresson and Thomas Laurent, An experimental study neural networks for variable graphs. 2018.
[41] Yeong-Day Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138 5149, 2021.
[42] Zhi Zheng, Shunyu Yao, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Ke Tang. Dpn: Decou- pling partition and navigation for neural solvers of min-max vehicle routing problems. arXiv preprint arXiv:2405. 17272, 2024.
[43] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: A generalizable routing problem solver with invariant nested view transformer. arXiv preprint arXiv:2402.02317, 2024.
[44] Ronald J Williams. Simple statistical gradient-foloowing algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256, 1992.
[45] 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.
[46] Yuhong Cao, Zhanhong Sun, and Guillaume Sartoretti. Dan: Decentralized attention-base neural network
to solve the minmax multiple traveling salesman problem. arXiv preprint arXiv:2109. 1000:2209.04205, 2021.
[47] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint MeXiv:1412.99880 2014.
[48] Keld Helsgaun. An extension of the tin-kemighhnn-helsgan tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12, 2017.
[49] Gorka Kobeaga, María Merino, and Jose A Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers & Operations Research, 90:42-59, 2018
[50] Laurent Perron and Vincent Furnon. Or-tools.
[51] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint 1 808.8003....... 2018
[52] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 12042- 12049, 2021.
[53] Gerhard Reinelt. Tsplib-a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
[54] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Mareus Poggi, Thibaut Vidal, and Anand Subramanian. New henchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 254(3)885--858, 2017.
[55] Florian Arnold, Michel Gendreau, and Kenneth Sörensen, Efficiently solving very large-scale routing problems. Compuders & operations research, 00::32-42, 2019.
[56] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[57] Nina Mazyavkina. Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforvement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
12

---

[58] Feng Wang. Qi He, and Shicheng Li. Solving combinatorial optimization problems with deep neural network: A survey. Tsinghua Science and Technology, 5965):1266-1288 2024.
[59] 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:1 14:11096--0 11107, 2021.
[60] Zhi Zheng, Shunyu Yao, Genghui Li, Linxi Han, and Zhenkun Wang. Pareto improver: Learning improvement heuristies for multi-objective route planning. IEEE Transactions on Intelligent Transportation Systems, 2023.
[61] Rui Sun, Zhi Zheng, and Zhenkun Wang. Learning encodings for constructive neural combinatorial optimization needs to regret. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20803-20811 2024.
[62] Jiwoo Son, Minsu Kim, Sanghyeok Choi, and Jinkyoo Park. Solving np-hard min-max routing problems as sequential generation with equity context. arXiv preprint (tii::200600268899 2023.
[63] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. arXiv preprint arXiv:2205. 33209, 2022.
[64] Jingwen Li, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Transactions Intelligent Transportation Systems, 23(3)23306 2315. 2021.
[65] Yimeng Min. Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 36, 2024.
[66] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
[67] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models, arXiv preprint 20.020000,02502,, 2020.
[68] Carmen Gervet. Large scale combinatorial optimization: methodological viewpoint. In DIMACS series: Constraint Programming and Large Scale Discrete Optimization, 2001.
[69]
Norman Biggs. The traveling salesman problem a guided tour of combinatorial optimization, 1986.
[70] Lahari Sengupta, Radu Mariescu-Istodor, and Pasi Fränti. Which local search operator works best for the open-loop isp? Applied Sciences, (19):3985, 2019.
[71] Cristina R Delgado Serna and Joaquín Pacheco Bonrostro. Minmax vehicle routing problems: application to school transport in the province of burgos. Computer-aided scheduling of public transport, pages 297-317. Springer, 2001.
[72] Jennifer David and Thorsteinn Rögnvaldsson. Multi-robot routing problem with min max objective. Robotics, 10(4): 2021.
[73] Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Siegoid-weighted linear units for neural network function approximation in reinforcement learning. Neural networks, 107:3-11, 2018.
[74] 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.
[75] Fei Liu. Xi Lin, Zhenkun Wang. Qingfu Zhang. Tong Xialiang, and Mingxuan Yuan. Multi-tase task learning for routing problem with zero-shot generalization. 2023.
[76] Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song. Yining Ma, Jie Zhang, and Chi Xu. Mvmoe: Multi-task vehicle routing solver with mixture-of-cxperts. arxiv preprint arXiv:2405.01029, 2024.
[77] László Erdós, Antti Knowles, Homg-Tzer Yau, and Jun Yin. Spectral statistics of erdös-rényi graphs i: Local semicircle law. 2013.
[78] Sasan Mahmoudinazlou and Changhyun Kwon. A hybrid genetic algorithm for the max multiple traveling salesman problem. Computers & Operations Research, 162:106455, 2024.
[79] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning, pages 42769- 42789. PMLR, 2023.
[80] Chengrui Gao, Haopu Shang, Ke Xue. Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy, 2024.
13

---

Appendix
In the following Appendix, we will provide literature review detailed definitions of CO problems & sub-CO problems B details of the proposed UDC method C
additional experimental results D additional ablation study Ej and visualizations on TSP1,000 instance, CVRP1,000 instance (i.e.. X-n1001-k43 in CVRPLib), and OP1,00 (,00000 instance F
A Related Work
A.1 Neural Combinatorial Optimization
Over the past few years, extensive research on learning- based methods has been applied to various CO problems. Pointer Network [56] first applies the deep learning technique to solve NP-hard CO problems, after that, [28] designs an RL-based framework for training NCO solvers. In recent years, more diverse and sophisticated NCO frameworks have been proposed [57 58 Among them, the mainstream methods include (RL-bbsedd constructive solvers [5T] (RL-based) improvement-baseed
solvers 559 600, (SL--based) sub-path solvers [8) the heatmap-based solvers [35], and the neural
divide-and- conquer methods [13.. These categories of methods demonstrate diverse advantages
across different scales and CO problems.
A.2
Constructive Neural Solvers
The basic idea of constructive neural solvers has been illustrated in Section 2.2 Up now, con- structive neural solvers are the most popular neural method for solving CO problems. By employing the self-attention mechanism [29], the Attention Model [5T] demonstrates the applicability among various VRPs and the efficiency in solving small-scale VRP instances. AM achieves outstanding results six VRPs including TSP, CVRP, Split Delivery Vehicle Routing (SDVRP), PCTSP, SPCTSP, and OP. Afterward, researchers mainly focus on the two most representative CO problems, TSP and CVRP. Some studies propose more advanced problem-solvin
others present more efficient network architectures [9] [2]) and some focus on designing better loss functions [5] 63 better escape potential local optima.
strategies
61
By employing a corresponding feasibility mask in each autoregressive construction step, constructive solvers can be effectively applied most CO problems. Therefore, although many model structures have been proposed for different CO problems (such as [64] for the Pickup and Delivery Problem (PDP)), ordinary frameworks are usually still feasible. This article adopts the model architectures proposed in POMO (5) and ICAM [16] for most CO problems for convenience. However, for some special CO problems, e.g., MIS. ATSP, and min-max mTSP, conventional constructive solvers are unable to process the groblem-speciff, constraints in their encoders. Therefore, we specifically use one-shot AGNN (consistent with the dividing policy) sub-MIS, MatNet [1] for sub-ATSP, and DPN 42
to solve sab-min--ax mTSP.
A.3 Heatmap-based Solvers
Recent heatmap-based solvers propose methods to improve the performance of GNN-based frame- works [31 32). Attn-MCTS (37] proposes a heuristic method to merge the smaller heatmap obtained from different regions of a TSP instance into larger heatmap of TSP. More importantly, Attn-MCTS also integrates an effective Monte-Carle tree search algorithm (MCTS) based on large-scale heatmaps. Therefore, the following heatmap-based works turn to pay more attention to providing better initial heatmaps for the following Monte Carlo tree search [65 R8 DIMES (35] proposes a meta-learning method based on reinforcement learning for stability training, while DIFUSCO (39] and T2T (66)
use supervised learning to learn diffusion process 667 of heatmap generation.
A.4 Neural Divide-and-Conquee Conqueer Methods
The Table in the main part offers a brief overview of all the existing neural divide-and-conquer methods. These methods and the proposed UDC follow the same two-stage solution generation framework. Instead of being fully neural method as UDC, some neural divide-and-conquer methods strategically incorporate problem-specific heuristics in either the dividing or conquering stages to
14

---

enhance performance or efficiency generalize to other CO problems.
122
23 21
13
Such setting undermines the possibility to
ICP 24 H-TSP 20 RBG 23,, TAM 12 and GLOP B3 (for CVRP and PCTSP) can use only neural networks in both stages, which enhances the applicability of methods to handle general CO problems without expert experience. However, these methods face challenges in terms of solution qualities. To tackle the instability in unified training [20], all these methods adopt separate training scheme and we believe there are inherent shortcomings in the separate training schemes. Among them, LCP [44 employs constructive neural solver (seeder) to generate diversified initial solutions (seeds) and another constructive neural solver (reviser) for sub-path solving. The seeders and revisers are trained separately and the objective functions of its seeders and revisers are not directly related to the objective function of the original CO problem (i.e., belonging to separate training scheme), so its effectiveness largely depends on randomness.
TAM 12). GLOP 13 (for CVRP and PCTSP), and RBG 23 adopt a similar training scheme, with only using different solvers for the dividing policy (i.e., TAM uses constructive neural solver, and GLOP chooses a aaatmmpp-baed solver). These methods pre-train a conquering policy on a preempted dataset and directly use them as local solvers (i.e., operators) for their initial solution. Such a training scheme fits the Pre-train + Train Dividing variant in Section 5.T which can hardly converge to good performance. The pre- pre-trained conquering policy will usually generate sub-optimal sub-solutions so such a training scheme will probably lead to local optima. Moreover, as another drawback of TAM and GLOP, they decompose CVRP and PCTSP into sub-TSP for the pre-trained conquering policy, but such solving framework cannot convert sub-optimal initial partitions into optimal ones, thus affecting the accessibility of optimal solutions.
H-TSP [20] focuses on the TSP problem and designs a lightweight convolutional neural network and clustering mechanism for initial solution generation. Unlike other works, implements a joint training scheme after pre-trained conquering policies. However, Section [. aaso demonstrates that the pre-training before joint (i.e., unified) training scheme will also lead to local optima. Moreover, similar to LCP, it does not align the optimization objectives of the dividing policy with the overall objective function of TSP well, which further limits its effectiveness.
15

---

B Detailed Definition
B.1 Definition of Large-scale CO problems
We refer to the definition in [68] for large-scale CO problems. Large-scale CO problems have more data, decision variables, or constraints. this article, we have considered more decision variables and data volumes in CO problems like TSP and more constraints in CO problems like MIS (i.e., dense graphs have relatively more constraints). Most large-scale NCO works solve TSPs on scales such 500, 1000, 2000, etc. 33 16 13 to general CO problems.
so UDC follows this setting in testing TSP and applies
B.2 Definition of Problem & Sub-problem
TSP Traveling salesman problem (TSP) is of the most representative COPs ......N NN, transformed from the input node-wise coordinates), where dj.x denotes the between nodes k and j. the goal is to minimize the following objective function:
69
Let {D=
dz.x.J = I,...,
= 1 1..., N be the x N cost metrics of a N-nodes TSP problem (in practice,
N
minimize
f(x)
Σ t=1
dar + dex.
where the solution (21, 22 ................................ EN) (T N) is a permutation of all nodes. All the feasible solutions (i.e., in of Eq. (T) satisfy the constraint of node degree being two and containing no loop with lengths less than N.
The TSP in UDC is usually considered as an open-loop TSP problem 77 (i.c., SHPP in GLOP 13). To make the optimization target of both stages correspond (with objective function f(-) and f'()) respectively), with the sub-cost metrics {D' = d'Ax: = -,...., n, h 1..., n), the objective function of sub-TSP solution 8 (81, ..,...,......................... 8a) is as follow:
minimize ((s))
Σ d' 1a
(8)
The feasibility set of sub-TSP adds additional selection constraints for the starting and ending points (i.e., the first and last node the original solution segments). UDC trains the TSP on various scales for every nodes, from N=500 to N=1,000 (i.e., for easier implement, we set n=100, and sampling N from (500, 600, 700, 800, 900, 1, 0003). Since the nodes in each sub-problem always come from compact region of the original instance,
follow the normalization approach in GLOP and conduct a coordinate transformation to coordinates of sub-problems. The specific formula detailed in Eq. 20
CVRP CVRP incorporates the vehicle capacity as a restriction while considering the total distance its objective function. Each CVRP contains depot and several customers, cost matrix {D = jj. = 0, 0,...,N,k- NJ.. the CVRP can be expressed as follows:
minimize
f(x) O(P)) j=l
18'1-1
C(p') Σ d dii + d
(9)
subject 0 05 < C,
i= 1,..., n,
Σ 6 CC j =1,... ......9. s
where æ is a solution representing the complete route of vehicles and consists of q sub-routes a = {p' p?...., p²}. Each sub-route p = (p....,, j E {1..... / starts from the depot To and backs to oo. n, represents the number of customer nodes in it. ΣS= nj is the total
16

---

CVRP Initial Solution
Sub-CVRP
Sub-CVRP1
Sub-CVRP2
Lub-CVRP1
Sub-CVRP2
Solution & Solution Flag
capacity of of (0+0+ 0+0)
8)0-0)
Solution
---
Sub-Cyap for Noder original oriser oib-mmne
Solution Flag
O......
O.....
O......
first
Figure 4: The process of preparing sub-CVRPs.
number of customer nodes; 8, denotes the demand of node i; C' denotes the capacity of the vehicle. In generating CVRP instances in test sets, we follow the common setting in [3] setting C' = 100 for 500-node CVRP (i.e.. CVRP500), C 200 for (VVRP10000 C 300 for CVRP2,000 and larger scale. In training, the capacity C' is uniformly sampled from 100 to 200 66 [6].
Similar to sub-TSP. Sub-CVRP is an open-loop CVRP (not forcing both starting and ending depot Zo for sub-route p² and p²) and also restricts the selection of starting and ending nodes. Moreover, each sub-CVRE instance has a special constraint on the capacity of the first and last sub-routes to ensure the legality of the merged solution. As shown in the right half of Figure I the capacity of the first and last sub-route restricted to be lower than the rest capacity of their connected partial sub-routes. Afterward, each pair of adjunct capacity constraints (shown in Figure 4 is normed to make the sum of 1. We follow the setting of BQ-NCO [4] in representing CVRP solutions, converting the route into a solution and an aligned solution flag which is set to for nodes before depot.
OP OP assigns each node a prize Pi and the goal is to maximize the total prize of all collected nodes, while keeping the total length of the route (a loop through all collected nodes) not surpassing maximum length T. OP contains depot node serving the route's ' starting node. We evaluate the UDC on OP500, OP1,000, and OP2,000 and set the T on all scales to 4. Assume solution route of OP is an r-length ordered sequence
(Ko, ..., x (No represents be depot, Po 0) and {D = dj. = O,... ......N, k = ........ }} is the N x cost metrics a N -ondes TSP problem, the objective function can be formulated as:
maximize f(x)) Σ Pi.
iE0
(10)
subject to 1(x) Σ da + dzy,z S T.
We follow the general OP (distance) (i.e., OP(dist) setting to generate OP instances 51 52
14
whose prize of each node is calculated Pj based on its distance to the depot. practice, we follow the setting in AM [51] A: = 1 [99
mux f J
do..
A The sub-OP in UDC contains segment of the 100
original solution while also randomly introducing some unselected nodes. By solving these sub-OPs, the conquering stage gains the potential to improve low-quality initial solution to optimal. For sub-solution s, the objective function of Sub-OP is f'(s) = Eise Ps. There is no normalization step in the conquering stage when solving OP. Sub-OP OP restricts the lengths of the generated sub-solution not surpassing the total length of the original sub-OP solution. One of the | sub-OPs contains the depot and the depot is restricted be included in the sub-solution of this sub-OP.
In testing, solving sub-OP limits the path length not to exceed the original sub-solution length, so continuously executing the conquering stage will result in a gradually shorter total route length I(x,)). So, we count the margin (i.e., T ((x,)) )) of the constraint in the current solution. In each conquering stage, we add the margin T [(x,) to the length constraint of random sub-OP.
PCTSP With a similar optimization requirement compared OP, PCTSP is also a typical CO problem [5]). PCTSP gives each node prize p. and a penalty 3,. The goal is to minimize the total
17

---

length of the solution route (a loop through all collected nodes as well) plus the sum of penalties of unvisited nodes. Moreover, constraint, PCTSP solutions should collect enough total prizes. The objective function is defined as follows:
minimize
f(x) Σ
doween + denes + Σ Bz:
(11)
subject to
E
We follow the settings in AM [5] and GLOP 133 to generate PCTSP instances, Pt ~ Uniform (0, ) 3, Uniform
We follow the setting in 13). define KN
9, 12, 15 for N
500, 1, 000, 2, 000.
Compared to OP, UDC uses similar way to process sub-PCTSP, introducing random unselected nodes in generated uub-problems and restricting the appearance of the depot. As a similar constraint of sub-OP, sub-PCTSP also restricts the total prize collected in the generated sub-solution to be larger than the total prize in the original sub-solution. Specifically, sub-PCTSP normalizes prizes of each node to A by dividing this constraint for better alignment, and the necessity of this procedure is demonstrated in Appendix with ablation studies. The objective function of sub-PCTSP solution
follows:
minimize
f'(8) = Σ docseet Σ Bi,
t=1
(12)
subject to Σd21.
The existing method GLOP [ divides the PCTSP into sub-TSP, this problem-specife design not only harms the accessibility optimal solutions but also impairs the generation ability of the framework to general CO problems.
SPCTSP SPCTSP evaluates the capability of the proposed UDC in dealing with uncertainty. As notable difference PCTSP, in SPCTSP, the real collected prize of each node only becomes known upon visitation but an expected node prize of E Uniform (0, 2p,) is known upfront. In solving SPCTSP with UDC, the expected node prize P is used to process sparse graph GD. heatmap H. and the encodings of conquering policy, while the real prize P: is only used to process the current states and constraints when constructing solutions of SPCTSP and sub-SPCTSP.
KP Besides VRPs, KP is also typical CO problem which can be formulated as follows:
minimize
f(X) =
Σ
U/
EX
(13)
subject to
Σ EX
w; I W.
where X (1,, represents the selection item indexes (i.e., KP solution) in knapsack and Uniform(0. 1) and w; ~ Uniform(O. 1) is the value and weight of candidate objects. In each conquering step, sub-KPs are randomly sampled. Sub-KP and KP are identical form and objective function, with only distinction on the number of decision variables and total capacity W. In training, UDC disables the Reunion stage in the DCR training method for KP, and the capacity W is sampled from 50 to 100. In testing, UDC adopts similar approach to OP in introducing the margin of maximum capacity (i.e., - -E w:) sub-KPs, adding the current margin (i.e., capacity minus current load) to random sub-KP.
18

---

OVRP As a variant on CVRP, OVRP calculates the objective function of each sub-route as open-
loops. The objective function of OVRP is calculated as follows:
9 1e'1-1
minimize
f(x)= Σ Σ
d dg
j=1
(14)
subject to
0 6: S C, i= 1,...,7,
Σ SC j= j=1,....4
EEP
ATSP ATSP is variant version of TSP with asymmetric cost metrics {D) = dj.k.j
O,..., N = 0 N. (i.e., ATSP and sub-ATSP have the same objective function as TSP and sub-TSP, respectively). Different from TSP, ATSP instances are inputted as cost metrics directly so this specificity makes impossible to use conquering models such as POMO [.) ICAM [16), etc. 41 When dealing with sub-ATSP, we employ a matrix-based sub-problem normalization method to normalize the longest item (i.e., edge) in cost metrics of sub-ATSPs to 1. For testing scale, the 1000-node ATSP is already huge in terms of the data size, while the 2000-node data is unable to generate and store in memory, so we refer to the testing scales of GLOP [33, conducting experiments on the 250-node (i.c., ATSP250), the ATSP500, and the ATSP1000.
MIS MIS originally defined on a graph G = EV where = |V| so in the dividing step we have GD G directly (without additional operations to construct the sparse graph 9D). For solution set X S 21,2, N]. the objective function of MIS to maximize the number of visited nodes in solution (i.e., fXX) [X) while ensuring edge connections
E between any two visited nodes. In training. follow the MIS instance generation process of ER[700-800) with y=0.15 355 The nodes in sub-MIS are randomly selected and nodes connecting visited nodes are constrained as unaccessible. The objective function of a sub-MIS solution is [(S) = SJ. The conquering policy for sub-MIS uses a Heatmap-based solver as well (i.e., AGNN in UDC) with non-autoregressive construction methods.
Min-max mTSP As a variant of VRP, the min-max vehicle routing problem (min-max VRP), instead of minimizing the total length of all sub-routes (i.e., min-sum), seeks to reduce the length of the longest one among all the sub-routes (i.e.. min-max). Min-max VRP has important application value in real life as well [71] (72) and researchers have also paid attention to solving them with deep learning techniques 622 42 The solution of min-max mTSP is defined similarly CVRP solutions, consisting of exactly M sub-routes (as a constraint on the number of total sub-routes) The objective function of min-max mTSP to minimize the length of the longest sub-route, which is as follows:
= (p': pp. ....... p M)
M f(x) max C(p'),
minimize
10'1-1
(15)
C(p') Σ d driiiie + d Pa
Similar to the normal min-sum objective function, the min-max objective function also be decomposed to independent objective functions of sub-problems so UDC can be evaluated on However, as the difference, the optimization of sub-min-max mTSP should encounter the lengths of sub-routes in adjunct sub- -roblrob.ems. For a sub-min-max mTSP with lengths of sub-routes in adjunct sub uu--robleems being lo and l,, the objective function of sub-min-mat mTSP solution with m sub-routes = {p'1 . ..?.....,p p' is calculated after adding l, to the first sub-route length C(p²)
and le to C(p"") ) as follows:
minimize
f(s) = max((C(p')) 4,, CI. + lch. (=1
(16)
Note that only holding two adjunct sub-problems unchanged can make the optimization of the sub- min-max mTSP consistent with the original min-max mTSP. So, to maintain optimality, the testing stage will not update adjacent sub-min-max-mile simultaneously.
19

---

C Method Details
C.1 Dividng Stgae:
Graph Construction
Liiht GNNs require constructing graph as input (the sparse graph GD). Some CO problems involved in this paper naturally have graph-like input (c.g., the MIS problem) so their sparse graph GD = G. However, the inputs of most other CO problems are coordinates or matrics. So. for the VRPs, we adopt the graph construction method in heatmap-base based solvers [3] and GLOP [3]. generally using the KNN method to connect edges in the edge set E E Ga. For CVRP, OVRP, ATSP, OP, PCTSP, SPCTSP, and min-max mTSP (min-max mTSP specifically uses dummy depots for constraints 62
we directly use a similar method to link edges based on KNN. In addition,
d. as the weight of (i,j) for 2 and use the KNN for edge connection as well. In the neighborhood selection where d/,j w.twy construction of all the involved CO problems (excluding MIS), we set neighborhood size K = 100, so the number of edges in the graph is limited to |E] OKN..
for the KP without neighborhood properties, we use 1 mix,e1.....
C.2 Dividing Policy: Anisotropic Graph Neural Networks
In modeling the dividing policy, we follow previous heatmap-based methods [39 on the choice of neural architectures. The graph neural network of UDC is an anisotropic GNN with an edge gating mechanism [40] Let hy and ef,, denote the d-dimensional node and edge features at layer i associated with node i and edge (i, respectively. The features at the next layer are propagated with an anisotropic message-passing scheme:
[+1 = h + aa(BNUU' h + (oEe() @ v'hji).. [+1 e + aa(BN(P'el, Q' R +' e.j
(17)
(18)
where Uº, VL, p Q¹ R Rddd are the learnable parameters of layer f, denotes the activation
function (we use SiLU 773 in this paper), BN denotes the Batch Normalization operator (74), A denotes the aggregation function (we use mean pooling in this paper), is the Hadamard product, and Nr denotes the outlines (neighborhood) of node i. We use a 12-layer (L=12) AGNN with a width of 64. The total space and time complexity of AGNN O(KNd), In training all involved CO problems, the learning rate of the dividing policy is set to Ir = 1e - 4.
the sigmoid function, O
T-revisit initial solution decoding. Next, based on the Eq. (4), the final layer edge representation et of AGNN is used to generate the heatmap. Heatmap-based solvers generally use an MLP to process the Ci.j. To integrate partial solution-related representations in the heatmap, UDC has designed an additional -revisit method, which will re-generate the heatmap by an additional T times using MLPs based on the existing partial solutions after multiple heatmap decoding steps. This operation increases the time and space complexity to O(TK Nd), but significantly improves the solution quality. Enabling the -eeeisiit method, the total initial solution generation strategy is shown below.
T-1 Ta (Zo (, 6) = p(ZO.1) II
T
if xo E
N Dim exp(Hss,.-1.00)))
0.
otherwise (19)
represents decoding solutions from the heatmap H. ~ GHH Φ, Fo $. (+1) and a new heatmap will generates every L steps. For CO problems without a depot (i.e., TSP, KP, MIS, ATSP), 1( nv and for other CO problems, 20 depot and p( = 1. In training UDC, set T J. In testing, we generally set T 1 N as well for 500-node to 4,999-node random instances. For efficiency, we set T 10 for very large-scale CO instances and CVX.Lib-XXI. datasets.
n
20

---

C.3 Conquering Stage:
Sub-problem Preparation
The detail of decomposing CO problems to their corresponding sub- CO problems is shown in B Generally, to generate the constraints of different sub-CO problems at this step, we need to 1) Keep the already determined solutions and likes unchanged (e.g., starting point in VRP, points connected to visited nodes in MIS) 2) Dispatch the original constraints to the current sub-problems (capacity of CVRP, capacity of KP, maximum length of OP, etc.). Usually, this kind of constraint is calculated from nodes in the original sub-solution. 3) In testing, consider the margin of constraints in the original CO problems (i.e., KP, OP, PCTSP, SPCTSP) to ensure the accessibility of optimal solutions.
C.4 Conquering Stage: Normalization
As presented in B TSP, ATSP, CVRP, OVRP, and min-max mTSP conduct normalization on the inputs of their sub-problems. ATSP normalizes the distance matrix by dividing by the maximum in each sub-ATSP cost matrix (i.e., d' mo.o.g ((l.... (do... and other sub-CO problems are normalized following the method in GLOP [13. Let (1'4 y/) denotes the coordinates of the i-th node after normalization, Tmax Emin, Vmaxx and Mmin denote the bounds of an sub-VRP instance { 3/1 )........ (In, yn)) (i.e., Tmax maxign Ii, et al.). Then, the coordinate transformation of coordinate (24, We) is formulated as follows:
dr,)
sc(2; Fmin
if I Fmax otherwise,
Fmin >
Ymax Vmins
sc(yi Umii
(20)
1/4
scly:
Ymnin
if Imax Fmin > otherwise,
Umax
ymin:
sc(2; Tminn)
where the scale coefficient sc max min -umus Maiin) sub-SPCTSP and sub- normalize prizes of nodes by dividing the total collected prize of the current sub-solution.
Besides normalizing the coordinates,
C,5
Conquering Stage: Conquering Policy
UDC adopts 5 solvers as the conquering policy, including AGNN 335 for MIS, ICAM [16 for TSP, CVRP, OVRP. and KP, POMO [5] for PCTSP, SPCTSP, OP, MatNet [4] for ATSP, and DPN 42 for min-max TSP. We employ 12-layer and 256-dimensional AGNN, 6-layer ICAM without AAFT, 6-layer POMO, and 5-layer MatNet, for these experiments respectively. In training, the learning rate well.
of all these solvers is set to Ir- le
The bascline calculation method in training conquering policies generally follows POMO (sam- pling 3 sub-solutions for each sub-CO instance), but the generation process of the 3 sub-solutions different for each CO problem. Some sub-CO problems (e.g., Sub-TSP, sub-CVRP, sub-OVRP, sub-OP) have symmetry (i.e., flipping sub-solutions will not change their objective values)
enable two sides conquering baseline, sampling & solutions on both the starting and ending nodes. For other CO problems, we sample 3 solutions from the starting point (e.g., the first randomly selected vertex in sub-MIS and the starting node of sub-ATSP). Please refer to the second last line in Table f whether the conquering policy enables the two sides conquering baseline in solving each CO problem. In testing, the conquering policy in the UDC samples only one sub-solution (i.e.. 3 = 1) for asymmetric sub-CO problems and sampling only two sub-solutions (i.e., 3 = 2) for symmetric ones.
Reason for using different solvers for different CO problems Using the same model for con- quering policy is an ideal choice. However, the experiment of UDC involves 10 CO problems, and some CO problems, like min-max mTSP 22] and ATSP AT. require specific model structures to process their inputs and constraints. Consequently, there is no constructive solver that can be used for all 10 involved CO problems. For each CO problem, UDC adopts the berf-performance constructive solver for the conquering policy (i.e., summarized in Table 7
UDC exhibits flexibility in choosing a constructive solver for conquering policy. For well- developed CO problems like TSP and KP, there are multiple constructive solvers available. Section 5.2 and Appendix E.6 present ablation study on the selection of these constructive solvers for TSP
21

---

and KP, respectively. Both sets of results indicate that the final performance of UDC is not sensitive the model selection for the conquering policy. Therefore, when generalizing UDC new CO problems, it may not be necessary to specifically choose which available constructive solver to model the conquering policy.
C.6 Total Algorithm
The total algorithm of training UDC is presented in Algorithm ! The total algorithm testing UDC on instances is presented in Algorithm
Algorithm 1 UDC: Training dividing and conquering policy on general large-scale CO problems.
1: Input: A CO instance G, number of node N; scale of sub-problems n; the number of sampled initial solution or; the number of sampled sub-solution 3; dividing policy o, conquering policy 0
2: Output: parameter ạ). 0
3: Generate sparse graph GD
4: Generate initial Heatmap H based p(H|SD, Ω ()
5: Sample initial tours: { xū } based on To in Eq. 4). (Eq. 19 for T reevist enabled.)
6: for i E {1, 2} do
7: Initialize the decomposition point: 2 i
8: Calculate the number of sub-tours decomposed from tour: C' == A
9:
{g)-1. ......9'
Pac/1
10:
((
(00pppt (o-+((C-))++chh--.. {
11: Apply coordinate transformation and constraint normalization to [9] ..... 9ac
12:
for E (I.......C)))) ,CC, E (1..... do
13:
Sample iJ ~ <-16% - ())
ifi= then
15:
Update conquering policy - 0+ VoCcl
end if
17:
i then
Update conquering policy / + 0 (9L end if end for
19:
21:
for & E (1...,,, aC) do
22:
Select best sub-solution among 3 samples: 8 arggax arggmax ...... of.. (...))
23: Substitute the s with improvement on f($)) in sub-CO problems the original
solution.
Merge solutions: {z!....<;) x; = [Concat($f...... sc)... "
s.c)
25:
end for
26:
end for
Update dividing policy o+ VgLa(9)
C.7 MDP of the dividing and conquering stages
In addition to the algorithms in Appendix C.6 this section will provide necessary descriptions of the training objective of both policies and the implicit MDP for the two stages.
should be noted that the training objectives and MDP are not designed originally from UDC, they also adopted in series of neural divide-anndconquee methods [13 20
Objective functions of optimizing the two networks For a CO problem (or sub-CO problem) with the objective function, f(-), the goal of training both networks is to maximize the reward functions of their corresponding MDP. The reward is -f(22) for the dividing policy (AGNN in UDC), (s*) for the constructive solver (conquering policy) in the Conquer step (i.e., the first conquering stages), and =f(=²) in the Reunion step.
22

---

Algorithm 2 UDC:
Solving general large-scale CO problems.
1: Input: A CO instance 9, number of node N; scale of sub-problent n; the number of sampled
solution a; number of conquering stage
2: Output: The best solution a
3: Generate sparse graph 9n
4: Generate initial Heatmap H based pHHl 2,
5: Sample a initial tours: [æti..... #g based on w. in Eq.
(Eq. 19 for Trevisit enabled.)
B 2 for TSP, ATSP, OP, PCTSP, SPCTSP.
6: for i E [1....,r} do
7: i <2 then
8: Initialize the decomposition point: < end if
9:
10:
if 23 then
Initialize the decomposition point: p Uniform
12:
end if
Calculate the number of sub-tours decomposed from tour:
[
14:
(9) .....96 9i-1
" ) }
15:
{( 1.p.p........................... (--ppppCCC--ppttaa h.... {ae pppta
H
16:
Apply coordinate transformation and constraint normalization to {g gart) for k {1, (1....,aC))53 E (1....,, 33} (f=1 2, see Appendix C.5 do
17:
Sample s Te 10 _.0 end for
19:
20:
for k E (I...., do
21:
3 = argmax o' "
i. Substitute the 8 with no improvement on f(8)) in sub-CO problems to the original solution.
22:
23:
Merge solutions: (x) o. + {Concat (8)
8 x ot 1pppC++))
Concat($ (a-1))++1 8 Sac x (11ptt(+1pp))
end for 26: t
argmax (em...e [
27:
end for
MDP for the dividing stage: represented as follows:
The MDP Ma ASa ra, Paj of the dividing stage can be
State. State sta E Sa represents the current partial solution. The state in the i-th time step is the current partial solution with nodes sta, Zo, = (I), X2, Tt). sta,o is empty and sta, = Vo.
Action & Transaction. The action is to select a node at time step i.e., Od, 21+1. The chosen node needs to ensure that the partial solution sta,++1 (21, Ø2, Ft, x141) valid (i.e., sta, E ?2).
Reward. Every single time step has the same reward ra, = fxx)) which the objective function value of the final solution 22 after the whole DCR process.
Policy. The policy æa is shown in Eq. (Eq. for T-revisit enable).
MDP for the conquering stage: The MDP M, As, Pe) of any single conquering stage is represented similarly as follows:
State. Each state st. E S. represents the current partial solution. The state in the t-th time step is the current partial solution with nodes stc,t = $; ($1, $2,... St). stz,o is empty and ste,7 = s.
Action & Transaction. The action is to select node at time step as well, i.e., Gc,t S141-
Reward. The reward in each time step becomes the objective value of sub-CO solution i.e.,
Te,t = -f()))
Policy. The policy ne is shown in Eq. 5
23

---

C.8
Time & Space Complexity
Table 6: Comparison time and space complexity.
LEHD
ICAM-single-star ICAM-N-start
UDC-a²
UDC
Time
O(N*)
O(N²)
O(N
OlTTKN +n²) OlaKN + + OlaKN + a
O(aTKN + +m²)
Space
((N3)
O(N7)
O(N2)
With lightweight GNN for global partition and constructive solvers for parallel small-scale sub- problems, both the time and space complexities of UDC are reduced compared to single-stage SL-based sub-path solvers and single-stage RL-based constructive-based solvers. When sampling T-revisit enabled initial solutions (7'=1 for disabling the T-revisit), the dividing stage of UDC has time complexity of O(TTKN and space complexity of N).
Both the time and space complexity of a single conquering stage on single sub- sub-problem is O(n").
There are a # parallel sub-problems for each instance so the complexity should be a [ [O(n"). However, the ox N sub-problems can be processed in parallel (as batch size = al N () in GPUs, so the total time complexity of UDC with conquering stages can be considered as O + + and the space complexity is O(a N + !
tubb-path-baae constructive solver adopts decoder-only model structure so for r-length solution, time complexity is (²) = ((N)) (d is the dimension embeddings, we regard r (n)) and the space complexity is ( ICAM is representative RL-based constructive solver, adopting an encoder-dccooder-bseee model structure. The space complexity (N2)) and the time complexity is O(rNd) = O(N2) for single-start ICAM and O(rN'd) ( for N-start (multi-start) ICAM. The comparison of time and space complexity is listed in Table 6, UDC generally adopts the parameter of T 10, 1, K 100 in testing. So on CO problems with N 1, 000, the proposed UDC-22 demonstrates less inference complexity compared to ( and exhibits superior efficiency. Empirical results especially very-large-scale experiments (N 5, 000) in Table and Appendix D.5 prove the above statements.
24

---

D Experiment Details
D.1 Hyperparameter
Hyperparameters of all 10 involved CO problems are listed in Table 7 Training UDC on most CO problems adopts the varying-size [45] and varying-constrain 6 setting. ICAM and POMO used for conquering policy are 6-layers, DPN is 3-layers, and MatNet is 5-layer. AGNN for conquering sub-MIS is 12-layer with 256. In training UDC for TSP, we don't conduct the varying scale training in the first 50 epochs with 80.
Table 7: Hyper parameter of training CO problems.
Hyperparameter
TSP
PCTSP,SPCTSP
CVRPOVVP
OP
Varying training size N
500-1,000
500-1,000
500-1,000
500-1,000
Varying training constraint Sub-path scale n in training
9-12
50-100
100
100
100
100
40
30
40
40
in training
50
50
40
50
Epoch size
1,000
1,000
1.000
1,000
Epoch-time
28m
29m
42m
22m
Total epochs
500
200
DCR enable
TRUE
TRUE
TRUE FALSE
TRUE
Two sides conquering baseline Conquering Policy
TRUE
TRUE
TRUE
ICAM
POMO
ICAM
POMO
Hyperparameter
KP
MIS/ER[700-8001)
min-max mTSP
ATSP
Varying training size N
500-1,000
700-800
500-1,000
250-500
Varying training constraint
50-100
30-50
Sub-path scale n
100
200
100
50
in training
50
35
25
30
@ training
35
30
Epoch size
1,000
1,000
1,000
1,000
Epoch-time
25m
7m
42m
29m
Total epochs
120
1,000
200
300
DCR enable
FALSE
TRUE
TRUE
TRUE
Two sides conquering baseline Conquering Policy
FALSE
FALSE
FALSE DPN
FALSE
ICAM
AGNN
MatNet
It can be seen that UDC adopts similar setups solve different problems. The third to last and the second to last rows of Table are related to the environment and the last row is unable to use
consistent setup and some flexibility in choices. Ablation studies Section 5.2 and Appendix E discuss the setting of some listed hyperparameters, such as a in testing, DCR enable=False for KP. and the selection of conquering Policy in KP and TSP.
25

---

D.2
Experiment on OVRP, MIS, ATSP, KP, and min-max m TSP
The main part of this paper has evaluated the proposed UDC on large-scale instances of repre- sentative CO problems. In this section. We will further evaluate the proposed UDC on more CO problems. OVRP is variant of CVRP that has been widely involved in recent multi-task NCO We introduce this problem to test UDC's ability to handle open loops and distant point-to-point relationships based on CVRP. MIS is classic CO problem widely used evaluate heatmap-based solvers [55], which can test the capability of UDC to handle CO problems on graphs. The experiment on ATSP can evaluate the flexibility of the UDC framework and its ability to process matrix-based data. We also employ KP to test the ability of UDC to handle CO problems without neighborhood properties. Most importantly, min-max mTSP introduced to test the ability UDC to handle problems with different aggregation functions (i.e., the max aggregation function) except for min-sum (i.e., objective functions of all the else CO problems). For OVRP, KP, ATSP, and min-max mTSP in this section, UDC works to minimize rather than maximize (like OP and MIS) their objective functions.
work 75 76
The experiment result is shown in Table 8 Compared to the current best NCO method 75] POMO (Trained on OVRPI00 with settings in 75 superiority in large-scale OVRP problems.
Experiment on OVRP:
UDC demonstrates significant
Table 8: Objective function (Obj.), Gap to the best algorithm (Gap), and solving time (Time) on 500-node (128 instances), 1,000-node (128 instances), and 2,000-node OVRP (16 instances).
OVRP500
OVRPI,000
OVRP2,000
Method
Obj-
Gap
Time
Obj-
Gap
Time
Obj-4
Gap
Time
LKH3
23.31
16m
28.96
32m
39.88
27m
POMO
28.73
22.21%
1.5m
59.26
104.61%
16m
108.82
172.90%
16m
UDC-x:(a=50)
25.82
9.86%
1.4m
33.01
13.97%
51.11
28. 18%
42s
UDC-zso(a=50)
24.39
3.77%
7.9m
29.95
3.41%
15.5m
44.19
10.82%
4.5m
UDC-0220 (o=50)
24.18
2.85%
34.5m
29.66
2.39%
1.1h
43.35
8.71%
20m
The MIS problem is widely adopted CO problem for heatmap-based solvers. UDC can also solve the MIS problem by employing AGNN as the conquering policy. Following DIFUSCO, we evaluate the proposed UDC on the Erdös-Rényi (ER) 77 dataset. We evaluate the MIS on ER[700-800] with p=0.15. We use the test set provided in [35], and the results on it are shown in Tableg 9 UDC can also achieve good results MIS after several conquering stages. Compared to the heatmap-base based solver that originally relied on search algorithms, UDC shows better efficiency.
Experiment on MIS:
Table 9: Performance on 128-instance ER[700-800 7000000000000000 test set (provided in DIMES 35 All the results reported in DIMES (35) DIFUSCO [39 and T2T (66). For MIS, the larger objective value (Obj.) is better.
ER-[700-800)
Method
Obj.t
Gap.
Time
*
44.87
52.13m
Gurobi*
41.38
7.78%
50.00m
hline Intel*
38.8
13.53%
20.00m
DGL*
37.26
16.96%
22.7Im
LwD*
41.17
8.25%
6.33m
DIFUSCO-greedy
38.83
13.46%
8.80m
DIMES-greedy
38.24
14.78%
6.1mm
T2T-greedy
39.56
11.83%
8.53m
UDC-aa(a=50)
41.00
8.62%
40s
DIMES-MCTS*
42.06
6.26%
12.01 m
DIFUSCO-MCTS*
41.12
8.36%
26.67m
T2T-MCTS*
41.37
7.80%
29.73m
UDC-=ao(a=50)
42.88
4.44%
21.05m
26

---

Experiment on ATSP: On ATSP, we compare the proposed UDC to traditional solver OR-Tools, constructive solver MatNet, and neural divide-and- and-conquer method GLOP. Results on ATSP250 to X00P are shown in Tanl results of MatNet and GL.OP are reported from GLOP [3 We follow the data generation method MatNet [41] and such data generation method is unavailable on larger scales (i.e., ATSP2,000). Results demonstrate the capability of UDC on large-scale ATSP and the superiority of UDC compared to GLOP. The advantage of performance contributes to the unified training scheme (ATSP of GLOP can be regarded as the separate training UDC.).
Table 10: Objective function (Obj.), Gap to the best algorithm (Gap), and solving time (Time) on 250-node (128 instances), 500-node (128 instances), and 1, 1,000-node ATSP (16 instances). a 20 for ATSP250 and ATSP500 and a 10 for ATSP1,000.
ATSP250
ATSP500
ATSPI,000
Methods
Obj
Gap
Time Im
Obj
Gap
Time
Obj
Gap
Time
OR-Tools
1.94
5.32%
2.00
1.57%
2m
2.08
0.14%
2m
MatNet
4.49
143.89%
GLOP
2.10
14.07%
2.79
34.39%
UDC-#2
1.96
6.63%
21s
2.05
3.92%
39s
2.16
3.85%
6s
UDC-#5a
1.84
7m
1.97
13m
2.08
1.5m
On KP, we involve OR-Tools (generally optimal on KP), POMO, and BQ as baselines. As shown in Table [1] compared to BQ and POMO, both the UDC-#50(a=l) and (D=1 exhibit the best learning-based performance KP500 and KP1,000. Moreover, UDC demonstrates outstanding time efficiency on KP1,000 and larger-scale KPs.
Experiment on KP:
Table 11: Objective function (Obj.), Gap to the best algorithm (Gap) 500-node, 1,000-node (128 instances), and 2,000-node, 5,000-node KP (16 instances). OR-Tools can generate solutions real time. The best learning-baat method is marked by shade.
KP500, W-00
KP1,000, =1000
Method
Obj-
Gap
Time
Obj
Gap
Time
OR-Tools
128,3690
258.2510
BQ
128.2786
0.07%
37s
258.0553
0.08%
4.4m
POMO
128.3156
0.04%
5s
254.5366
1.44%
27s
(DC==sa(o=1)
128.3373
0.02%
14s
258. 1838
0.03%
24s
UDC-#2sn(a=))
128.3583
0.01%
258.2236
0.01%
56s
KP2
KP5,000,
5500
Method
Obj-
Gap
Time
Obj
Gap
Time
OR-Tools
518.2880
1294.2263
UDC-=aa(o=1)
518.1653
0.02%
1293.9041
0.02%
16.2s
UDC-22sofo=))
518.2337
0.01% %
24s
1294.0966
0.01%
40s
27

---

Experiment on min-max mTSSP: For min-max mTSP. we involve heuristic method hybrid ge- netic algorithm (HGA) 78 and LKH3, constructive method (parallel plamning) DAN [46], Equity- Transformer [62] and DPN 42
We use the dataset provided in DPN and the model of Equity- Transformer and DPN are finetuned on N=500, M E (30..... 50]. The results in Table demon-
strate that the UDC can get outstanding results on CO problems with min-max objective functions as well.
Table 12: Objective function (Obj., Gap to the best algorithm (Gap) on 500-node, 1,000-node min-max mTSP instances (100 instances). The best result in bold.
min-max mTSP
N=500.M=30
N=500.
N=1.000.M//50
Methods
Obj-
Gap
Obj.
Gap
Obj.
Gap
HGA
2.0061
2.0061
0.00%
2.0448
LKH
2.0061
0.00%
2,0061
0.00%
2.0448
0.00%
DAN
2,2345
11.39%
2.1465
7.00%
2.3390
14.39%
SquityTrranfforme-FFiie
2.0165
0.52%
2.0068
0.04%
2.0634
0.91%
DPN-Finete
2.0065
0.02%
2.0061
0.00%
2.0452
0.02%
UDC=asa(a=I)
2.0840
3.89%
2.1060
4,99%
2.1762
6.43%
(D=5msa(a=50)
2.0087
0.13%
2.0060
2.0495
0,23%
D.3 Experiments on TSP & CVRP Instances with Various Distributions
The cross-distribution generalization ability of NCO solvers also necessary. we evaluate UDC on the Rotation distribution, and the Explosion distribution provided in Omni_ VRP (79 on TSP and CVRP. The result is shown in T3 UDC demonstrates outstanding robustness on large-scale CO problems with different distributions.
Table 13: Experimental results on cross-distribution generalization. All four test sets are obtained from Omni VRP [79] and contain 128 instances. The runtime marked with an asterisk (*) is proportionally adjusted (128/1,000) to match the size of our test datasets. The best learning-based method is marked by shade.
TSP1,000, Rotation
TSP1,000, Explosion
Method
0bj4
Gap
Time
Obj
Gap
Time
Optimal
17.2
0.00%
15.63
0.00%
POMO
24.58
42.84%
8.5m
22.7
45.24%
8.5m
V
19.53
14.30%
49.9m
17.75
13.38%
49.9m
ELG
19.09
10.97%
15.6m
17.37
11.16%
13.7m
UDC-@gso(a=1)
18.19
5.73%
61s
16.76
7.21%
61s
CVRP1,000, Rotation
CVRPP1000 Explosion
Method
Obj-
Gap
Time
Obj.
Gap
Time
Optimal
32.49
0.00%
32.31
0.00%
POMO
64.22
97.64%
10.2m
59.52
84.24%
11.0m
Omni Omni_VRP *
35.6
10.26%
56.8m
35.25
10.45%
56.8m
ELG
37.04
14.00%
16.3m
36.48
12.92%
16.6m
UDC=#g50(==1)
34.91
7.45%
3.3m
34.75
7.55%
3.3m
28

---

D.4 Experiments on MIS Instances with Various Distributions
In addition the TSP and CVRP, we conduct generalization experiments on the MIS problems. We conduct zero-shot generalization on the model trained by ER graphs with N ~ U7700, 800) and p=0.15 five other datasets, including:
A random ER graph dataset with -=720 and p=0.05. (average 12,960 undirected edges)
A random ER graph dataset with N=720 and p=0.25. (average 64,800 undirected edges)
A random ER graph dataset with N~2,000 and p=0.05. (average 100,000 undirected edges)
The ego-Facebook data in Stanford Large Network Dataset Collection (SNAP) (https
//snap. /ssap.staaford.eett sttafford.eduddatte
(4,039 nodes, 88,234 undirected edges)
The feather-lastfi-ssoiial data in SNAP. (7,624 nodes, 27,806 undirected edges)
All the first three ER random datasets contain 128 graph instances, and we consider the last two data as a single graph. The table below exhibits the comparison results between UDC and the SOTA heuristics KaMIS (implemented on h giubt.tt..u..u. com/ com/Karll Karl SaarssuueMII/KKKK //MMIIS) on the original in-domain dataset (ER-[700-800), p=0.1) and the five out-of-domain datasets mentioned above. Obj. represents the objective function value, Gap represents the performance gap compared to the best algorithm and Time is the time consumption for solving the whole dataset.
Table 14: Objective function (Obj.), Gap to the best algorithm (Gap) on 500-node, 1,000-node min-max mTSP instances (100 instances). For MIS, the larger objective value (Obj.) is better.
Dataset
ER, N=720, p=005
ER-[700-800), ((nmm(nn-mmma))
Method
Obj-t
Gap
Time
Obj-t
Gap
Time
KaMIS
99.5
40.6m
44.9
52.13m
UDC-#a(a = 50)
79.5
20.10%
8s
41.0
8.62%
40s
UDC-#5o(a = 50)
89.5
10.07%
9.03m
42.9
4,44%
21.05m
UDC-aasola 50)
94.5
5.03%
44.84m
43.8
2.41%
1.73h
Dataset Method
ER, N=720, p-225
ER, N=2,000, p=0.05
Obj-t
Gap
Time
Obj.t
Gap
Time
KaMIS
28.2
1.4h
133,9
3h
UDC-xo(a 20)
21.6
23.46%
58s
116.9
12.72%
2m
UDC-#50(a = 20)
25.3
10.54%
21m
119.1
11.05%
21m
UDC-0250(a = 20)
26.4
6.59%
63m
122.9
8.25%
90m
Dataset
SNAP- S.AP-eg-Facceboo
ENAP-featber-lasffnnsoiii
Method
Obj-1
Gap
Time
Obj.1
Gap
Time
KaMIS
1052.0
155s
4177.0
0.1s
UDC-cala = 1)
767.0
27.09%
68
3622.0
13.29%
2s
UDC-æ250(a
901.0 O
14.35%
11s
3751.0
10.20%
13s
UDC-a2200
1009.0
4.09%
60s
4067.0
2.63%
80s
Compared to KaMIS, UDC variants exhibit relatively stable performance gaps across datasets with various node sizes (n), sparsity (p), and generation methods, demonstrating good generalization ability. Moreover, except for the extremely sparse graph SNAP-featheer-astfn--ccca.l UDC variants have significant advantages over KaMIS terms of time.
Unfortunately, we are unable to re-implement any learning- based methods for MIS (e.g. Difusco 39 and T2T (66)), so we are unable compare the generalization ability with other learning based algorithms. However, the stable performance gaps on different datasets partially demonstrate certain out-of-domain generalization performance of UDC on MIS.
29

---

D.5 Experiments on Very Large-scale
This section evaluates the proposed UDC on very large-scale instances (i.e., 5,000-node, 7,000-node, and node00-node ones). On mod000-node and n,00 CVRP, the proposed UDC-2250(a=1) variant still demonstrate better performance.
However, on very large-scale TSP (results shown in Table 16), the UDC fails to converge to an outstanding performance in testing. We find that this is mainly due significant decrease in effectiveness when generalizing the dividing policy to 10,000-node TSP instances. So, we substitute the dividing policy to the random insertion used in [33, shown Table The UDC with random- insertion-based initial solution achieved outstanding results. The experimental results preliminarily verify that in some problems such as TSP, UDC may generate unreliable dividing policies when processing scale generalization. In this case, using other initial solutions with a similar shape to the optimal solution can also obtain figh-quality solutions.
Table 15: Objective function (Obj.), Gap to the best algorithm (Gap) 5,000-node, 7,000-node The best result in bold and the best learning- based method is
CVRP (100 instances) 12 13
marked in shade.
CVRP5,000
CVRP7.000
Methods
Obj-
Gap
Time
Obj--
Gap
Time
LKH3
175.7
28.53%
4.2h
245.0
30.17%
14h
BQ
139.8
2.32%
45m
LEHD
138.2
1.09%
3h
ICAM
136.9
0.19%
50m
TAM(LKH3)*
144.6
5.80%
35m
196.9
4.61%
Ih
TAM(HGS)
142.8
4.48%
1h
193.6
2.86%
1.5h
GLOP-G (LKH-3)
140.4
2.69%
8m
191.2
1.59%
10m
UDC-
167.1
22.27%
8m
248.9
32.22%
8m
UDC-aso(o=1)
140.8
2.99%
195.8
4.03%
13m
UDC=a920(o=1)
136.7
16m
188.2
21.4m
Table 16: Objective function (Obj.). Gap to the best algorithm (Gap) on 5,000-node (128 instances), 10,000-node TSP instances (16 instances). The best result is in bold and the best learning- based method is marked shade.
TSP5,000
TSP10,000
Methods
Obj-
Gap
Time
Obj 71.8
Gap
Time
LKH3
50.9
12m
1h
BQ
58.1
14.10%
8m
LEHID
59.2
16.23%
20m
ICAM
60.3
18.34%
8m
GLOP-more revision
53.3
4.54%
21m
75.3
4.90%
1.8m
S0-mixed*
52.6
3.25%
55m
74.3
3.52%
2h
H-TSP
55.0
7.99%
26s
77.8
8.33%
50s
UDC-=a(a=I)
56.2
10.28%
1.6m
82.1
14.35%
7m
UDC=+00(0=))
54.5
7.06%
2.6m
79.2
10.41%
7m
Table 17: Objective function (Obj.), Gap to the best algorithm (Gap) 10,000-node, 100,000-node TSP instances (16 instances). The best result is in bold and the best learning- based method is marked in shade. We use the TSP100,000 result reported in GLOP 13 on probably different test set.
TSP10.000
TSP100,000
Methods
Obj
Gap
Time
Obj-
Gap
Time
LKH3
71.8
1h
226.4
8.1h
DIMES+$
86.3
20.18%
3.1m
286.1*
26.375
2.0m
GLOP-more revision
75.3
4.90%
1.8m
238.0*
5.12%*
2.8m
UDC-250(a=I)
74.7
4.11%
18s
235.8
4.15%
3.5m
UDC-#zm0(a=))
74.7
4.03%
235.6
4.05%
11.5m
30

---

E Ablation Study
E.1
Ablation Study on r (Convergence Speed Testing)
The proposed UDC adopts the multi-conquering stage (r stages) in common variants. Therefore, as an iterative method, the effectiveness of our testing phase is closely related to the testing time. We record the iterative convergence curves of the objective function value (Obj.) during testing TSP1,00 ,000, CVRP1,000, and PCTSP1,000 1,000 with UDC(a=1), UDC(x=50), GLOP [13, LEHD (RRC) [8) and DIFUSCO 39 The results are shown in Figure 5 and curves (except for DIFUSCO, which
reported results) are generated under the same test set and computation resources. We can obtain the following conclusions:
For the two variants of UDC, UDC(a=1) can generate better solutions compared to UDC(a=50) in limited period but will trap into local optima quickly. For PCTSP, there no significant difference in the final convergence result between the two versions.
2. Compared to the advanced neural divide-and-conque and-conuuer method GLOP, the objective functions of both the two UDC variants always significantly lead when going through the same testing time.
3. Compared with the search-enabled heatmap-based method DIFUSCO, although the heatmap-based method can ultimately obtain a superior value of the objective function through sufficient search on TSP, the two variants of UDC lead in the value of the objective function in finite period.
4. Compared to the SL-based sub-path solver LEHD with RRC (8) the RL-based UDC(a=50) variant demonstrates competitive objective function values on CVRP, while both the two variants of UDC show higher efficiency TSP and CVRP.
128-insince TSP1000
UpC-e--)
UDC(j-1)
(DC(e-90)
UDC+a 583
GLOP
GLOP
DIFUSCO
GLOPILKH3I [FHD/BAC)
(EHDIHIC)
Timeim)
Timelmi
(a) TSP1,000
(b) CVRP1,000
128-instnce PCTSP1000
61.0P
Time(m)
(c) PCTSP1.000
Figure 5: Testing curves for ablation study.
E.2 Ablation Study on a (Sampled Initial Solutions)
In this subsection, we demonstrate the change in effectiveness UDC relating to the numbers of initial solutions (i.e., a) for each CO problem. We use different values to test the TSP, CVRP,
31

---

OP, PCTSP, and SPCTSP (CO problems evaluated in the main paper) on their original test set. As exhibited Table I8 results with a 50 always demonstrate significantly better performance but much more time consumption.
However, the sensitivity of a: performance varies among different CO problems. In TSP, CVRP, and OP, the differences between results with a 50 and results with = appear to be quite significant, while in PCTSP and SPCTSP, employing more initial solutions demonstrates no significant effect. Moreover, On 2,000-node problems TSP, CVRP, and OP, the effect of a 50 is particularly pronounced. Since the difference in initial solutions entirely from sampling the dividing policy, more significant distinction between a 50 and 1 variants might mean that the initial solution prediction is more difficult these instances. Meanwhile, the more significant difference in 2,000-node instances indicates that compared to (S)PCTSP, the dividing policy has worse scaling ability on TSP, CVRP, and OP.
Table 18: Ablation the number of initial solution Objective function values (Obj.), Gap the best algorithm (Gap) on 500-node, 1,000-node, and 2,000-node instances are listed.
TSP500
TSP1,000
TSP2,000
Methods
Obj.
Gap
Time
Obj
Gap
Time
Obj.
Gap
Time
LKH3
16.52
5.5m
23.12
24m
32.45
1h
UDC==>(a=I)
17.12
3.62%
10s
24.06
4.05%
18s
34.44
6.13%
48s
UDC-a50 (o=1)
16.92
2.41%
14s
23.68
2.42%
26s
33.60
3.54%
1.1m
UDC-2a(a=50)
16.94
2.54%
20s
23.79
2.92%
32s
34.14
5.19%
23s
UDC-250
16.78
1.58%
4m
23.53
1.78%
8m
33.26
2.49%
15m
CVRP500
CVRP1,000
CVRP2,000
Methods
Obj
Gap
Time
Obj-
Gap
Time
Obj-
Gap
Time
LKH3
37.23
7.1h
46.40
8.18%
14m
64.90
8.14%
20min
UDC=#z(a=I)
40.64
9.15%
46.91
9.09%
2m
68.86
14.74%
3.1m
UDC-2sa(a=)
38.68
3.89%
1.2m
43.98
2.28%
2.2m
62.10
3.48%
3.5m
UDC-2250(Q=I)
38.32
2.93%
2.1m
43.46
1.06%
3,4m
61.03
1.70%
5.5m
(0=5=)
40.05
7.57%
1m
46.09
7.18%
2.1m
65.26
8.75%
5m
UDC-#5a (0=50)
38.35
3.01%
9.6m
43.48
1.11%
14m
60.94
1.55%
23m
UDC 100C2220(a=50
38.00
2.06%
1.1h
43.00
1.1h
60.01
2.15h
OP500
OP1,000
OP2,000
Methods
Obj.t
Gap
Time
Obj-t
Gap
Time
Obj-t
Gap
Time
EА4OP
81.70
7.4m
117.70
63. 1m.4m
167.74
38.4m
UDC-æx(a=l)
75.28
7.86%
17s
109.42
7.03%
25s
135.34
19.32%
5s
UDC=
78.02
4.51%
23s
111.72
5.08%
23s
139.25
16.99%
8s
UDC-æzso(a=I)
79.27
2.98%
48s
113.27
3.76%
1.1m
144.10
14.09%
21s
(D=5
75.61
7.46%
25s
110.25
6.33%
40s
147.48
12.08%
10s
UDC UDC=#50
78.55
3.86%
5m
112.59
4.34%
9.5m
151.89
9.45%
2m
UDC=#2u
79.81
2.32%
24m
114.16
3.01%
47m
159.10
5.15%
11m
PCTSP500
PCTSP1,000
PCTSP2,000
Methods
Obj
Gap
Time
Obj-
Gap
Time
Obj-
Gap
Time
Tools*
14.40
10.19%
16h
20.60
13.34%
16h
UDC==2(o=1)
13.95
6.78%
34s
19.50
7.30%
27.22
8.87%
18s
UDC-25a
13.25
1.39%
42s
18.46
1.59%
1.3m
25.46
1.81%
23s
UDC-2250(a=I)
13.17
0.74%
80s
18.29
0.61%
25.04
0.12%
53s
UDC-a2(0=50)
13.80
5.61%
40s
19.32
6.32%
1.6m
26.76
7.02%
24s
UDC-#50(a=500
13.15
0.63%
7m
18.33
0.86%
25.22
0.85%
3.4m
UDC=#230(a=50))
13.07
40m
18.18
70m
25.01
17.6m
SPCTSP500
SPCTSPI,ON
SPCTSP2,000
Methods
Obj-4
Gap
Time
Obj
Gap
Time
Obj-
Gap
Time
UDC-22(a=I)
14.21
8.20%
42s
20.01
9.04%
1.1m
28.15
11.15%
20s
UDC-#sa(a=l)
13.40
2.04%
1m
18.93
3.11%
1.4m
26.24
3.60%
29s
UDC-22s0(a=I)
13.24
0.82%
2.3m
18.54
1.03%
2.6m
25.38
0.22%
1.1m
UDC-
14.05
6.98%
40s
19.74
7.52%
1.6m
27.98
10.48%
24s
ADC-#sa(a=30
13.27
1.01%
7m
18.71
1.9%%
15m
26.17
3.34%
3.4m
UDC-#230(a=500
13.13
40m
18.35
70m
25.33
17.6m
32

---

E.3 Ablation Study on the Generation Method of Initial Solutions
To check the ability of the dividing policy, we further conduct experiments on TSP with different generation methods of initial solutions, and the results shown in Table[I9]emoonsttr demonstrate the significance of good initial solution the final performance. The UDC variants with random initial solution or nearest greedy initial solution cannot converge to good objective values even with 50 conquering stages. Moreover, from TSP500 to TSP2,000, the dividing policy of UDC produces similar results to the heuristic algorithm random insertion (used in GLOP 13 which verifies the quality of the dividing policy.
Table 19: Ablation different algorithms as initial solutions Zn. The conquering stages of all the variants are the constructive of UDC. Random-UDC directly represents a random solution as the initial solution. Nearest Greedy-UDC uses the nearest greedy algorithm (starting from the first node) and Random Insertion-UDC employs the random insertion heuristic as the initial solution. a = in all UDC variants. UDC-a:, and UDC-W50 is the original version. Obj. is the objective value and Gap represents the gap to the best method.
Method
TSP500
TSP1,000
TSP2,000
Method
Obj.
Gap
Obj.
Gap
Obj.
Gap
Concorde
16.52
23.12
32.45
Random- UDC
33.98
105.68%
67.82
193.34%
134.98
315,98%
Random- Landom-UDC--50
26.11
58.01%
52.48
126.98%
104.48
221.96%
Nearest Prredy-UDC-az
18.48
11.87%
26.42
14.27%
37.48
15.50%
Nearest Greedy- UUeedy-DCC-s0
17.88
8.23%
25.75
11.38%
36.80
13.40%
Random Insertion UDC-#2
17.09
3,45%
24.08
4.17%
34.00
4.78%
Random Insertion Cecetton-UDC-are U50
16.84
1.93%
23.75
2.73%
33.55
3,38%
UDC-zz(a 1)
17.12
3.62%
24.06
4.05%
34.44
6.13%
UDC-#sala
16.92
2.41%
23.68
2.42%
33.60
3.54%
E.4 Ablation Study Components
In the main part, we have shown the result the ablation study on the unified training scheme and the conquering policy, demonstrating the superiority of the unified training scheme and the flexibility in selecting a model for the conquering policy.
In this sub-section, we conduct experiments to demonstrate the necessity of three other components of UDC, including the Reunion step in the DCR training method, and the coordinate transformation& constraint normalization in the conquering stage.
Figure 6 (b) compares the training efficiency of the Original UDC to the UDC variant without the Reunion step in DCR (i.e., the w/o Reunion in the DCR variant) and the UDC variant without the coordinate transformation (i.e., normalization) in the conquering stage (i.e., the w/o Norm in the Conquering Stage). The training curve on both TSP500 and TSP 1,000 demonstrates the significance of both two components and the Reunion step seems more significant for better training convergency,
Moreover, we also evaluate the significance of constraint normalization on PCTSP. As shown in Figure c),,, The final performance after 250 epochs and training efficiency of UDC is strongly nerfed without the normalization on the total prize lower-bound in PCC-SS)
T5 bioiio Components
1000 Ablatio Components
Companents
UDC
2012
wil
Mro Reunion DCR
win Norm in Conquering Stage
wib Norm Conqueting Stage
Norm Conquering Stage
Epactts
Epochs
Epochs
(a) TSP500
(b)
TSP1,000
(c) PCTSP1,000
Figure Training curves for ablation study.
33

---

E,5 Ablation Study on Disable DCR in KP
For KP, there will be no sub-optimal connection as shown in Figure 2 so there no logical difference in whether DCR is enabled or not. We provide the KP results of Enable DCR in Table 20 and the results support the above conclusion.
Table 20:
Ablation on whether to enable the DCR in training UDC for KP. The version with disabling DCR (i.e., Disable DCR) is the same as Table 11 in the original paper and the datasets are also the same. The value shown the table the gap to optimal (OR-Tools).
Method
KP500
KP1,000
KP2,000
KP5,000
UDC-aaaoDissbll DCR)
0.0247%
0.0260%
0.0237%
0.0249%
UDC- DDDC#aasoDissabl DCR)
0.0083%
0.0106%
0.0105%
0.0100%
UDC-2su(Enabi) DCR)
0.0105%
0.0258%
0.0254%
0.0273%
UDC-a2so(Enable DCR)
0.0080%
0.0117%
0.0128%
0.0095%
E.6 Supplementary Ablation Study on Conquering Policies of KP
UDC exhibits flexibility in choosing constructive solver for conquering policy. For well-developed CO problems like TSP and KP, there are multiple constructive solvers available. 5.2 an ablation study the selection of these constructive solvers for TSP. In this subsection, conducted similar ablation study on KP, and the results are displayed Table [2] Both sets of results indicate that the final performance of UDC is not sensitive to the model selection for the conquering policy.
Therefore, when generalizing UDC to new CO problems, it may not be necessary to specifically choose which available constructive solver model the conquering policy.
Table 21: Ablation on the choice of constructive model as the conquering policy in KP. ICAM and POMO are two available constructive solvers for KP. The datasets are the same Table 11 in the original paper. The value shown in the table is the gap to optimal (OR-Tools))
Method
KP500
KP1,000
KP2,000
KP5,000
IDCC#55(ICAN)
0.0247%
0.0260%
0.0237%
0.0249%
UDC- (ICAM)
0.0083%
0.0106%
0.0105%
0.0100%
0.0255%
0.0252%
0.0253%
0.0242%
UICC#ass(POM))
0.0098%
0.0107%
0.0119%
0.0113%
34

---

Visualization
In this section, we provide visualization to explain our procedure and show our effectiveness directly. As shown in 7 and 9 respectively. Figures exhibit the initial solution, optimal solution, and reported solutions (i.e., (DC===(a=50), UD552, and UDC-#230(0=50)) The singular shape of initial solutions verifies that the dividing policy is mainly not to obtain a shorter predicted path, but to predict an initial solution that is easier to improve to the optimal solution by following two conquering stages. In addition, these examples also preliminarily verify that our trained UDC can handle large-scale TSP, large-scale CVRP, and large-scale OP well after several rounds of conquering.
(a) Initial solution ao and sub-TSPs G% lo (1....,0]
(b) UDC-a1 and sub-TSPs g k E (l,..., 10) (for Reunion)
(c) Optimal, Obj.= 23.4522
(d) UDC-E2, Obj = 24.1011
(c) UDC-E30, Obj. = 23.7346
(f) UDC-R150 Obj 23.7338
Figure 7: Visualization of TSP solutions on a random TSP instance, Obj. represents the objective function. The colors in subfigure (a)(b) represent sub-problems.
35

---

(a) Initial solution æo and sub-CVRPs G & [1....,0}}
(b) UDC-#; and sub-CVRPs Gh. & E {L..... 10} (for Reunion)
(c) Optimal, Gap 0%
(d) UDC-a2, Gap = 27.1%
(c) UDC-a550 Gap 7.3%
(f) UDC-a2200 Gap 5.4812%
Figure 8: Visualization of CVRP solutions on a SetX CVRPLib instance X-n1001-k43, Gap represents the gap of objective function compared to optimal. The colors in subfigure (a)(b) represent sub- problems.
36

---

Initial solution do and sub-OPs Gl, k (l.....10 10}
(b) UDC-#: and sub-OPs G2 (L...., 10) (for Reunion)
(c) Optimal, Obj. 19.4480, ((-) 3.9981
(d) UDC- 02 Obj. 113.320, ((-) = 3,9832
(e) UDC-950, Obj. 114.380, 1(-) 3.9619
UDC-a250, Obj. 116.940, 1(-) 3.9735
Figure 9: Visualization of OP solutions random OP instance, the size of nodes from sub-figure (c) to (f) represents their values P.. Obj. represents the objective function and ((-) is the length of the solution defined in Eq. (TO). The colors in subfigure (a)(b) represent sub-problems.
37

---

G Baselines & License
Classical solvers. For LKH3, We adopt the commonly used setting in NCO methods [3] and implement the LKH3 in TSP. CVRP. OVRP, and min-max mTSP based on the code from For min-max mTSP, the pa- rameter MAX_ MAX_MAAAAII CANDIDATES is set to 6, and for OVRP VEHICLE is set to 100. In mim-max For also im-
https://gá thub. thub. wow./ootterkoo///teeoooooooooooe htt.oootlltttetttonnnnoo -earriiooneee----ee teeeannttorrooe
mTSP, the implemented HGA algorithm given in httpt/pp//gggtttt..oeaaaaaaaaaaa
OR-Tools, we implement the code in htw00//tttrr/ggghoooooooooaaaaaa
kmapsack?hlzth en for KP. EA4OP
plemented as OP baseline and KaMIS mented for MIS.
imple-
SL-based sub-path solvers SL-based sub-path solvers contain the LEHD and BQ In addressing OP by BQ, we fail to get legal solutions so we use the reported gap EA4OP.
RL-based constructive solvers This paper involves AM [5T], POMO 5.. ELG [2], ICAM [6]] MDAM [52]. MatNet [4]] Omni VRP (79.. and Sym-NCO 65 baselines. Constructive solver DAN 46 DPN [42] and Eruity-Tr [62] are employed for min-max mTSP, and MatNet is specially employed for ATSP. For POMO, ELGG, Omni_ and ICAM, We the multi-start with x8 augmentation setting for CO instances with size < 1, 000 and multi-start with no augmentation for instances with N 1, 000 [1]. Specifically, the ELG aug in Table 4 adopts special setting given in its paper [80]. We adopt 200-augmentation for Sym-NCO on CO problems with size N 1, 000 and -00-amgmettaiinn on 2,000-node CO problems.
Deatmap-based We fail to implement all involved heatmap- bassd solvers (i.e., Attn-MCTS (3]] DIMES 35). DIFUSCO (3)], and T2T 66 ) so adopt the report results for comparison.
Neural divide-andd-onquer methods We implement H-TSP 20 and GLOP 13 as baselines, For
L2D, TAM, and SO, we list their reported results in comparisons. The random insertion in 17 is generated based on code in GI.OP /tttp:://
com http://twww.........oeeeeeeeeeee
Considering datasets, we use the benchmark TSPLib, CVRPLib, two SNAP graphs, and two provided test sets in DIMES httpe://ggittub..coDDDDtistt oa (MIS) and Omnn_VRPPnsstt VRP WtWPttttts///egttec
com
o httpp/u...ooo//yyaaaaaaaaaa 0mni- VRP (TSP & CVRP).
Table 22: A summary of licenses.
Resources
Тype
License
LKH3
Code
Available for academic research use
HGA
Code
Available online
KaMIS
Code
MIT License
OR-Tools
Code
Apache License, Version 2.0
LEHD
Code
Available for any non-commercial use
BQ
Code
CC BY-NC-SA 4.0 license
AM
Code
MIT License
POMO
Code
MIT License
ELG
Code
MIT License
MDAM
Code
MIT License
Sym-NCO
Code
Available online
MatNet
Code
MIT License
Omni_VR VRP
Code
MIT License
DAN
Code
MIT License
Equity-Transee Transforref
Code
Available online
H-TSP
Code
Available for academic research
GLOP
Code
MIT License
TSPLib
Dataset
Available for any non-commercial use
CVRPLib S3 55
Dataset
Available for any non-commercial use
Omni VRP
Dataset
MIT License
DIMES
Dataset
MIT License
SNAP (ego-Facebook & feather-lastfm-ssone
Dataset
Available online
The licenses for codes and datasets used in this work are listed in Table 22
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims made in the abstract and introduction accurately reflect the contributions and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the paper discusses the limitations of the work in the last section (i.e., Section Conelusion and Future Work).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer: [NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The implementation and experiment details are presented in both the main paper (Section (4) and Appendix D and we have published the code, datasets, and pre-trained models via /htpps: github.thhhccm cotccoo/////oo/o CAaom/CIAMMGOOO Sww.Ll/-Crrrp//OOoooooottteeeeee single saglleoon oejeeee_oeeeetieiD----aaee Large- Cisaale----maas
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
40

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provided the code of TSP and CVRP in the supplementary file for the first submission and now the final code can be found online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ httppp.ccppubcccguuucceee Codeeubmii ssi criionPooiccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Settings of both the testing and training are detailed in Scction Experiment Appendix B and Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The neural combinatorial optimization (NCO) methods typically only report the mean value or the gap to optimal (or best known solution) in statistics. Our method does not include randomness with all seeds 1234.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
41

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have presented in the text the details of the time required for each experi- ment (see Section 4 Appendix D). the GPU required for the experiment (Tesla V100S, see Section and other compute resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics cattps://neuripee: httffiittttppe/rrrprpp.ppppppppp
Answer: [Yes]
Justification: This paper is conducted fully in the paper conform, especially NeurIPS Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This work is about solving and optimizing CO problems, which has the opportunity to assist with real-world applications. It seems have no negative social impact.
42

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We list the licenses in Appendix G
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
43

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
The new assets introduced the paper are well documented and the documen- tation is provided alongside the assets (See Appendix G
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
44

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "elYAjXFyw0", "reviewer": "Reviewer_Eauz", "summary": "The paper introduces a Unified Neural Divide-and-Conquer (UDC) framework designed to tackle large-scale combinatorial optimization problems by leveraging a novel training methodology called Divide-Conquer-Reunion (DCR). This framework employs graph neural networks for the division of problems and utilizes established constructive solvers for conquering sub-problems, aiming to optimize the entire process. UDC has been evaluated across a range of benchmark datasets and demonstrated superior performance compared to existing neural and heuristic methods, particularly in scalability and solution quality.", "questions": "1. How does the UDC framework ensure that feasible initial solutions are generated during the division stage, particularly when traditional heuristics are not applicable?\n2. Does the UDC framework require extensive expert intervention for tuning neural network parameters and training regimens to achieve optimal performance, especially when adapting to new or unseen problem types?", "limitations": "**Constraint Handling**: UDC may not perform well on problems with intricate constraints (e.g., time windows in routing problems) that require more than just feasibility checks.\n\nThis is an interesting field, and if the authors can provide sufficiently detailed responses to the questions raised, I would be willing to consider revising my score.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Innovative Framework**: UDC integrates a novel training methodology that effectively addresses the challenge of sub-optimal divide policies, improving overall solution quality.\n2. **Extensive Applicability**: The framework demonstrates broad applicability across various large-scale combinatorial problems, confirming its versatility and effectiveness.\n3. **Strong Empirical Results**: UDC outperforms several baseline methods on a diverse set of problems, which strongly supports the utility and efficiency of the approach.", "weaknesses": "**Dependence on Specific Architectures**: The success of the method heavily relies on the choice of graph neural networks and the specific configurations of constructive solvers, which might not generalize across all types of combinatorial optimization problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the proposed UDC integrates a novel training methodology, demonstrates broad applicability across various large-scale CO problems, and outperforms several baseline methods.\n\nWe address your concerns as follows.\n\n>**Weakness 1. Dependence on specific architectures:** The success of the method heavily relies on the choice of graph neural networks and the specific configurations of constructive solvers, which might not generalize across all types of combinatorial optimization problems. \n\nThanks for your insightful comments. However, we respectfully disagree with you that the success of UDC heavily relies on the choice of graph neural networks and the specific configurations of constructive solvers. Our reasons are as follows:\n\n**Constructive solvers**: As illustrated in ``Common Concern 1`` of the general response, UDC involves 10 CO problems and it is impossible to employ the same constructive solver for all CO problems [1]. However, UDC exhibits outstanding flexibility in employing different constructive solvers as the conquering policy. Experiments mentioned in ``Common Concern 1`` show that the final performance of UDC does not rely on a specific constructive model for the conquering policy, which means that any available constructive solver with good performance can be chosen.\n\n**Graph neural networks (GNNs)**: The current UDC framework only evaluates the AGNN for the dividing policy across all 10 CO problems. However, the use of AGNN [2] in UDC is not a specific choice as well. **1)** UDC adopts GNN instead of other network structures because of its lightweight memory and time consumption and **2)** AGNN is one of the most basic forms of massage-passing neural network [3], which only calculates the bidirectional edge information and bidirectional node information within neighbors. **3)** When using AGNN to process embeddings of all 10 CO problems, UDC follows a consistent configuration.\n\n\n>**Question 1. feasible initial solution**:  How does the UDC framework ensure that feasible initial solutions are generated during the division stage, particularly when traditional heuristics are not applicable?\n\nFor involved CO problems, UDC autoregressively constructs the initial solution node-by-node based on the heatmap generated by GNN. At every step, it employs a **feasibility mask mechanism** to ensure the feasibility of the final generated solution. This mechanism is fundamental in both heatmap-based solvers [4] and constructive solvers [5]. It prevents the selection of nodes that would lead the next partial solution outside the set of all feasible solutions $\\Omega$. For example, the feasibility mask mechanism for TSP will mask the selection probabilities of all visited nodes to 0.\n\nWith the feasibility mask, the dividing policy can construct valid solutions for most CO problems. UDC cannot apply to the relatively rare CO problems where the feasibility mask mechanism cannot ensure a valid initial solution.\n\n>**Question 2. Requirement on tunning**: Does the UDC framework require extensive expert intervention for tuning neural network parameters and training regimens to achieve optimal performance, especially when adapting to new or unseen problem types?\n\nUDC does not conduct special tuning for specific CO problems. As shown in Appendix D.1, we use the same learning rate and AGNN structure across all 10 CO problems.\n\nWhen applying to a new problem type, UDC requires: \n\n**1)** Employing an available constructive solver for conquering policy (Please refer to ``Common Concern 1`` \\& ``Weakness1``). \n\n**2)** Set up new RL environments and feasibility masks based on constraints. \n\n**3)** Changing $\\alpha$ and $\\beta$ to maximize the CUDA memory usage. Note that this change is not for solving performance and will only facilitate training efficiency.\n\n\n***\n\n>**References**\n\n[1] Kwon, Yeong-Dae, et al. \"Matrix encoding networks for neural combinatorial optimization.\" Advances in Neural Information Processing Systems 34, 2021.\n\n[2] Xavier Bresson and Thomas Laurent. \"An experimental study of neural networks for variable\ngraphs.\" In ICLR 2018 Workshop, 2018.\n\n[3] Gilmer, Justin, et al. \"Message passing neural networks.\" Machine learning meets quantum physics, 2020.\n\n[4] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems 35, 2022.\n\n[5] Zhou, Changliang, et al. \"Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization.\" arXiv preprint, 2024.", "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": "", "extra_scores": {}}, {"review_id": "Nht0JmlWr7", "reviewer": "Reviewer_h7Dg", "summary": "The paper proposes a Divide-Concur-Reunion training approach for solving multiple \"large\" scale COPs.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1- Handling several problems under the same framework with possible different components per CO problem.  \n\n2- When compared to learning-based methods, in terms of testing time and solutions sizes, the proposed approach achieves competitive results. \n\n3- The Divide-Concur-Reunion training algorithm.", "weaknesses": "[Major Comments]\n\n1- Large- and small-scale instances are not properly defined. Large-scale cannot be only larger instances from previously tested relatively smaller instances by learning-based methods. Scalability is the main bottleneck in many COPs. For example, ILPs are very efficient for smaller scale instances for the MIS problem and are also efficient in larger scale sparse graphs.\n \n2- Furthermore, any learning-based CO solver (or NCO methods) must undergo generalization testing/analysis for every problem. While proposing a method to solve many CO problems is the main goal of the paper, investigating the generalization can differ significantly for each COP. This leads to improved understanding of the limitations/capabilities of the proposed framework. For TSP, the weights and size of the graph are the two parameters to consider. However, for MIS, there are additional parameters such as the graph density and degree distribution. The authors only consider ER700 with p=0.15 (probability of edge creation per node).\n\n3- The proposed solver should tackle what heuristics and exact solvers cannot handle. Comparing run-time results with heuristics is not valid as learning-based methods require datasets and training time (which is ~10 days for the proposed method). For example, LKH3 results of Table 8 indicate that this heuristic requires only 6 seconds (unclear if it is average of total time) to solve 16 instances of OVRP2000 (which is considered large-scale by the authors) whereas the proposed approach takes 20 minutes, excluding the training time. \n\n4- The availability of datasets is a challenging problem. For example, if at testing time, a real-world graph from the SNAP dataset (https://snap.stanford.edu/data/) is presented to UDC. How is it handled? The SNAP graphs do not follow a generative function in NetworkX which means training instances are not available. A discussion is needed here. \n\n5- No details about graph sparsification or why it is needed. In Section 3.1, it is briefly described for TSP and MIS. How about other problems? The paper considers 10 problems. Furthermore, if the edges of the original graph in MIS are maintained, how is that graph sparsification? \n\n6- In the second paragraph of Section 3.1, the write-up covers VRP and TSP, but no discussion is given of the other problems. \n\n7- For the previous two points, Appendix B covers some of the details, but not all. For example, how is the sub-problem preparation done for the MIS? \n\n8- In line 150, if the dividing and conquering stages can be defined as MDP, can you define the MDP explicitly? For example, what are the States set, Transition function, and Reward function?\n\n9- What is “i” in \\Omega_i in (5)? If it is from the set defined in line 132, shouldn't it be k? \n\n10- What is the objective function(s) for training the DCR? Since training is the main contribution of the paper, this needs to be explained properly. Saying that \"we use the REINFORCE algorithm\" is not clear! Algorithm 1 outlines the procedure but does not explain this point. I think the training Algorithm should be placed in the main body of the paper while the gradients in (6) should be placed in the Appendix. \n\n11- What is the functions Rank and Top-k in line 190? Citation(s) or brief description is needed. \n\n12- How are the constraints in Appendix B being handled? \n\n13- Generally, there are many unclear descriptions of the proposed methodology. Even if the proposed approach consists of many components, they need to be properly described and defined. Examples include points 5, 6, 7, 8, 10, 11, and 12. \n\n14- The last three rows of the sub tables in Table 7 (Appendix D) indicate that the proposed approach is not fully unified across different COPs. They do not only suggest that different components are being enabled or disabled for every COP, but also the use of different strategies/architectures of obtaining the policies. For example, the DCR (which is the main contribution of the paper) in the KP problem is disabled. \n\n[Minor]\n\nThere are many writing issues and typos in the paper. Few examples are: \n\n1- \"exp\" in (3) and (4) are denoted using different fonts. \n\n2- Subscripts of \\script H is not defined in (4). \n\n3- The title of Section 3.3 can be \"Applicability in General CO Problems\". \n\n4- \"Experiments\" in line 199. \n\n5- \"Definitions\" in line 539.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the proposed UDC achieves competitive results and can handle several problems under the same framework with possible different components per CO problem.\n\nWe sincerely appreciate the effort you have put into reviewing this article and we address your concerns as follows.\n>**Weakness 1. Definition of ``large-scale``.**\n\nWe agree that the definition of large-scale cannot only consider the size of instances. As the definition in [1], the large-scale CO problem has more data or decision variables or constraints (large-size sparse graphs might have relatively more decision variables, data, and fewer constraints). We will provide a clearer definition of large-scale CO problems.\n>**Weakness 2 & 4. Generalization.**\n\nWe deeply agree that the generalization performance on instances with different parameters is essential to test NCO methods. However, we have to declare that for some CO problems, there are no established datasets to evaluate the generalization. When generalizing the model trained on the ER graph with p=0.15 to the ``Social circles: Facebook`` graph in the SNAP dataset, we find UDC can also output legal solutions with seemingly good objective values but there is no ground truth of MIS on the graph so we cannot check the ability of UDC on it. \n\nWe evaluate the generalization performance of UDC on established out-of-domain datasets, e.g., vehicle routing problem (VRP) instances with coordinates sampled from non-uniform distributions. As exhibited in Table 13 in Appendix D.3, the generalization ability of UDC on TSP and CVRP can surpass existing neural solvers. Such advantage may be attributed to the normalization process in the conquering stage.\n>**Weakness 3. Solving time.**\n\nFirstly, we apologize for the typo in the time results of OVRP and we will revise it to the content shown in ``Table 3 of the one-page PDF``, where LKH3 takes 16 minutes for the OVRP500 dataset, 32 minutes for OVRP1,000, and 27 minutes for OVRP2,000. \n\nWe agree that neural methods should tackle what heuristics and exact solvers cannot handle, especially when heuristics has only low performance or requires an unacceptable time to generate solutions. In certain CO problems, UDC can compensate for the above two situations. Considering **performances**, UDC can produce better results than all available existing heuristics in (S)PCTSP and min-max mTSP. For **solving time**, we acknowledge that NCO methods require additional training time, which is time-consuming. However, well-trained models, such as UDC for large-scale OP and TSP, can generate good solutions within several seconds. Compared to heuristics, the online solving characteristic of UDC may be valuable for practical applications that require response speed.\n>**Weakness 5-7, 13. Pipeline settings.**\n\nThanks for your comments. We will improve the expression in Section 3 and Appendix B based on your suggestions to eliminate ambiguity, and we will also publish all the code after the paper is published to show the detailed implementation.\n\nFor weakness 5, in non-graph input CO problems, especially VRPs, constructing sparse graphs aims at deleting more useless edges to reduce the time complexity. It is a general step for existing heatmap-based solvers.  By processing only sparse graphs, each layer of GNNs can achieve a time complexity of O ($KN$) ($K$ is the neighbor size, usually 100 in UDC), which is helpful to large-scale VRPs. In addition, this procedure is to construct sparse graphs for instances rather than ``graph sparsification``. For MIS, the ER graph with p=0.15 is a sparse graph itself so there are no additional steps needed for constructing sparse graphs. For weakness 7, Sub-MIS is generated with random nodes from the original MIS.\n\n>**Weakness 8 & 10. MDP & training.**\n\nPlease refer to ``Common Concern 2`` for the MDP definition & objective functions.\n\n>**Weakness 11: Line 190.**\n\nOnly CO problems with decomposable aggregate functions [2] can be solved by the divide-and-conquer method. So UDC can not apply to CO problems with indecomposable aggregate functions such as minimizing the visiting rank of given nodes or the top-k longest route in a graph.\n\n>**Weakness 12. Constraint handling.**\n\nFeasibility masks will mask the illegal action in generating both initial solutions and sub-solutions (You can also refer to ``Question 1 of reviewer Eauz`` for details).\n\n\n>**Weakness 14. Unified configuration.**\n\nWe need to declare that 'unified' in this article means that UDC adopts a unified training framework for the diving and conquering stages. For the 10 CO problems involved, there is no unified conquering policy that can solve all problems (Please refer to ``Common Concern 1``) so UDC adopts different conquering policies for different CO problems.\n\n**The third to last** and **the second to last** rows of Table 7 are related to the environment or constraint of different CO problems. For KP, the sub-optimal connection shown in Figure 2 in the original paper will not occur, so there is no optimality difference in whether DCR is enabled. We provide the KP results with DCR enabled in ``Table 2 of the one-page PDF`` and these results support the above conclusion. \n\nThe two-side conquering baseline may not be applicable in certain CO problems like ATSP and CVRP where reversing the sub-solution will be illegal, so we disable such baseline in these problems. We will add an explanation to summarize all the settings in Table 7.\n\n>**Minor Weakness & Weakness 9. Typos.**\n\nYes, the $\\Omega_i$ should be $\\Omega_k$. Thanks for pointing typos out, we will fix all of them accordingly.\n\n***\n>**References**\n\n[1] Gervet, Carmen. \"Large scale combinatorial optimization: A methodological viewpoint.\" DIMACS series, 2001.\n\n[2] Jesus, Paulo, Carlos Baquero, and Paulo Sérgio Almeida. \"A survey of distributed data aggregation algorithms.\" IEEE Communications Surveys & Tutorials, 2014", "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": "", "extra_scores": {}}, {"review_id": "2OWgiHuwM4", "reviewer": "Reviewer_kAJo", "summary": "The paper introduces a novel Unified Neural Divide-and-Conquer (UDC) framework designed to address large-scale CO problems. The UDC framework leverages a Divide-Conquer-Reunion (DCR) training method that uses GNN for global instance division and a constructive neural solver for sub-problem solutions. This unified approach aims to improve both efficiency and applicability across various CO problems by combining the training process of the dividing stage and the conquering stage.", "questions": "See weakness", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The DCR method proposes a view of unifying the training of dividing and conquering stages for solving large-scale CO problems.\n2. The UDC framework is designed with applicability to a wider range of CO problems, without heavy reliance on problem-specific heuristics like in the previous works.\n3. The idea of considering interdependencies between dividing and conquering stages is interesting as a neural CO training scheme.\n4. The authors conduct extensive experiments where the proposed framework's performance is shown to be generally good on certain problems.", "weaknesses": "1. The novelty of the proposed framework requires further explanation. The current UDC/DCR seems to be a combination of existing techniques in either dividing or conquering stages. From a local perspective, 1) the sub-problem dividing policy is simply a conventional continuous node split based on the initial solution, 2) the conquering phase is a direct exploitation of existing problem-specific models like POMO, ICAM, MatNet, etc., to tackle the small scaled sub-problem, and 3) the technique in the reunion part resembles prevalent tricks in the neural CO literature, such as POMO/random-start/multi-sampling/random augmentation, etc. Therefore, the proposed unified framework is more of a mathematical or conceptual summarization of the current RL-based divide-and-conquer pipeline rather than a novel methodology for tackling various CO problems using a unified architecture. \n2. The training procedure is not stated clearly enough. As two different networks are adopted in either phase, how are the gradients in equation (6) updated simultaneously during an instantiated epoch? If the initial solution is generated using a heatmap and some decoding scheme while the sub-solutions are computed auto-regressively with another model, how the REINFORCE algorithms are implemented necessitates further presentation in order to address obscurity regarding implementation details.\n3. The solving time of UDC is relatively longer than several compared neural methods which is questionable of its efficiency and practiability. Further notably is the rapidly increased time consumed with the raising number of stages it takes in conquering, to which, on the other hand, the solving quality actually highly relates. Thus, further experiments shall be necessary to explicitly illustrate the relationship among solving quality, the number of conquering stages and solving time. \n4. Will it benefit from using supervised learning over current RL method for sub-problem conquering? Note that SL-based approaches achieve better performance in problems like TSP in previous problem-specific research.\n5. Can the framework generalize to a wider range of CO problems? Ten problems as the authors evaluated in this paper, most of them have a similar setting or formulation to routing tasks like TSP, VRP or their variants. \n6. Experiments on different initial solutions are missing. To what extent are the effectiveness of the UDC framework rely on the quality of the initial solution generated during the dividing stage? Note the fact that a poor initial solution may lead to sub-optimal conquering solutions (as mentioned in Appendix D.4), more empirical studies or ablation should be conducted regarding the ways and quality of initial solution generation.\n7. Unsatisfactory readability and inelegant comparison. A great many experiments are conducted, yet tables demonstrating results in this paper are somewhat dispersed in pieces and hard to follow. Different problems/scales/settings own different compared components/methods and reporting manners. A  unified format with as many commonly comparable and explicitly categorized methods is supposed better-organized. Names like AM-bs1024 require explanation. Introduction or classification of methods like SO-mixed is missing. The meaning of the asterisk mark is unclear until Appendix D. Minor points. E.g., in line 167, the second $x_{1,0}$ is likely to be $x_1$? Furthermore, results of T2T are not reported.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the proposed UDC framework is designed with applicability to a wider range of CO problems, and its performance is shown to be generally good on certain problems.\n>**Weakness 1. Novelty of UDC.**\n\nThanks for your insightful comments. Neural-divide-and-conquer methods are indeed a combination of existing methods in terms of network structure and solving process. However, we would like to declare that the significant novelty of UDC lies in its **training approach**.\n\nConsidering the **training approach**, we do not agree that the technique in the Reunion step resembles prevalent tricks in the neural CO literature. The training methods you mentioned (i.e., POMO/Sym-NCO, etc.) are all for obtaining the RL baseline for single-stage constructive solvers [1]. However, the DCR training method proposed in this article is designed to handle the negative impact of sub-optimal dividing results in neural divide-and-conquer methods (as shown in Table 1 in the original manuscript), which is novel in NCO methods.\n\nAs demonstrated in the paper, the DCR training method can significantly facilitate the applicability and effectiveness of UDC. \n>**Weakness 2. Training process.**\n\nThanks for your suggestion. UDC employs a neural network for the dividing policy and another network for the conquering policy. In a Divide-Conquer-Reunion (DCR) enabled training process, the model for conquering policy will successively update its parameters twice according to the loss $\\mathcal{L} _ {c1}(\\mathcal{G})$ and $\\mathcal{L} _ {c2}(\\mathcal{G})$ after the Conquer step and the Reunion step, respectively. Finally, we will calculate the dividing loss function $\\mathcal{L} _ {d}(\\mathcal{G})$ based on the solution $\\boldsymbol{x}_ 2$ and the dividing policy will update the model parameters according to the dividing loss.\n\nA pseudo-code of the training process is provided in Algorithm 1 in Appendix C.6. Please refer to ``Common Concern 2`` for MDP \\& Training objectives and we will provide more implementation details to increase the clarity of illustrations.\n>**Weakness 3. Solving time.**\n\nThanks for your constructive comments. For a better discussion, we respond to the two concerns in Weakness 3 in reverse order.\n\n**The number of conquering stages**: Both the solving time and solution quality of UDC are related to the number of initial solutions $\\alpha$ and the number of conquering stages $r$. Therefore, we conduct ablation experiments on the two factors in Appendix E.1 and Appendix E.2, respectively, in the original paper. Changing the $r$ value to adjust solving times, the results in ``Figure 5 of the original paper`` demonstrate that UDC has an efficiency advantage, as its variants generally need less time for better performance compared to the SOTA neural divide-and-conquer methods GLOP and SL-based sub-path solver LEHD. \n\n**Solving time of UDC**: Based on the results above, together with Table 3 and Table 17 of the original manuscript, when generating solutions with $\\alpha$=1, UDC can generate acceptable solutions with a significant advantage in solving speed.\n\nAdditionally, we are sorry for an index mistake in line 816 where ``Figure 6`` should be ``Figure 5``.\n>**Weakness 4. Supervised learning.**\n\nAlthough SL-based approaches achieve better performance in some CO problems like TSP and CVRP, we believe that the SL method is not suitable for sub-problem conquering for **Poor applicability**: using SL for sub-problem conquering requires a large number of high-quality heuristic algorithm solutions as training labels. However, in most CO problems, heuristic algorithms are not outstanding (e.g., PCTSP) or are too time-consuming (e.g., min-max mTSP). Therefore, SL-based sub-problem conquering will compromise the availability of UDC for these CO problems.\n>**Weakness 5. Applicability.**\n\nYes, according to the discussion in Section 3.3, UDC can handle combinatorial optimization problems that meet the conditions.\n\nThis paper chooses the 10 CO problems to evaluate UDC, mainly because they have **established datasets, baseline methods, and constructive solvers**. When a new CO problem has developed established datasets, baseline methods, and constructive solvers, it can also be incorporated to evaluate the proposed UDC framework.\n>**Weakness 6. Initial solution.**\n\nThanks for your valuable suggestion. We further conduct experiments on TSP with different initial solutions, and the results are shown in ``Table 4 of the one-page PDF``. Results demonstrate the contribution of a good initial solution to the final solution. The variants with a random or nearest greedy initial solution cannot converge to good objective values even with 50 UDC conquering stages. Moreover, from TSP500 to TSP2,000, the dividing policy of UDC produces similar results to the heuristic algorithm random insertion, which verifies the quality of the dividing policy.\n>**Weakness 7. Readability.**\n\nThank you for your suggestion. We will unify the reporting methods, add footnotes, clarify all method names and references, and provide more instructions for appendices accordingly to improve readability. In Table 2 in the original manuscript, we will supplement the reported results of T2T [4].\n\n***\n>**References**\n\n[1] Berto, Federico, et al. \"Rl4co: an extensive reinforcement learning for combinatorial optimization benchmark.\" arXiv preprint, 2023.\n\n[2] Drakulic, Darko, et al. \"Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization.\" Advances in Neural Information Processing Systems 36, 2024.\n\n[3] Bertazzi, L. et al. Min–max vs. min–sum vehicle routing: A worst-case analysis. European Journal of Operational Research, 2015.\n\n[4] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.", "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": "", "extra_scores": {}}, {"review_id": "e2skXLt3aS", "reviewer": "Reviewer_Uqww", "summary": "UDC focuses on the divide-and-conquer-based NCO methods, proposing a novel framework that does not require heuristics and adopting an efficient training approach DCR. Compared to existing methods, UDC has significant improvements in effectiveness and applicability.", "questions": "1. UDC shows wide applicability compared to existing NCO methods. What is the reason for its significant advantage in applicability compared to existing divide-and-conquer methods?\n2. The solution representation in the upper part of Figure 2 is not clear enough, please add illustrations in the Figure caption.\n3. On TSPLib and CVRPLib, UDC seems to perform less prominently. Please provide the result of UDC on benchmark instances of other CO problems.\n4. Please add more clear indexes in the main part for contents in the Appendix.\n5. Should GLOP for TSPLib in Table 4 be GLOP more revision?\n6. Do BS and bs in Table 3 represent beam search? Please provide a detailed introduction.", "limitations": "Chapter 3.3 discusses the unavailability of UDC on certain CO problems, such as TSPTW. This should also be included in discussing the limitation.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This paper conducts extensive experiments. UDC exhibits effectiveness in 10 different CO problems, improving the existing divide-and-conquer methods in both effectiveness and applicability.\n2. This paper validates the importance of unified training. The idea of DCR is quite novel.\n3. The article is easy to follow and experiments give detailed explanations on the setting reason for hyperparameters and components.", "weaknesses": "There are no major weaknesses in the article, my questions are presented in the Question section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the idea of DCR quite novel, UDC exhibits effectiveness in 10 different CO problems, the article is easy to follow, and experiments give detailed explanations on the setting reason for hyperparameters and components. \n\nWe address your concerns point-by-point as follows:\n\n\n>**Question 1. Reason for applicability**: UDC shows wide applicability compared to existing NCO methods. What is the reason for its significant advantage in applicability compared to existing divide-and-conquer methods?\n\n\nThe wide application of UDC on large-scale CO problems mainly depends on two reasons as follows: **1)** UDC gets rid of the heuristic components in both the dividing policy and the conquering policy (as shown in Table 1 in the original paper). Heuristic components often require expert knowledge to redesign when handling unseen instances and new CO problems, thus undermining the applicability of methods. **2)** The efficient training method DCR enables a unified training framework for all CO problems. The unified training framework does not rely on the design of separate pre-training procedures or tunings for specific CO problems, making UDC easy to apply to new CO problems.\n\n\n>**Question 3. Benchmark experiments**: Please provide the result of UDC on benchmark instances of other CO problems.\n\nThank you for your suggestion. We further evaluate the proposed UDC on the benchmark dataset of min-max mTSP. The benchmark dataset of min-max mTSP contains instances from 500 to 1,000 nodes. It includes the u574 instance, the p654 instance, and the rat783 instance (selected by the paper of Equity-Transformer [1] and we use the reported results from [1]). Objective values of methods are shown in the table below. Compared to Equity-Transformer and the heuristic method LKH-3 and OR-Tools, UDC-$\\boldsymbol{x}_{50}$ ($\\alpha=50$) can significantly lead.\n\n| Instance  | $M$= | LKH-3 | OR-Tools | Equity-Transformer | UDC-$\\boldsymbol{x}_{50}$ ($\\alpha=50$) |\n|-----------|------|-------|----------|---------------------|-----------------------------------------|\n|    | 30   | 8800  | 19391    | 6642                | 6641                                    |\n| u574      | 40   | 8051  | 15924    | 6642                | 6641                                    |\n|    | 50   | 7733  | 14192    | 6642                | 6641                                    |\n|    | 30   | 13317 | 25552    | 12795               | 12380                                   |\n|   p654      | 40   | 13668 | 25547    | 12795               | 12303                                   |\n|     | 50   | 13188 | 25547    | 12795               | 12270                                   |\n|   | 30   | 2217  | 5105     | 1272                | 1243                                    |\n| rat783    | 40   | 1872  | 5105     | 1272                | 1232                                    |\n|    | 50   | 1640  | 4005     | 1272                | 1232                                    |\n\n\n>**Question 2,4. Writing clarity.**\n\nThanks for your valuable suggestion. The upper part of Figure 2 shows the pipeline of the training method DCR. In the DCR-enabled training process, there are two conquering stages, the Conquer step and the Reunion step, where the Reunion step is introduced to eliminate the negative impact of the sub-optimal dividing policy. The lower part provides a local view of a solution fragment to demonstrate our motivation. DCR has the potential to correct wrong dividing results by generating the solution of the connection part in the Reunion step.\n\nWe will include this illustration in the caption of Figure 2, use more appropriate colors for better expression, and add more indexes in the main part for contents in the Appendix of the original manuscript.\n\n>**Question 5,6. Abbreviation in Tables.**\n\nThank you for your comments. Yes, in Table 4 in the original paper, the GLOP for TSP should be GLOP more revision instead of GLOP-LKH3. We will change the index in Table 4 to GLOP and provide an additional description of the settings.\n\nYes, both BS and bs in Table 3 of the original manuscript represent the beam search. Beam search is a commonly used decoding strategy in autoregressive sequence model decoding, which is a form of breadth-first search (BFS) [2]. Attention Model [3] first introduces the technique into the field of NCO. For a beam limited to k (noted as bs$k$ in Table 3 of the original manuscript, e.g., bs1024 or bs16), the beam search will construct k solutions with top probabilities sampled from the model policy. Models with beam search in decoding can get better results with more solving time.\n\n\n>**Limitation**: Chapter 3.3 discusses the unavailability of UDC on certain CO problems, such as TSPTW. This should also be included in discussing the limitation. \n\nThank you for pointing this out, we will include the content discussed in Chapter 3.3 in the illustration on limitations.\n\n***\n\n>**References**\n\n[1] Son, Jiwoo, et al. \"Equity-Transformer: Solving NP-Hard Min-Max Routing Problems as Sequential Generation with Equity Context.\" AAAI 2024, 2024.\n\n[2] Meister, Clara, Tim Vieira, and Ryan Cotterell. \"If beam search is the answer, what was the question?.\" arXiv preprint, 2020.\n\n[2] Kool, Wouter, Herke Van Hoof, and Max Welling. \"Attention, learn to solve routing problems!.\" arXiv preprint, 2018.", "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": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all reviewers for their constructive comments and valuable suggestions. These suggestions greatly help us to improve our manuscript. The current manuscript has received extensive positive evaluations regarding its novelty, effectiveness, applicability, and impact:
* **Reviewer Eauz**: UDC integrates a novel training methodology that effectively addresses the challenge of sub-optimal divide policies. It demonstrates broad applicability across various large-scale combinatorial problems. UDC outperforms several baseline methods on a diverse set of problems, which strongly supports the utility and efficiency of the approach.
* **Reviewer h7Dg**: When compared to learning-based methods, in terms of testing time and solution sizes, the proposed UDC achieves competitive results.
* **Reviewer kAJo**: The UDC framework is designed with applicability to a wider range of CO problems, without heavy reliance on problem-specific heuristics like in the previous works. The authors conduct extensive experiments where the proposed framework's performance is shown to be generally good on certain problems.
* **Reviewer Uqww**: This paper conducts extensive experiments. UDC exhibits effectiveness in 10 different CO problems, improving the existing divide-and-conquer methods in both effectiveness and applicability. The idea of DCR is quite novel and experiments give detailed explanations to the setting reason for hyperparameters and components.

***

We address some common concerns shared by different reviewers in this response.
 
>**Common Concern 1**: Explanation of choosing different constructive solvers (i.e., models for conquering policy) for different CO problems. (Reviewer Eauz, Reviewer h7Dg)

Using the same model for conquering policy is an ideal choice. However, the experiment of UDC involves 10 CO problems, and some CO problems, like min-max mTSP [1] and ATSP [2], require specific model structures to process their inputs and constraints. Consequently, there is no constructive solver that can be used for all 10 involved CO problems. For each CO problem, UDC adopts the best-performance constructive solver for the conquering policy (i.e., summarized in Appendix Table 7).

UDC exhibits flexibility in choosing the constructive solver for the conquering policy. For well-developed CO problems like TSP and KP, there are multiple constructive solvers available. Table 5 in the original paper presents an ablation study on the selection of these constructive solvers for TSP. In rebuttal, we conduct a similar ablation study on KP, and the results are displayed in ``Table 1 of the appendix one-page PDF``. Both sets of results indicate that the final performance of UDC does not rely on a specific constructive model for the conquering policy.

***

>**Common Concern 2**: Presentation of training objective and their Markov Decision Process (MDP) (Reviewer h7Dg, Reviewer kAJo)


In addition to Algorithm 1 in Appendix C.6, we will include descriptions of the training objective of both policies and the MDP for the two stages.

**Objective functions of optimizing the two networks**: For a CO problem (or a sub-CO problem) with an objective function $f(\cdot)$, the objective of optimizing both networks is to maximize the reward functions of their corresponding MDP. The reward is $-f(\boldsymbol{x}_2)$ for the GNN, $-f(\boldsymbol{s}^1)$ for the constructive solver in the Conquer step (i.e., the first conquering stages), and $-f(\boldsymbol{s}^2)$ in the Reunion step.


**MDP for the dividing stage**: The MDP $\mathcal{M}_d=${$\mathcal{S}_d,\mathcal{A}_d,\boldsymbol{r}_d,\mathcal{P}_d$} of the dividing stage can be represented as follows: 

* State. The state ${st} _ d \in \mathcal{S} _ d $ represents the current partial solution. The state in the $t$-th time step is the current partial solution with $t$ nodes ${st} _ {d,t}=\boldsymbol{x} _ {0,t}=(x_{1},x_2,\ldots,x_t)$. $st_{d,0}$ is empty, $st_{d,T}=\boldsymbol{x}_0$. 

* Action \& Transaction. The action is to select a node at time step $t$, i.e., $a_{d,t}=x_{t+1}$. The chosen node needs to ensure that the partial solution ${st} _ {d,t+1}=(x _ 1,\ldots,x _ t,x _ {t+1}) $ is valid (i.e., $st _ {d, T}\in \Omega$). 

* Reward. Every single time step has the same reward $r_{d,t}=-f(\boldsymbol{x}_2)$, which is the negative objective function value of the final solution $\boldsymbol{x}_2$ after the whole DCR process. 

* Policy. The policy $\pi_d$ is shown in Eq. (4) of the original paper.

**MDP for the conquering stage**: The MDP $\mathcal{M}_c=${$\mathcal{S}_c,\mathcal{A}_c,\boldsymbol{r}_c,\mathcal{P}_c$} of any single conquering stage is represented similarly as follows: 

* State. Each state ${st} _ c\in \mathcal{S} _ c$ represents a partial solution of sub-CO problems. The state in the $t$-th time step is the current partial (sub-)solution with $t$ nodes ${st} _ {c,t}=\boldsymbol{s} _ {t}=(s_{1},s_2,...,s_t)$. $st_{c,0}$ is empty and $st_{c,T}=\boldsymbol{s}$. 

* Action \& Transaction. The action is to select a node at time step $t$ as well, i.e., $a_{c,t}=s_{t+1}$. 

* Reward. The reward in each time step becomes the objective value of sub-CO solution $\boldsymbol{s}$, i.e., $r_{c,t}=-f(\boldsymbol{s})$.

* Policy. The policy $\pi_c$ is shown in Eq. (5) of the original paper.


***


Point-to-point responses can be found below. We are also glad to continually improve our work to address any further concerns.

Best Regards,

Paper12083 Authors

***

>**Reference**


[1] Son, Jiwoo, et al. "Equity-Transformer: Solving NP-Hard Min-Max Routing Problems as Sequential Generation with Equity Context." AAAI 2024, 2024.

[2] Kwon, Yeong-Dae, et al. "Matrix encoding networks for neural combinatorial optimization." NeurIPS 2021, 2021.

Meta-review: After extensive discussion, all reviewers concur that this interesting paper, which advances the size and generality of the combinatorial optimization problems that can be solved with a deep-learning approach, should be accepted.
Decision: Accept (poster)