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

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the idea of DCR quite novel, UDC exhibits effectiveness in 10 different CO problems, the article is easy to follow, and experiments give detailed explanations on the setting reason for hyperparameters and components.

We address your concerns point-by-point as follows:

Question 1. Reason for applicability: UDC shows wide applicability compared to existing NCO methods. What is the reason for its significant advantage in applicability compared to existing divide-and-conquer methods?

The wide application of UDC on large-scale CO problems mainly depends on two reasons as follows: 1) UDC gets rid of the heuristic components in both the dividing policy and the conquering policy (as shown in Table 1 in the original paper). Heuristic components often require expert knowledge to redesign when handling unseen instances and new CO problems, thus undermining the applicability of methods. 2) The efficient training method DCR enables a unified training framework for all CO problems. The unified training framework does not rely on the design of separate pre-training procedures or tunings for specific CO problems, making UDC easy to apply to new CO problems.

Question 3. Benchmark experiments: Please provide the result of UDC on benchmark instances of other CO problems.

Thank you for your suggestion. We further evaluate the proposed UDC on the benchmark dataset of min-max mTSP. The benchmark dataset of min-max mTSP contains instances from 500 to 1,000 nodes. It includes the u574 instance, the p654 instance, and the rat783 instance (selected by the paper of Equity-Transformer [1] and we use the reported results from [1]). Objective values of methods are shown in the table below. Compared to Equity-Transformer and the heuristic method LKH-3 and OR-Tools, UDC-$\boldsymbol{x}_{50}$ ($\alpha=50$) can significantly lead.

Question 2,4. Writing clarity.

Thanks for your valuable suggestion. The upper part of Figure 2 shows the pipeline of the training method DCR. In the DCR-enabled training process, there are two conquering stages, the Conquer step and the Reunion step, where the Reunion step is introduced to eliminate the negative impact of the sub-optimal dividing policy. The lower part provides a local view of a solution fragment to demonstrate our motivation. DCR has the potential to correct wrong dividing results by generating the solution of the connection part in the Reunion step.

We will include this illustration in the caption of Figure 2, use more appropriate colors for better expression, and add more indexes in the main part for contents in the Appendix of the original manuscript.

Question 5,6. Abbreviation in Tables.

Thank you for your comments. Yes, in Table 4 in the original paper, the GLOP for TSP should be GLOP more revision instead of GLOP-LKH3. We will change the index in Table 4 to GLOP and provide an additional description of the settings.

Yes, both BS and bs in Table 3 of the original manuscript represent the beam search. Beam search is a commonly used decoding strategy in autoregressive sequence model decoding, which is a form of breadth-first search (BFS) [2]. Attention Model [3] first introduces the technique into the field of NCO. For a beam limited to k (noted as bs$k$ in Table 3 of the original manuscript, e.g., bs1024 or bs16), the beam search will construct k solutions with top probabilities sampled from the model policy. Models with beam search in decoding can get better results with more solving time.

Limitation: Chapter 3.3 discusses the unavailability of UDC on certain CO problems, such as TSPTW. This should also be included in discussing the limitation.

Thank you for pointing this out, we will include the content discussed in Chapter 3.3 in the illustration on limitations.

---

References

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

[2] Meister, Clara, Tim Vieira, and Ryan Cotterell. "If beam search is the answer, what was the question?." arXiv preprint, 2020.

[2] Kool, Wouter, Herke Van Hoof, and Max Welling. "Attention, learn to solve routing problems!." arXiv preprint, 2018.

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the proposed UDC achieves competitive results and can handle several problems under the same framework with possible different components per CO problem.

We sincerely appreciate the effort you have put into reviewing this article and we address your concerns as follows.

Weakness 1. Definition of large-scale.

We agree that the definition of large-scale cannot only consider the size of instances. As the definition in [1], the large-scale CO problem has more data or decision variables or constraints (large-size sparse graphs might have relatively more decision variables, data, and fewer constraints). We will provide a clearer definition of large-scale CO problems.

Weakness 2 & 4. Generalization.

We deeply agree that the generalization performance on instances with different parameters is essential to test NCO methods. However, we have to declare that for some CO problems, there are no established datasets to evaluate the generalization. When generalizing the model trained on the ER graph with p=0.15 to the Social circles: Facebook graph in the SNAP dataset, we find UDC can also output legal solutions with seemingly good objective values but there is no ground truth of MIS on the graph so we cannot check the ability of UDC on it.

We evaluate the generalization performance of UDC on established out-of-domain datasets, e.g., vehicle routing problem (VRP) instances with coordinates sampled from non-uniform distributions. As exhibited in Table 13 in Appendix D.3, the generalization ability of UDC on TSP and CVRP can surpass existing neural solvers. Such advantage may be attributed to the normalization process in the conquering stage.

Weakness 3. Solving time.

Firstly, we apologize for the typo in the time results of OVRP and we will revise it to the content shown in Table 3 of the one-page PDF, where LKH3 takes 16 minutes for the OVRP500 dataset, 32 minutes for OVRP1,000, and 27 minutes for OVRP2,000.

We agree that neural methods should tackle what heuristics and exact solvers cannot handle, especially when heuristics has only low performance or requires an unacceptable time to generate solutions. In certain CO problems, UDC can compensate for the above two situations. Considering performances, UDC can produce better results than all available existing heuristics in (S)PCTSP and min-max mTSP. For solving time, we acknowledge that NCO methods require additional training time, which is time-consuming. However, well-trained models, such as UDC for large-scale OP and TSP, can generate good solutions within several seconds. Compared to heuristics, the online solving characteristic of UDC may be valuable for practical applications that require response speed.

Weakness 5-7, 13. Pipeline settings.

Thanks for your comments. We will improve the expression in Section 3 and Appendix B based on your suggestions to eliminate ambiguity, and we will also publish all the code after the paper is published to show the detailed implementation.

For weakness 5, in non-graph input CO problems, especially VRPs, constructing sparse graphs aims at deleting more useless edges to reduce the time complexity. It is a general step for existing heatmap-based solvers. By processing only sparse graphs, each layer of GNNs can achieve a time complexity of O ($KN$) ($K$ is the neighbor size, usually 100 in UDC), which is helpful to large-scale VRPs. In addition, this procedure is to construct sparse graphs for instances rather than graph sparsification. For MIS, the ER graph with p=0.15 is a sparse graph itself so there are no additional steps needed for constructing sparse graphs. For weakness 7, Sub-MIS is generated with random nodes from the original MIS.

Weakness 8 & 10. MDP & training.

Please refer to Common Concern 2 for the MDP definition & objective functions.

Weakness 11: Line 190.

Only CO problems with decomposable aggregate functions [2] can be solved by the divide-and-conquer method. So UDC can not apply to CO problems with indecomposable aggregate functions such as minimizing the visiting rank of given nodes or the top-k longest route in a graph.

Weakness 12. Constraint handling.

Feasibility masks will mask the illegal action in generating both initial solutions and sub-solutions (You can also refer to Question 1 of reviewer Eauz for details).

Weakness 14. Unified configuration.

We need to declare that 'unified' in this article means that UDC adopts a unified training framework for the diving and conquering stages. For the 10 CO problems involved, there is no unified conquering policy that can solve all problems (Please refer to Common Concern 1) so UDC adopts different conquering policies for different CO problems.

The third to last and the second to last rows of Table 7 are related to the environment or constraint of different CO problems. For KP, the sub-optimal connection shown in Figure 2 in the original paper will not occur, so there is no optimality difference in whether DCR is enabled. We provide the KP results with DCR enabled in Table 2 of the one-page PDF and these results support the above conclusion.

The two-side conquering baseline may not be applicable in certain CO problems like ATSP and CVRP where reversing the sub-solution will be illegal, so we disable such baseline in these problems. We will add an explanation to summarize all the settings in Table 7.

Minor Weakness & Weakness 9. Typos.

Yes, the $\Omega_i$ should be $\Omega_k$. Thanks for pointing typos out, we will fix all of them accordingly.

---

References

[1] Gervet, Carmen. "Large scale combinatorial optimization: A methodological viewpoint." DIMACS series, 2001.

[2] Jesus, Paulo, Carlos Baquero, and Paulo Sérgio Almeida. "A survey of distributed data aggregation algorithms." IEEE Communications Surveys & Tutorials, 2014

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.

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.

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.

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.

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the proposed UDC framework is designed with applicability to a wider range of CO problems, and its performance is shown to be generally good on certain problems.

Weakness 1. Novelty of UDC.

Thanks for your insightful comments. Neural-divide-and-conquer methods are indeed a combination of existing methods in terms of network structure and solving process. However, we would like to declare that the significant novelty of UDC lies in its training approach.

Considering the training approach, we do not agree that the technique in the Reunion step resembles prevalent tricks in the neural CO literature. The training methods you mentioned (i.e., POMO/Sym-NCO, etc.) are all for obtaining the RL baseline for single-stage constructive solvers [1]. However, the DCR training method proposed in this article is designed to handle the negative impact of sub-optimal dividing results in neural divide-and-conquer methods (as shown in Table 1 in the original manuscript), which is novel in NCO methods.

As demonstrated in the paper, the DCR training method can significantly facilitate the applicability and effectiveness of UDC.

Weakness 2. Training process.

Thanks for your suggestion. UDC employs a neural network for the dividing policy and another network for the conquering policy. In a Divide-Conquer-Reunion (DCR) enabled training process, the model for conquering policy will successively update its parameters twice according to the loss $\mathcal{L} _ {c1}(\mathcal{G})$ and $\mathcal{L} _ {c2}(\mathcal{G})$ after the Conquer step and the Reunion step, respectively. Finally, we will calculate the dividing loss function $\mathcal{L} _ {d}(\mathcal{G})$ based on the solution $\boldsymbol{x}_ 2$ and the dividing policy will update the model parameters according to the dividing loss.

A pseudo-code of the training process is provided in Algorithm 1 in Appendix C.6. Please refer to Common Concern 2 for MDP & Training objectives and we will provide more implementation details to increase the clarity of illustrations.

Weakness 3. Solving time.

Thanks for your constructive comments. For a better discussion, we respond to the two concerns in Weakness 3 in reverse order.

The number of conquering stages: Both the solving time and solution quality of UDC are related to the number of initial solutions $\alpha$ and the number of conquering stages $r$. Therefore, we conduct ablation experiments on the two factors in Appendix E.1 and Appendix E.2, respectively, in the original paper. Changing the $r$ value to adjust solving times, the results in Figure 5 of the original paper demonstrate that UDC has an efficiency advantage, as its variants generally need less time for better performance compared to the SOTA neural divide-and-conquer methods GLOP and SL-based sub-path solver LEHD.

Solving time of UDC: Based on the results above, together with Table 3 and Table 17 of the original manuscript, when generating solutions with $\alpha$=1, UDC can generate acceptable solutions with a significant advantage in solving speed.

Additionally, we are sorry for an index mistake in line 816 where Figure 6 should be Figure 5.

Weakness 4. Supervised learning.

Although SL-based approaches achieve better performance in some CO problems like TSP and CVRP, we believe that the SL method is not suitable for sub-problem conquering for Poor applicability: using SL for sub-problem conquering requires a large number of high-quality heuristic algorithm solutions as training labels. However, in most CO problems, heuristic algorithms are not outstanding (e.g., PCTSP) or are too time-consuming (e.g., min-max mTSP). Therefore, SL-based sub-problem conquering will compromise the availability of UDC for these CO problems.

Weakness 5. Applicability.

Yes, according to the discussion in Section 3.3, UDC can handle combinatorial optimization problems that meet the conditions.

This paper chooses the 10 CO problems to evaluate UDC, mainly because they have established datasets, baseline methods, and constructive solvers. When a new CO problem has developed established datasets, baseline methods, and constructive solvers, it can also be incorporated to evaluate the proposed UDC framework.

Weakness 6. Initial solution.

Thanks for your valuable suggestion. We further conduct experiments on TSP with different initial solutions, and the results are shown in Table 4 of the one-page PDF. Results demonstrate the contribution of a good initial solution to the final solution. The variants with a random or nearest greedy initial solution cannot converge to good objective values even with 50 UDC conquering stages. Moreover, from TSP500 to TSP2,000, the dividing policy of UDC produces similar results to the heuristic algorithm random insertion, which verifies the quality of the dividing policy.

Weakness 7. Readability.

Thank you for your suggestion. We will unify the reporting methods, add footnotes, clarify all method names and references, and provide more instructions for appendices accordingly to improve readability. In Table 2 in the original manuscript, we will supplement the reported results of T2T [4].

---

References

[1] Berto, Federico, et al. "Rl4co: an extensive reinforcement learning for combinatorial optimization benchmark." arXiv preprint, 2023.

[2] Drakulic, Darko, et al. "Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization." Advances in Neural Information Processing Systems 36, 2024.

[3] Bertazzi, L. et al. Min–max vs. min–sum vehicle routing: A worst-case analysis. European Journal of Operational Research, 2015.

[4] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find the proposed UDC integrates a novel training methodology, demonstrates broad applicability across various large-scale CO problems, and outperforms several baseline methods.

We address your concerns as follows.

Weakness 1. Dependence on specific architectures: The success of the method heavily relies on the choice of graph neural networks and the specific configurations of constructive solvers, which might not generalize across all types of combinatorial optimization problems.

Thanks for your insightful comments. However, we respectfully disagree with you that the success of UDC heavily relies on the choice of graph neural networks and the specific configurations of constructive solvers. Our reasons are as follows:

Constructive solvers: As illustrated in Common Concern 1 of the general response, UDC involves 10 CO problems and it is impossible to employ the same constructive solver for all CO problems [1]. However, UDC exhibits outstanding flexibility in employing different constructive solvers as the conquering policy. Experiments mentioned in Common Concern 1 show that the final performance of UDC does not rely on a specific constructive model for the conquering policy, which means that any available constructive solver with good performance can be chosen.

Graph neural networks (GNNs): The current UDC framework only evaluates the AGNN for the dividing policy across all 10 CO problems. However, the use of AGNN [2] in UDC is not a specific choice as well. 1) UDC adopts GNN instead of other network structures because of its lightweight memory and time consumption and 2) AGNN is one of the most basic forms of massage-passing neural network [3], which only calculates the bidirectional edge information and bidirectional node information within neighbors. 3) When using AGNN to process embeddings of all 10 CO problems, UDC follows a consistent configuration.

Question 1. feasible initial solution: How does the UDC framework ensure that feasible initial solutions are generated during the division stage, particularly when traditional heuristics are not applicable?

For involved CO problems, UDC autoregressively constructs the initial solution node-by-node based on the heatmap generated by GNN. At every step, it employs a feasibility mask mechanism to ensure the feasibility of the final generated solution. This mechanism is fundamental in both heatmap-based solvers [4] and constructive solvers [5]. It prevents the selection of nodes that would lead the next partial solution outside the set of all feasible solutions $\Omega$. For example, the feasibility mask mechanism for TSP will mask the selection probabilities of all visited nodes to 0.

With the feasibility mask, the dividing policy can construct valid solutions for most CO problems. UDC cannot apply to the relatively rare CO problems where the feasibility mask mechanism cannot ensure a valid initial solution.

Question 2. Requirement on tunning: Does the UDC framework require extensive expert intervention for tuning neural network parameters and training regimens to achieve optimal performance, especially when adapting to new or unseen problem types?

UDC does not conduct special tuning for specific CO problems. As shown in Appendix D.1, we use the same learning rate and AGNN structure across all 10 CO problems.

When applying to a new problem type, UDC requires:

1) Employing an available constructive solver for conquering policy (Please refer to Common Concern 1 & Weakness1).

2) Set up new RL environments and feasibility masks based on constraints.

3) Changing $\alpha$ and $\beta$ to maximize the CUDA memory usage. Note that this change is not for solving performance and will only facilitate training efficiency.

---

References

[1] Kwon, Yeong-Dae, et al. "Matrix encoding networks for neural combinatorial optimization." Advances in Neural Information Processing Systems 34, 2021.

[2] Xavier Bresson and Thomas Laurent. "An experimental study of neural networks for variable graphs." In ICLR 2018 Workshop, 2018.

[3] Gilmer, Justin, et al. "Message passing neural networks." Machine learning meets quantum physics, 2020.

[4] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems 35, 2022.

[5] Zhou, Changliang, et al. "Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization." arXiv preprint, 2024.