UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems

Authors: zhi  zheng
changliang  zhou
xialiang  tong
mingxuan  yuan
zhenkun  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:48:19

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

Main paper: 
 introduction: 
 Combinatorial optimization (CO) [1] has numerous practical applications including route planning [2] , 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 [5, 6] can generate near-optimal solutions for small-scale instances (e.g., TSP instances with no more than 200 nodes) without the requirement of expert knowledge [7] . These solvers usually adopt a 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 of training on larger-size instances directly [8, 9, 10] , these methods exhibit limited performance when generalizing to solve large-scale CO problems.Table 1 : Comparison between our UDC and the other existing neural divide-and-conquer methods. The proposed UDC utilizes learning-based 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. [24] TSP,CVRP ✓ ✓ × × L2D [22] CVRP ✓ × × × H-TSP [20] TSP ✓ ✓ × × RBG [23] CVRP & CVRP variants ✓ ✓ × × TAM [12] CVRP ✓ ✓ × × SO [21] TSP × ✓ × × GLOP [13] (A)TSP, CVRP, PCTSP× 1 ✓ × × 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, 13] . BQ-NCO [14] and LEHD [8] develop a 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 [6] , ICAM [16] , and DAR [17] integrate auxiliary information to guide the learning of RL-based single-stage constructive solvers [5] . However, the auxiliary information needs problem-specific designs, and the O(N 2 ) complexity caused by the self-attention mechanism also poses challenges for large-scale (N -node) problems. As another category of large-scale NCO, neural divide-and-conquer methods have attracted increasing attention. Inspired by the common divide-and-conquer idea in traditional heuristics [18, 19] , these methods execute a two-stage solving process, including a 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 [13] have demonstrated superior efficiency in large-scale TSP and CVRP.Despite acknowledging the prospect, these neural divide-and-conquer approaches still suffer from shortcomings in applicability and solution quality. Some neural divide-and-conquer methods rely on problem-specific heuristics in either dividing (e.g., GLOP [13] and SO [21] ) or conquering stages (e.g., L2D [22] and RBG [23] ), which limits their generalizability across various CO problems. Moreover, all the existing neural divide-and-conquer methods adopt a separate training process, training the dividing policy after a pre-trained conquering policy [13, 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 a training scheme might guide the dividing policy to adapt the pre-trained sub-optimal conquering policy, thus converging to local optima.As shown in Table 1 , this paper finds that considering the negative impact of sub-optimal dividing results is essential in generating high-quality divide-and-conquer-based solutions. To this aim, we propose a novel RL-based training method termed Divide-Conquer-Reunion (DCR). Enabling the DCR in a unified training scheme, we propose the unified neural divide-and-conquer framework (UDC) for a 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.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.2 Preliminaries: Neural Divide-and-ConquerQuestion: 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 in 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 as long as it is clear that these goals are not attained by the paper. 
divide-and-conquer: 
 A CO problem with N decision variables is defined to minimize the objective function f of a solution x = (x 1 , x 2 , . . . , x N ) as follows: minimizeEQUATIONwhere G represents the CO instance and Ω is a set consisting of all feasible solutions.Leveraging the divide-and-conquer idea in solving CO problems is promising in traditional (meta)heuristic algorithms [25] , especially large-neighborhood-search-based algorithms [26, 27] . These methods achieve gradual performance improvement from an initial solution through iterative sub-problem selection (i.e., the dividing stage) and sub-problem repair (i.e., the conquering stage).Recent neural divide-and-conquer methods conduct a similar solving process and employ efficient deep-learning techniques to model the policies of both stages [13] . The dividing policy π d (G) decomposes the instance G to K mutually unaffected sub-problems {G 1 , G 2 , . . . , G K } and the conquering policy π c generates sub-solutions s k for k ∈ {1, . . . , K} by s k ∼ π c (G k ) to minimize the objective function f ′ (s k , G k ) of corresponding sub-problems. Finally, a total solution x of G is merged as x = Concat(s 1 , . . . , s K ).The (single-stage) constructive NCO solvers are promising in solving general small-scale CO problems with time efficiency. These constructive solvers typically employ an attention-based encoderdecoder network structure, where a multi-layer encoder processes CO instances into embeddings in hidden spaces and a lightweight decoder handles dynamic constraints while constructing feasible 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 a τ -length solution x = (x 1 , . . . , x τ ) as follows:EQUATIONwhere x 1:t-1 represents the partial solution before the selection of x t . DRL-based constructive NCO solvers demonstrate outstanding solution qualities in small-scale CO problems. So existing neural divide-and-conquer methods [13, 21] also generally employ a pre-trained constructive neural solver (e.g., Attention Model [28] ) for their conquering policy π c .Advanced constructive NCO solvers rely on the self-attention layers [29] for node representation, whose quadratic time and space complexity related to problem scales [30] hinders the direct training on large-scale instances. So, heatmap-based solvers [31, 32] are proposed to solve large-scale CO problems efficiently by a lighter-weight GNN [33] . In heatmap-based solvers for vehicle routing problems (VRPs), a GNN with parameter ϕ first generates a heatmap H ∈ R N ×N within linear time [34] and a feasible solution is then constructed based on this heatmap with the policy [35] as follows:π(x|G, Ω, θ) = p θ (H|G, Ω)p(x 1 )EQUATIONHowever, the non-autoregressively generated heatmap [36] excludes the information about the order of the constructed partial solution x 1:t-1 , so the greedy decoding policy in heatmap-based solvers becomes low-quality and these solvers rely on search algorithms [37, 38] for higher-quality solutions.3 Methodology: Unified Divide-and-ConquerAs shown in Figure 1 , UDC follows the general framework of neural divide-and-conquer methods [13] , solving CO problems through two distinct stages: the dividing stage and the conquering stage. The dividing stage of UDC is expected to generate a feasible initial solution with a similar overall shape compared to the optimal solution, so the subsequent conquering stage can obtain more high-quality solutions by solving local sub-problems. For all the involved CO problems, UDC first constructs a sparse graph to represent the instance and then employs a heatmap-based 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 as the conquering policy to generate sub-solutions. There is no single universal constructive neural solver that can handle all types of CO problems [41, 42] , so we employ suitable solvers for each sub-CO-problem (e.g., AGNN [39] for MIS, POMO [5] or ICAM [16] for VRPs).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 6 Conclusion and Future Work).Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
pipeline: dividing stage & conquering stage: 
 Dividing Stage: Heatmap-based Neural Dividing: Heatmap-based solvers require less time and space consumption compared to constructive solvers, so they are more suitable for learning global dividing policies on large-scale instances. The dividing stage first constructs a sparse graph G D = {V, E} (i.e., linking K-nearest neighbors (KNN) in TSP, or 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 H ∈ R N ×N and a τ -length initial solutions x 0 = (x 0,1 , . . . , x 0,τ ) is generated based on the policy π d as follows:EQUATIONConquering Stage: Sub-problem Preparation: The conquering stage first generates pending subproblems along with their specific constraints. For VRPs, the nodes in sub-VRPs and the constraints of sub-VRPs are built based on continuous sub-sequences in the initial solution x 0 . In generating n-node sub-problems, UDC divides the original N -node instance G into ⌊ N n ⌋ sub-problems {G 1 , . . . , G ⌊ N n ⌋ } according to x 0 , temporarily excluding sub-problems with fewer than n nodes. The constraints {Ω 1 , . . . , Ω ⌊ N n ⌋ } of sub-problems include not only the problem-specific constraints (e.g., no selfloop in sub-TSPs) but also additional constraints to ensure the legality of the merged solution after integrating the sub-problem solution to the original solution (e.g., maintaining the first and last node in sub-VRPs). Similar to previous works [13, 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 {G 1 , . . . , G ⌊ N n ⌋ }. We utilize constructive solvers with parameter θ for most involved sub-CO problems. Their sub-solution s k = (s k,1 , . . . , s k,n ), k ∈ {1, . . . , ⌊ N n ⌋} are sampled from the conquering policy π c as follows:EQUATIONwhere s k,1:t-1 represents the partial solution before the selection of s k,t . Finally, as the last step in a conquering stage, sub-solutions with improvements on the objective function will replace the original solution fragment in x 0 and the merged solution becomes x 1 . It's worth noting that the conquering stage can execute repeatedly on the new merged solution for a gradually better solution quality and we note the solution after r conquering stages as x r .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 is 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 a conquering policy on specific datasets before training the dividing policy [13] . However, this separate training process not only requires additional problem-specific dataset designs [13] but also undermines the collaborative optimization of the dividing and conquering policies (further discussed in Section 5.1).In this paper, we imply that considering the negative impact of sub-optimal sub-problems decomposition 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 solution so as shown in Figure 2 , despite obtaining high-quality sub-solutions, there may be error connections emerging at 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 Divide-Conquer-Reunion (DCR) process to eliminate the impact as 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 x 1 with new sub-problem decompositions. The Reunion step can be formulated as rolling the original start point x 1,0 along the solution x 1,0 by l times (i.e., to x 1,l ) and conquering again. To ensure equal focus on the adjacent two sub-problems, we set l = n 2 in training all the DCR-enabled UDC models. DCR provides a better estimation for the 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 L d ) and the conquering policy (with Loss L c1 for the Conquer step and L c2 for the Reunion step). The baseline in training dividing policy is the average reward over α initial solutions x i 0 , i ∈ {1, . . . , α} and the baseline for conquering policy is calculated over β sampled sub-solutions. The gradients of loss functions on a single instance G are calculated as follows:EQUATIONwhere {x 1 2 , . . . , x α 2 } represents the α sampled solutios. There are α⌊ N n ⌋ sub-problems G 0 c , c ∈ {1, . . . , ⌊ N n ⌋, . . . , α⌊ N n ⌋} generated based on {x 1 0 , . . . , x α 0 } in the first conquering stage with constraints Ω 0 c . α⌊ N n ⌋ can be regarded as the batch size of sub-problems, and G 1 c , Ω 1 c , c ∈ {1, . . . , α⌊ N n ⌋} is the sub-problems and constraints in the second conquering stage. The β sampled sub-solutions for sub-problem G 0 c , G 1 c , c ∈ {1, . . . , α⌊ N n ⌋} are noted as {s 1,i c , . . . , s 1,β c }, {s 2,i c , . . . , s 2,β c }.This subsection discusses the applicability of UDC to various CO problems. Most existing neural divide-and-conquer methods rely on problem-specific designs, so they are only applicable to limited CO problems. UDC uses no heuristics algorithms or problem-specific designs in the whole solving process, thus can be applied to 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 of initial solutions and sub-solutions can be ensured with feasibility masks.• The solution of the divided sub-problem is 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 on dense graphs or job scheduling problems, the solution of sub-problems has already been uniquely determined, so the conquering stages become ineffective.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 to have no negative social impact.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
experiment: 
 To verify the applicability of UDC in the general CO problem, we evaluate the UDC on 10 combinatorial 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. CVRP1,000 and CVRP2,000 contain 100 instances (following the generation settings in [13] ). The overall best performance is in bold and the best learning-based method is marked by shade. VRP (OVRP), and min-max multi-agent TSP (min-max mTSP). Detailed formulations of these problems are provided in the Appendix B.Implementation By employing lightweight networks for dividing policies, UDC can be directly trained on large-scale CO instances (e.g., TSP500 and TSP1,000). To learn more scale-independent features, we 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 are provided in Appendix D.1. 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 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] , POMO [5] , ELG [6] , ICAM [16] , MDAM [52] , et al.), heatmapbased solvers (DIMES [35] , DIFUSCO [39] , et al.) and neural divide-and-conquer methods (GLOP [13] , TAM [12] , H-TSP [20] , et al.). The implementation details and settings of all the baseline methods are described in Appendix G.Results on 500-node to 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 [16] and single-stage sub-path solvers [8] 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-x 2 ) but also the results after conducting more conquering stages (i.e., 50 and 250 stages, labeled as UDC-x 50 , UDC-x 250 ). In the following conquering stages after a greedy solution, the starting point of sub-problem dividing is no longer fixed at n 2 but is sampled from Uniform(0, n). For better performances, we sample α = 50 initial UDC variants demonstrate the best results in PCTSP, SPCTSP, CVRP1,000, and CVRP2,000, together with the best learning-based method in most involved CO problems. The UDC-x 250 (α=1) showcases extensive efficiency in OP, PCTSP, and PCTSP. Compared to sub-path solvers BQ [14] and LEHD [8] , UDC variants exhibit more competitive results on TSP1,000, TSP2,000, CVRP, and OP. RL-based constructive solver ICAM [16] with 8 augmentation [5] is outstanding performance on TSP500, 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-conquer methods GLOP [13] , H-TSP [20] , and TAM(LKH3) [12] , UDC achieves significant advantages in performance with no heuristic design, which preliminarily implies the significance of a unified training scheme for neural divide-and-conquer methods.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  
discussion: 
 The experimental results have preliminarily proven that the proposed UDC method achieves excellent results on a 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 E includes the ablation experiments on the testing procedure of UDC, including the ablation on the number of conquering stages r and the number of sampled solutions α.For neural divide-and-conquer methods, the unified training process does not require special designs for pre-training conquering policies, thus being easier to implement compared to separate training processes. Moreover, unified training can also avoid the antagonism between the dividing and 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 [13] ). According to the training curves of UDC and the two variants in Figure 3 , the unified training scheme demonstrates superiority, while the Pre-train step leads the training into local optima, which significantly harms the convergence of UDC. UDC adopts the state-of-the-art constructive solver ICAM [16] for conquering sub-TSP. However, the selection of constructive solvers for the conquering policy is not limited. We employ POMO [33] for the conquering policy, with experiment results of this version (i.e., UDC(POMO)) on TSP500 and TSP1,000 shown in Table 5.1 (α = 50 for all variants). The UDC framework demonstrates conquering-policy-agnosticism, as it does not show significant performance degradation when the conquering policy becomes POMO.In Appendix E.4, we further validate the conqueringpolicy-agnosticism of UDC on KP. We also conduct other ablation studies to demonstrate the necessity of other components of the proposed UDC, including the Reunion step in the DCR training method and the coordinate transformation in the conquering stage. 
conclusion, limitation, and future work: 
 This paper focuses on neural divide-and-conquer solvers and develops a novel training method DCR for neural divide-and-conquer methods by alleviating the negative impact of sub-optimal dividing results. By using DCR in training, this paper enables a superior unified training scheme and proposes a novel unified neural divide-and-conquer 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. In the future, we will focus on a more suitable loss for the UDC framework to further improve training efficiency. Moreover, we will attempt to extend the applicability of UDC to CO problems mentioned in Section 3.3 that are not applicable in the current version. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The new assets introduced in the paper are well documented and the documentation is provided alongside the assets (See Appendix G).Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as details about compensation (if any)?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 crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: In the following Appendix, we will provide a literature review A, detailed definitions of CO problems & sub-CO problems B, details of the proposed UDC method C, additional experimental results D, additional ablation study E, and visualizations on a TSP1,000 instance, a CVRP1,000 instance (i.e., X-n1001-k43 in CVRPLib), and a OP1,000 instance F.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-based) constructive solvers [51] , (RL-based) improvement-based solvers [59, 60] , (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.The basic idea of constructive neural solvers has been illustrated in Section 2.2. Up to now, constructive neural solvers are the most popular neural method for solving CO problems. By employing the self-attention mechanism [29] , the Attention Model [51] demonstrates the applicability among various VRPs and the efficiency in solving small-scale VRP instances. AM achieves outstanding results in 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-solving strategies [61, 62, 42] , others present more efficient network architectures [9, 52] , and some focus on designing better loss functions [5, 63] to better escape potential local optima.By employing a corresponding feasibility mask in each autoregressive construction step, constructive solvers can be effectively applied to most CO problems. Therefore, although many new 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 problem-specific constraints in their encoders. Therefore, we specifically use one-shot AGNN (consistent with the dividing policy) in sub-MIS, MatNet [41] for sub-ATSP, and DPN [42] to solve sub-min-max mTSP.Recent heatmap-based solvers propose methods to improve the performance of GNN-based frameworks [31, 32] . Attn-MCTS [37] proposes a heuristic method to merge the smaller heatmap obtained from different regions of a TSP instance into a larger heatmap of TSP. More importantly, Attn-MCTS also integrates an effective Monte-Carlo 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, 38] . DIMES [35] proposes a meta-learning method based on reinforcement learning for stability in training, while DIFUSCO [39] and T2T [66] use supervised learning to learn a diffusion process [67] of heatmap generation.The Table 1 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 a fully neural method as UDC, some neural divide-and-conquer methods strategically incorporate problem-specific heuristics in either the dividing or conquering stages to enhance performance or efficiency [22, 23, 21, 13] . Such a setting undermines the possibility to generalize to other CO problems.LCP [24] , H-TSP [20] , RBG [23] , TAM [12] , and GLOP [13] (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 a separate training scheme and we believe there are inherent shortcomings in the separate training schemes. Among them, LCP [24] employs a 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 a 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 a constructive neural solver, and GLOP chooses a heatmap-based 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.1 which can hardly converge to a good performance. The 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, it implements a joint training scheme after pre-trained conquering policies. However, Section 5.1 also demonstrates that the pre-training before a 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 as well, which further limits its effectiveness.We refer to the definition in [68] for large-scale CO problems. Large-scale CO problems have more data, decision variables, or constraints. In 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 as 500, 1000, 2000, etc. [39, 8, 16, 13] , so UDC follows this setting in testing TSP and applies it to general CO problems.TSP Traveling salesman problem (TSP) is one of the most representative COPs [69] . Let {D = d j,k , j = 1, . . . , N, k = 1 . . . , N } be the N × N cost metrics of a N -nodes TSP problem (in practice, transformed from the input node-wise coordinates), where d j,k denotes the cost between nodes k and j, the goal is to minimize the following objective function:EQUATIONwhere the solution x = (x 1 , x 2 , . . . , x N ) (τ = N ) is a permutation of all nodes. All the feasible solutions (i.e., in Ω of Eq. ( 1)) satisfy the constraint of node degree being two and containing no loop with lengths less than N.The sub-TSP in UDC is usually considered as an open-loop TSP problem [70] (i.e., SHPP in GLOP [13] ). To make the optimization target of both stages correspond (with objective function f (•) and f ′ (•), respectively), with the sub-cost metricsEQUATIONThe feasibility set of sub-TSP adds additional selection constraints for the starting and ending points (i.e., the first and last node in the original solution segments). UDC trains the TSP on various scales for every n 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, 000}). Since the nodes in each sub-problem always come from a compact region of the original instance, so we follow the normalization approach in GLOP and conduct a coordinate transformation to coordinates of sub-problems. The specific formula is detailed in Eq. (20) .CVRP CVRP incorporates the vehicle capacity as a restriction while considering the total distance as its objective function. Each CVRP contains a depot and several customers, on a cost matrix {D = d j,k , j = 0, . . . , N, k = 0 . . . , N }, the CVRP can be expressed as follows:EQUATIONwhere x is a solution representing the complete route of vehicles and consists of q sub-routes x = {ρ 1 , ρ 2 , . . . , ρ q }. Each sub-route ρ j = (ρ j 1 , . . . , ρ j nj ), j ∈ {1, . . . , q} starts from the depot x 0 and backs to x 0 , n j represents the number of customer nodes in it. n = q j=1 n j is the total In generating CVRP instances in test sets, we follow the common setting in [13, 14] , setting C = 100 for 500-node CVRP (i.e., CVRP500), C = 200 for CVRP1,000, C = 300 for CVRP2,000 and larger scale. In training, the capacity C is uniformly sampled from 100 to 200 [6, 16] .Similar to sub-TSP, Sub-CVRP is an open-loop CVRP (not forcing both starting and ending at depot x 0 for sub-route ρ 1 and ρ q ) and also restricts the selection of starting and ending nodes. Moreover, each sub-CVRP 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 4 , the capacity of the first and last sub-route is 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 [14] in representing CVRP solutions, converting the route into a solution and an aligned solution flag which is set to 1 for nodes before a depot.OP OP assigns each node a prize ρ i 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 a maximum length T . OP contains a depot node serving as 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 τ -length ordered sequence x = (x 0 , . . . , x τ ) (x 0 represents be depot, ρ 0 = 0) and {D = d j,k , j = 0, . . . , N, k = 0 . . . , N } is the N × N cost metrics of a N -nodes TSP problem, the objective function can be formulated as:EQUATIONWe follow the general OP (distance) (i.e., OP(dist)) setting to generate OP instances [51, 52, 63, 14] , whose prize of each node is calculated ρ i based on its distance to the depot. In practice, we follow the setting in AM [51] , ρi = 1 + ⌊99d0,i max N j=1 d0j ⌋, ρ i = ρi100 . The sub-OP in UDC contains a segment of the original solution while also randomly introducing some unselected nodes. By solving these sub-OPs, the conquering stage gains the potential to improve a low-quality initial solution to optimal. For sub-solution s, the objective function of sub-OP is f ′ (s) = i∈s ρ i . There is no normalization step in the conquering stage when solving OP. Sub-OP restricts the lengths of the generated sub-solution not surpassing the total length of the original sub-OP solution. One of the ⌊ N n ⌋ sub-OPs contains the depot and the depot is restricted to 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 l(x r ). So, we count the margin (i.e., T -l(x r )) of the constraint T in the current solution. In each conquering stage, we add the margin T -l(x r ) to the length constraint of a random sub-OP.PCTSP With a similar optimization requirement compared to OP, PCTSP is also a typical CO problem [51] . PCTSP gives each node a prize ρ i and a penalty β i . The goal is to minimize the total length of the solution route (a loop through all collected nodes as well) plus the sum of penalties of unvisited nodes. Moreover, as a constraint, PCTSP solutions should collect enough total prizes. The objective function is defined as follows:EQUATION)We follow the settings in AM [51] and GLOP [13] to generate PCTSP instances, ρ i ∼ Uniform(0, 4 N ),β i ∼ Uniform(0, 3 • K N N ).We follow the setting in [13] , define K N = 9, 12, 15 for N = 500, 1, 000, 2, 000.Compared to OP, UDC uses a similar way to process sub-PCTSP, introducing random unselected nodes in generated sub-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 ρ ′ i by dividing this constraint for better alignment, and the necessity of this procedure is demonstrated in Appendix E with ablation studies. The objective function of sub-PCTSP solution s is as follows:EQUATIONThe existing method GLOP [13] divides the PCTSP into sub-TSP, this problem-specific design not only harms the accessibility to 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 a notable difference to PCTSP, in SPCTSP, the real collected prize of each node only becomes known upon visitation but an expected node prize ρ * i ∈ Uniform(0, 2ρ i ) is known upfront. In solving SPCTSP with UDC, the expected node prize ρ * i is used to process sparse graph G D , heatmap H, and the encodings of conquering policy, while the real prize ρ i is only used to process the current states and constraints when constructing solutions of SPCTSP and sub-SPCTSP. KP Besides VRPs, KP is also a typical CO problem which can be formulated as follows:EQUATIONwhere X ⊆ {1, 2, ..., N } represents the selection item indexes (i.e., KP solution) in a knapsack and v i ∼ Uniform(0, 1) and w i ∼ Uniform(0, 1) is the value and weight of candidate objects. In each conquering step, sub-KPs are randomly sampled. Sub-KP and KP are identical in 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 a similar approach to OP in introducing the margin of maximum capacity (i.e., W -i∈X w i ) to sub-KPs, adding the current margin (i.e., capacity minus current load) to a random sub-KP.OVRP As a variant on CVRP, OVRP calculates the objective function of each sub-route as openloops. The objective function of OVRP is calculated as follows:EQUATION)ATSP ATSP is a variant version of TSP with asymmetric cost metrics {D = d j,k , j = 0, . . . , N, k = 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 it impossible to use conquering models such as POMO [5] , 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 [13] , conducting experiments on the 250-node (i.e., ATSP250), the ATSP500, and the ATSP1000.MIS MIS is originally defined on a graph G = {V, E} where N = |V| so in the dividing step we have G D = G directly (without additional operations to construct the sparse graph G D ). For solution set X ⊆ {1, 2, ..., N }, the objective function of MIS is to maximize the number of visited nodes in solution (i.e., f (X) = |X|) while ensuring no edge connections e ∈ E between any two visited nodes. In training, follow the MIS instance generation process of ER[700-800] with p=0.15 [35] . The nodes in sub-MIS are randomly selected and nodes connecting to visited nodes are constrained as unaccessible. The objective function of a sub-MIS solution S is f (S) = |S|. 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 [62, 42] . The solution of min-max mTSP is defined similarly to CVRP solutions, consisting of exactly M sub-routes (as a constraint on the number of total sub-routes) x = {ρ 1 , ρ 2 , . . . , ρ M }. The objective function of min-max mTSP is to minimize the length of the longest sub-route, which is as follows:minimize f (x) = M max i=1 C(ρ j ), C(ρ j ) = |ρ j |-1 t=0 d ρ j t ,ρ j t+1 + d ρ j n j ,ρ j 0 (15)Similar to the normal min-sum objective function, the min-max objective function can also be decomposed to independent objective functions of sub-problems so UDC can be evaluated on it. However, as the difference, the optimization of sub-min-max mTSP should encounter the lengths of sub-routes in adjunct sub-problems. For a sub-min-max mTSP with lengths of sub-routes in adjunct sub-problems being l b and l e , the objective function of sub-min-max mTSP solution with m sub-routes s = {ρ ′,1 , ρ ′,2 , . . . , ρ ′,m } is calculated after adding l b to the first sub-route length C(ρ 1 ) and l e to C(ρ m ) as follows:EQUATIONNote that only holding two adjunct sub-problems unchanged can make the optimization of the submin-max mTSP consistent with the original min-max mTSP. So, to maintain optimality, the testing stage will not update adjacent sub-min-max-mTSP simultaneously.Light-weight GNNs require constructing a graph as input (the sparse graph G D ). Some CO problems involved in this paper naturally have graph-like input (e.g., the MIS problem) so their sparse graph G D = 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-based solvers [31] and GLOP [13] , generally using the KNN method to connect edges in the edge set E ∈ G d . 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, for the KP without neighborhood properties, we use 1 -d ′ i,j max q∈1,...,N d ′ i,qas the weight of (i, j) for neighborhood selection where d ′ i,j = vi+vj wi+wj and use the KNN for edge connection as well. In the 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| = O(KN ).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 h ℓ i and e ℓ i,j denote the d-dimensional node and edge features at layer ℓ associated with node i and edge (i, j), respectively. The features at the next layer are propagated with an anisotropic message-passing scheme:EQUATIONEQUATIONwhere U ℓ , V ℓ , P ℓ , Q ℓ , R ℓ ∈ R d×d are the learnable parameters of layer ℓ, α denotes the activation function (we use SiLU [73] in this paper), BN denotes the Batch Normalization operator [74] , A denotes the aggregation function (we use mean pooling in this paper), σ is the sigmoid function, ⊙ is the Hadamard product, and N i denotes the outlines (neighborhood) of node i. We use a 12-layer (L=12) AGNN with a width of d = 64. The total space and time complexity of AGNN is O(KN d).In training all involved CO problems, the learning rate of the dividing policy is set to lr = 1e -4.T -revisit initial solution decoding. Next, based on the Eq. ( 4), the final layer edge representation e L i,j of AGNN is used to generate the heatmap. Heatmap-based solvers generally use an MLP to process the e i,j . To integrate partial solution-related representations in the heatmap, UDC has designed an additional T -revisit method, which will re-generate the heatmap by an additional T -1 times using MLPs based on the existing partial solutions after multiple heatmap decoding steps. This operation increases the time and space complexity to O(T KN d), but significantly improves the solution quality. Enabling the T -revisit method, the total initial solution generation strategy is shown below.EQUATIONIt represents decoding solutions from the heatmap H ∼ p(H|G, Ω, ϕ, x 0,1:⌊ N T ⌋c+1 ) and a new heatmap will generates every ⌊ N T ⌋ steps. For CO problems without a depot (i.e., TSP, KP, MIS, ATSP), p(x 0,1 ) = 1 N and for other CO problems, x 0,1 = depot and p(x 0,1 ) = 1. In training UDC, we set T = ⌊ N n ⌋. In testing, we generally set T = ⌊ N 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 CVRPLib-XXL datasets.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.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 ′ i,j = di,j maxo,q∈{1,...,N }do,q ) and other sub-CO problems are normalized following the method in GLOP [13] . Let (x ′ i , y ′ i ) denotes the coordinates of the i-th node after normalization, x max , x min , y max , and y min denote the bounds of an sub-VRP instance {(x 1 , y 1 ), . . . , (x n , y n )} (i.e., x max = max i≤n x i , et al.). Then, the coordinate transformation of coordinate (x i , y i ) is formulated as follows:EQUATIONwhere the scale coefficient sc = 1 max(xmax-xmin,ymax-ymin) . Besides normalizing the coordinates, sub-SPCTSP and sub-PCTSP normalize prizes of nodes by dividing the total collected prize of the current sub-solution.UDC adopts 5 solvers as the conquering policy, including AGNN [35] for MIS, ICAM [16] for TSP, CVRP, OVRP, and KP, POMO [5] for PCTSP, SPCTSP, OP, MatNet [41] for ATSP, and DPN [42] for min-max mTSP. 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 of all these solvers is set to lr = 1e -4 as well.The baseline calculation method in training conquering policies generally follows POMO [5] (sampling β sub-solutions for each sub-CO instance), but the generation process of the β sub-solutions is 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) so we enable a two sides conquering baseline, sampling β 2 solutions on both the starting and ending nodes. For other CO problems, we sample β 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 to last line in Table 7 for 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., β = 1) for asymmetric sub-CO problems and sampling only two sub-solutions (i.e., β = 2) for symmetric ones.Reason for using different solvers for different CO problems 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 [42] and ATSP [41] , 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 Table 7 ).UDC exhibits flexibility in choosing a constructive solver for conquering policy. For welldeveloped CO problems like TSP and KP, there are multiple constructive solvers available. Section 5.2 and Appendix E.6 present an ablation study on the selection of these constructive solvers for TSP and KP, respectively. 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 to model the conquering policy.The total algorithm of training UDC is presented in Algorithm 1. The total algorithm of testing UDC on instances is presented in Algorithm 2.Algorithm 1 UDC: Training dividing and conquering policy on general large-scale CO problems. Calculate the number of sub-tours decomposed from a tour:C = ⌊ N n ⌋ 9: {G i-1 1 , . . . , G i-1 C , . . . , G i-1 αC } ← 10:{{x 1 0,p:p+n , . . . , π 1 0,p+n(C-1):p+nC }, . . . , {x α 0,p:p+n , . . . , x α 0,p+n(C-1):p+nC }} 11:Apply coordinate transformation and constraint normalization to{G i-1 1 , . . . , G i-1 αC } 12:for k ∈ {1, . . . , αC}, j ∈ {1, . . . , β} doSamples i,j k ∼ π c (•|G i-1 k , Ω i-1 k , θ) 14: if i = 1 then 15:Update conquering policy θ ← θ + ∇ θ L c1 (G) ← ϕ + ∇ ϕ L d (G)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.It should be noted that the training objectives and MDP are not designed originally from UDC, they are also adopted in a series of neural divide-and-conquer methods [13, 20] .Objective functions of optimizing the two networks . For a CO problem (or a 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 (x 2 ) for the dividing policy (AGNN in UDC), -f (s 1 ) for the constructive solver (conquering policy) in the Conquer step (i.e., the first conquering stages), and -f (s 2 ) in the Reunion step. Calculate the number of sub-tours decomposed from a tour: SampleC = ⌊ N n ⌋ 14: {G i-1 1 , . . . , G i-1 C , . . . , G i-1 αC } ←s i,j k ∼ π c (•|G i-1 k , Ω i-1 k , θ) 19:end for 20:for k ∈ {1, . . . , αC} do 21:ŝi k = argmax s ′ ∈{s i,1 k ,...,s i,β k } f (s ′ ) 22:Substitute the s i,j k with no improvement on f (ŝ i k ) in sub-CO problems to the original solution.Merge solutions: {x 1 i , . . .EQUATION, . . . , Concat(ŝ i (α-1)C+1 , . . . , ŝi αC , x α i-1,p+nC+1,p )} State. State st d ∈ 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 = x 0,t = (x 1 , x 2 , ..., x t ). st d,0 is empty and st d,T = 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 , x 2 , ..., x t , x t+1 ) is valid (i.e., st d,T ∈ Ω).Reward. Every single time step has the same reward r d,t = -f (x 2 ) which is the objective function value of the final solution x 2 after the whole DCR process.Policy. The policy π d is shown in Eq. ( 4) (Eq. ( 19) for T -revisit enable).The MDP M c = {S c , A c , r c , P c } of any single conquering stage is represented similarly as follows:State. Each state st c ∈ S c represents the current partial solution. The state in the t-th time step is the current partial solution with t nodes st c,t = s t = (s 1 , s 2 , ..., s t ). st c,0 is empty and st c,T = 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 s, i.e., r c,t = -f (s).Policy. The policy π c is shown in Eq. ( 5). LEHD ICAM-single-start ICAM-N-start UDC-x 2 UDC-x r Time O(N 3 ) O(N 2 ) O(N 3 ) O(αT KN + n 2 ) O(αT KN + rn 2 ) Space O(N 2 ) O(N 2 ) O(N 2 ) O(αKN + α⌊ N n ⌋n 2 ) O(αKN + α⌊ N n ⌋n 2 )With a lightweight GNN for global partition and constructive solvers for parallel small-scale subproblems, both the time and space complexities of Both the time and space complexity of a single conquering stage on a single sub-problem is O(n 2 ).There are α⌊ N n ⌋ parallel sub-problems for each instance so the complexity should be α⌊ N n ⌋O(n 2 ). However, the α⌊ N n ⌋ sub-problems can be processed in parallel (as batch size = α⌊ N n ⌋) in GPUs, so the total time complexity of UDC with r conquering stages can be considered as O(αT KN + rn 2 ) and the space complexity is O(αKN + α⌊ N n ⌋n 2 ). Sub-path-based constructive solver adopts a decoder-only model structure so for a τ -length solution, the time complexity is O(τ 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-x 2 demonstrates less inference complexity compared to O(N 2 ) and exhibits superior efficiency. Empirical results especially very-large-scale experiments (N ≥ 5, 000) in Table 11 and Appendix D.5 prove the above statements.N 2 d) = O(N 3 ) (dHyperparameters of all 10 involved CO problems are listed in Table 7 . Training UDC on most CO problems adopts the varying-size [45] and varying-constraint [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 d = 256. In training UDC for TSP, we don't conduct the varying scale training in the first 50 epochs with α = 80. It can be seen that UDC adopts similar setups to solve different problems. The third to last and the second to last rows of Table 7 are related to the environment and the last row is unable to use a consistent setup and some flexibility in choices. Ablation studies in Section 5.2 and Appendix E discuss the setting of some listed hyperparameters, such as α in testing, DCR enable=False for KP, and the selection of conquering Policy in KP and TSP.The main part of this paper has evaluated the proposed UDC on large-scale instances of 5 representative CO problems. In this section. We will further evaluate the proposed UDC on more CO problems. OVRP is a variant of CVRP that has been widely involved in recent multi-task NCO work [75, 76] . We introduce this problem to test UDC's ability to handle open loops and distant point-to-point relationships based on CVRP. MIS is a classic CO problem widely used to evaluate heatmap-based solvers [35] , 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 is introduced to test the ability of 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 9 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.The experiment result is shown in Table 8 . Compared to the current best NCO method [75] POMO (Trained on OVRP100 with settings in [75] ), UDC demonstrates significant superiority in large-scale OVRP problems. Experiment on MIS: The MIS problem is a 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 Table9. UDC can also achieve good results on MIS after several conquering stages. Compared to the heatmap-based solver that originally relied on search algorithms, UDC shows better efficiency.Table 9 : Performance on 128-instance ER[700-800] test set (provided in DIMES [35] ). All the results are reported in DIMES [35] DIFUSCO [39] and T2T [66] . For MIS, the larger objective value (Obj.) is better. Experiment on ATSP: On ATSP, we compare the proposed UDC to traditional solver OR-Tools, constructive solver MatNet, and neural divide-and-conquer method GLOP. Results on ATSP250 to ATSP1,000 are shown in Table 10 and results of MatNet and GLOP are reported from GLOP [13] . We follow the data generation method in MatNet [41] and such a 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.). Experiment on KP: On KP, we involve OR-Tools (generally optimal on KP), POMO, and BQ as baselines. As shown in Table 11 , compared to BQ and POMO, both the UDC-x 50 (α=1) and UDC-x 250 (α=1) exhibit the best learning-based performance on KP500 and KP1,000. Moreover, UDC demonstrates outstanding time efficiency on KP1,000 and larger-scale KPs. Experiment on min-max mTSP: For min-max mTSP, we involve heuristic method hybrid genetic algorithm (HGA) [78] and LKH3, constructive method (parallel planning) 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 ∈ {30, . . . , 50}. The results in Table 12 demonstrate 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 is in bold. min-max mTSP N =500,M =30 N =500,M =50 N =1,The cross-distribution generalization ability of NCO solvers is also necessary. So we evaluate the UDC on the Rotation distribution, and the Explosion distribution provided in Omni_VRP [79] on TSP and CVRP. The result is shown in Table 13 , 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. 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 between UDC and the SOTA heuristics KaMIS (implemented on https://github.com/KarlsruheMIS/KaMIS) on the original in-domain dataset (ER-[700-800], p=0.15) 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. Unfortunately, we are unable to re-implement any learning-based methods for MIS (e.g. Difusco [39] and T2T [66] ), so we are unable to 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. 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,000, CVRP1,000, and PCTSP1,000 with UDC(α=1), UDC(α=50), GLOP [13] , LEHD (RRC) [8] , and DIFUSCO [39] . The results are shown in Figure 5 , and curves (except for DIFUSCO, which uses reported results) are generated under the same test set and computation resources. We can obtain the following conclusions:1. For the two variants of UDC, UDC(α=1) can generate better solutions compared to UDC(α=50) in a limited period but will trap into local optima quickly. For PCTSP, there is no significant difference in the final convergence result between the two versions.2. Compared to the advanced neural divide-and-conquer 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 a sufficient search on TSP, the two variants of UDC lead in the value of the objective function in a finite period.4. Compared to the SL-based sub-path solver LEHD with RRC [8] , the RL-based UDC(α=50) variant demonstrates competitive objective function values on CVRP, while both the two variants of UDC show higher efficiency on TSP and CVRP. In this subsection, we demonstrate the change in effectiveness of UDC relating to the numbers of initial solutions (i.e., α) for each CO problem. We use different α values to test the TSP, CVRP, OP, PCTSP, and SPCTSP (CO problems evaluated in the main paper) on their original test set. As exhibited in Table 18 , results with α = 50 always demonstrate significantly better performance but much more time consumption.However, the sensitivity of α on performance varies among different CO problems. In TSP, CVRP, and OP, the differences between results with α = 50 and results with α = 1 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 α = 50 is particularly pronounced. Since the difference in initial solutions is entirely from sampling the dividing policy, a more significant distinction between α = 50 and α = 1 variants might mean that the initial solution prediction is more difficult in 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. 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 19 demonstrate the significance of a good initial solution to the final performance. The UDC variants with a random initial solution or a 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. In the main part, we have shown the result of 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. For KP, there will be no sub-optimal connection as shown in Figure 2 , so there is 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. Therefore, when generalizing UDC to new CO problems, it may not be necessary to specifically choose which available constructive solver to model the conquering policy. In this section, we provide visualization to explain our procedure and show our effectiveness directly. As shown in 7, 8, and 9, respectively. Figures exhibit the initial solution, optimal solution, and reported solutions (i.e., UDC-x 2 (α=50), UDC-x 50 (α=50), and UDC-x 250 (α=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 the 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. The licenses for codes and datasets used in this work are listed in Table 22 .NeurIPS Paper ChecklistGLOP[13] utilizes heuristic dividing policy for TSP and Asymmetric TSP (ATSP) and neural dividing policy for CVRP and Prize Collecting TSP (PCTSP).OP aims to maximize the objective function, while PCTSP and SPCTSP aim to minimize the objective function. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: **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.
questions: 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?
2. 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: 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.

This 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.
paper_summary: paper_summary: The paper proposes a Divide-Concur-Reunion training approach for solving multiple "large" scale COPs.
strength_weakness: strength_weakness: [Major Comments]

1- 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.
 
2- 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).

3- 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. 

4- 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. 

5- 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? 

6- In the second paragraph of Section 3.1, the write-up covers VRP and TSP, but no discussion is given of the other problems. 

7- 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? 

8- 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?

9- What is “i” in \Omega_i in (5)? If it is from the set defined in line 132, shouldn't it be k? 

10- 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. 

11- What is the functions Rank and Top-k in line 190? Citation(s) or brief description is needed. 

12- How are the constraints in Appendix B being handled? 

13- 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. 

14- 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. 

[Minor]

There are many writing issues and typos in the paper. Few examples are: 

1- "exp" in (3) and (4) are denoted using different fonts. 

2- Subscripts of \script H is not defined in (4). 

3- The title of Section 3.3 can be "Applicability in General CO Problems". 

4- "Experiments" in line 199. 

5- "Definitions" in line 539.
questions: questions: See Weaknesses.
limitations: limitations: See Weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. 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.
3. 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. 
4. 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.
5. 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. 
6. 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.
7. 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.
questions: questions: See weakness
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: There are no major weaknesses in the article, my questions are presented in the Question section.
questions: 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?
2. The solution representation in the upper part of Figure 2 is not clear enough, please add illustrations in the Figure caption.
3. On TSPLib and CVRPLib, UDC seems to perform less prominently. Please provide the result of UDC on benchmark instances of other CO problems.
4. Please add more clear indexes in the main part for contents in the Appendix.
5. Should GLOP for TSPLib in Table 4 be GLOP more revision?
6. Do BS and bs in Table 3 represent beam search? Please provide a detailed introduction.
limitations: 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.

Comments: title: Message to AC
Further experiments to validate the capabilities and limitations.
Response to Rebuttal
Thank you
Comment about generalization with MIS
My concerns are partially addressed.
comment: Dear Area Chair,

Thank you very much for your effort in organizing the review of our work. Here is our summary of the author-reviewers discussion.

This paper presents a novel neural divide-and-conquer framework termed UDC for large-scale CO problems. UDC proposes a novel method DCR to enhance training by alleviating the negative impact of sub-optimal dividing policies. Leveraging DCR in training, the proposed UDC achieves a unified neural divide-and-conquer training scheme, it demonstrates extensive applicability and has been evaluated on 10 CO problems with outstanding performances.

After the discussion period, **all four reviewers** appreciated the effectiveness and broad applicability of UDC. 

**Reviewer Uqww** found the article easy to follow, the idea of DCR is quite novel, and experiments give detailed explanations on the setting reason for hyperparameters and components. Reviewer Uqww raised the rating from Weak Accept (6) to **Accept (7)** after the discussion and believed that our work ``is inspiring to the NCO research``.

**Reviewer Eauz** found that UDC integrates a novel training methodology that effectively addresses the challenge of sub-optimal divide policies and rated our work as **Weak Accept (6)**. 

**Reviewer kAJo** found the proposed UDC does not heavily rely on problem-specific heuristics compared to the previous works and the idea of considering interdependencies between dividing and conquering stages is interesting as a neural CO training scheme. Reviewer kAJo raised the rating from Borderline Reject(4) to **Borderline Accept (5)** after the discussion.

**Reviewer h7Dg** found that UDC handles several problems under the same framework with possible different components per CO problem. After discussion, reviewer h7Dg found some of the comments were well explained and raised the rating from Reject(3) to **Borderline Accept (5)**. Reviewer h7Dg further suggested conducting the out-of-domain generalization experiments on CO problems besides TSP and CVRP to validate the capabilities and limitations of UDC. We have supplemented the generalization experiments of UDC on the MIS problem and will also conduct the generalization tests on more CO problems in the camera-ready version accordingly.

Best Regards,

Paper12083 Authors
>**Further experiments to validate the capabilities and limitations**:

Thank you for your valuable suggestions on generalization experiments. In addition to 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$\sim U(700,800)$ and p=0.15 to five other datasets, including:

* A random ER graph dataset with n=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 SNAP. (4,039 nodes, 88,234 undirected edges)

* The feather-lastfm-social 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 non-connected graph. The table below exhibits the comparison results between UDC and the SOTA heuristics KaMIS (implemented on https://github.com/KarlsruheMIS/KaMIS) on the original in-domain dataset (ER-[700-800], p=0.15) 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.


| Dataset                   || |ER, n=720,   p=0.05 | |||ER-[700-800], p=0.15| (in-domain)       |
|---------------------------|-|-------------|-------------|---------|-|-----------------|-----------------|-----------------|
| Method                   | | Obj.        | Gap         | Time   | | Obj.            | Gap             | Time            |
| KaMIS                    | | 99.5        | -           | 40.6m  | | 44.9            | -               | 52.13m          |
| UDC-$x_0$($\alpha=50$)    || 79.5        | 20.10%      | 8s   |   | 41.0            | 8.62%           | 40s             |
| UDC-$x_{50}$($\alpha=50$) || 89.5        | 10.07%      | 9.03m  | | 42.9            | 4.44%           | 21.05m          |
| UDC-$x_{250}$($\alpha=50$)|| 94.5        | 5.03%       | 44.84m  || 43.8            | 2.41%           | 1.73h           |
| **Dataset**               | ||**ER, n=720, p=0.25**   |||| **ER, n=2,000, p=0.05**               |   |
| Method                   | | Obj.        | Gap         | Time  |  | Obj.            | Gap             | Time            |
| KaMIS                    | | 28.2        | -           | 1.4h   | | 133.9           | -               | 3h              |
| UDC-$x_0$($\alpha=20$)    || 21.6        | 23.46%      | 58s   |  | 116.9           | 12.72%          | 2m              |
| UDC-$x_{50}$($\alpha=20$)| | 25.3        | 10.54%      | 21m  |   | 119.1           | 11.05%          | 21m             |
| UDC-$x_{250}$($\alpha=20$)|| 26.4        | 6.59%       | 63m   |  | 122.9           | 8.25%           | 90m             |
| **Dataset**                 | |**SNAP-** | **ego-Facebook** | ||**SNAP-**| **feather-lastfm-social**            ||
| Method                   | | Obj.        | Gap         | Time  |  | Obj.            | Gap             | Time            |
| KaMIS                    | | 1052.0      | -           | 155s  |  | 4177.0          | -               | 0.1s            |
| UDC-$x_0$($\alpha=1$)     || 767.0       | 27.09%      | 6s |     | 3622.0          | 13.29%          | 2s              |
| UDC-$x_{250}$($\alpha=1$)| | 901.0       | 14.35%      | 11s|     | 3751.0          | 10.20%          | 13s             |
| UDC-$x_{2500}$($\alpha=1$)|| 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-feather-lastfm-social, UDC variants have significant advantages over KaMIS in terms of time.


As for learning-based methods, currently, we are not able to run the given code of any learning-based algorithm with given instruction, so we are temporarily unable to compare the generalization ability with other learning-based algorithms. We will try to include these learning-based baselines in future manuscripts. In addition, besides MIS, we will also strive to conduct generalization tests on more CO problems.

We hope the above discussion could address your remaining concerns. Please let us know if you have any further concerns.
Thanks for your support and positive score. We are glad to hear your appreciation of the broad applicability of UDC and that our explanation has addressed your concerns.
Thank you for your detailed and thoughtful rebuttal. Your explanations have addressed my concerns, particularly regarding the flexibility of the UDC framework in terms of architecture and solver selection. I now have a better understanding of how the framework ensures feasible solutions during the division stage and the level of tuning required for different problem types.

This is indeed an impressive framework with broad applicability across various combinatorial optimization problems. I am satisfied with your responses and will maintain my positive score.
Thank you for raising the score.
Thanks for you rebuttal. I would like to raise my scores.
Thank you for changing the score. Sorry, we're a little confused about your question. Does the graph embedding refer to the embedding itself or its size? 

If it is the former, different graph inputs are bound to get different embeddings. 

If it is the latter, the answer is no. The calculation methods of embeddings are unchanged regardless of the size of the input graph. The obtained graph embeddings on each vertex are always d-dimensional vector $\mathcal{R}^{d}$ and no new parameters will be introduced.

When AGNN computes the graph embedding of each vertex, it only needs the neighborhood information of this vertex, without the full graph information. Therefore the computation of embeddings is independent of the graph size.
Thanks for pointing this out. I did change the score. 

My question can be answered without an experiment. I wanted to know if the proposed model, when tested with graphs with larger size than the training set, does the encoding change? If yes, would newly un-optimized parameters be fine-tuned or left randomly chosen?
Thank you very much for your prompt reply. We will conduct the experiment mentioned in the 2nd point of Generalization first.

The option to change the score can be found by editing the initial submitted official review.
Could the authors answer the question I raised in the 2nd point of Generalization. 

In regard to the score, I did not see the option to change the score.
Thank you very much for your valuable comments and raising your score to 5. We are glad to hear that some of your concerns have been resolved and that you recognize the advantage of UDC in applicability. We will include these details in our manuscript and provide a formal definition of large-scale accordingly. 

Thank you very much for your helpful suggestions on the generalization study. We will try our best to accomplish these experiments as soon as possible and provide the results before the end of the rebuttal period.

By the way, the score in the system seems to remain unchanged. Could you please double-check it?
Definition of large Scale instance: 

- CO problems have been well-studied, with a history dating back to the seventies (see "Reducibility among combinatorial problems" for an example). Understanding the difficulty of each problem should give the authors a better sense of which instances are more challenging to solve and, therefore, evaluate them accordingly. Harder instances may not necessary be larger instances. For the MIS example, mid-density graphs (w.r.t. complete graphs) with n~2000 is much harder to solve in KaMIS and ILP solvers when compared to the very-large and very sparse SNAP dataset graphs (with million of nodes).  

Generalization: 

- Generalization in COPs shouldn't rely on the availability of a dataset. Most datasets in COPs were specifically created for ML4CO methods, but that doesn't mean datasets will always be available in practice. For example, in the case of MIS, apart from the SATLIB dataset (which represents hard, sparse instances compared to ER), there are no other datasets with accurately known MISs.

- The generalization test can be as simple as the following: Evaluate your ER-trained model with different values of p and n. Does your model require different graph embeddings for larger graph sizes?

- For SNAP, you can compare with SOTA heuristics (KaMIS) unless the proposed model requires different embeddings or needs to be trained from scratch (or possibly fine-tuned). If any of these conditions apply, they should be stated and discussed.

- Prior to the development of DNNs, we didn't know how to classify images. This is not the case for COPs as they are not typical supervised ML problems. For COPs, we already have (1) well-performing problem-specific heuristics and/or ILP solvers, and (2) a large body of previous problem-specific studies that investigate the hardness of every problem.     

- Please note that I am not saying that the proposed method should obtain SOTA results (in terms of both solutions sizes and run-time) on all CO problems on all instances, but I am saying that the proposed framework should be evaluated such that the limitation/capabilities are clear and understood with the main target: Can the proposed framework, by any metric, outperform SOTA problem-heuristics that does not require any data on a specific instance(s)? For MIS, the results in Table 9 says otherwise if we count for the nearly 10 days of training. Even if we exclude the training time and observe only that the inference time (21.05m), can the proposed method outperform KaMIS when p or n change for ER? These are the types of questions that should be accounted when evaluating the 10 problems. 

- I acknowledge the authors results for TSP in Tables 3 and 4 of the one-page PDF in the rebuttal. This is a good example of evaluating the performance UDC for a CO problem. 


Overall: 
- My comments on solving time, pipeline Settings, description of MDP and the training algorithm, and constraints handling are well explained by authors. I highly recommend to integrate these into subsequent versions of the paper. 
- I think the advantage of this proposed framework is obtaining solutions (not necessarily the best in terms of solution quality and run-time) to some instances of 10 different CO problems. 
- I thank the authors for their efforts and the additional experiments. As such, I will increase my score to 5 as I still believe that the capabilities and limitations of the proposed framework of most problems are not well-understood.
Thanks for your support and raising the score to 7. We are delighted to hear your appreciation for the novelty, effectiveness, and wide applicability of UDC.
Thank you for your response, which has addressed my concerns. I raised my score to 7. I appreciate the novelty and effectiveness of UDC, especially its wide applicability. This work is inspiring to the NCO research so I think it should be accepted.