UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems
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.
Paper
Similar papers
Peer review
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.
Strengths
1. This paper conducts extensive experiments. UDC exhibits effectiveness in 10 different CO problems, improving the existing divide-and-conquer methods in both effectiveness and applicability. 2. This paper validates the importance of unified training. The idea of DCR is quite novel. 3. The article is easy to follow and experiments give detailed explanations on the setting reason for hyperparameters and components.
Weaknesses
There are no major weaknesses in the article, my questions are presented in the Question section.
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.
Rating
7
Confidence
4
Soundness
3
Presentation
3
Contribution
4
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.
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.
Strengths
1. The DCR method proposes a view of unifying the training of dividing and conquering stages for solving large-scale CO problems. 2. The UDC framework is designed with applicability to a wider range of CO problems, without heavy reliance on problem-specific heuristics like in the previous works. 3. The idea of considering interdependencies between dividing and conquering stages is interesting as a neural CO training scheme. 4. The authors conduct extensive experiments where the proposed framework's performance is shown to be generally good on certain problems.
Weaknesses
1. The novelty of the proposed framework requires further explanation. The current UDC/DCR seems to be a combination of existing techniques in either dividing or conquering stages. From a local perspective, 1) the sub-problem dividing policy is simply a conventional continuous node split based on the initial solution, 2) the conquering phase is a direct exploitation of existing problem-specific models like POMO, ICAM, MatNet, etc., to tackle the small scaled sub-problem, and 3) the technique in the reunion part resembles prevalent tricks in the neural CO literature, such as POMO/random-start/multi-sampling/random augmentation, etc. Therefore, the proposed unified framework is more of a mathematical or conceptual summarization of the current RL-based divide-and-conquer pipeline rather than a novel methodology for tackling various CO problems using a unified architecture. 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
See weakness
Rating
5
Confidence
4
Soundness
3
Presentation
2
Contribution
2
Limitations
NA
Summary
The paper proposes a Divide-Concur-Reunion training approach for solving multiple "large" scale COPs.
Strengths
1- Handling several problems under the same framework with possible different components per CO problem. 2- When compared to learning-based methods, in terms of testing time and solutions sizes, the proposed approach achieves competitive results. 3- The Divide-Concur-Reunion training algorithm.
Weaknesses
[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
See Weaknesses.
Rating
5
Confidence
4
Soundness
2
Presentation
1
Contribution
2
Limitations
See Weaknesses.
My concerns are partially addressed.
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 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?
Comment about generalization with MIS
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 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.
Thank you
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 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.
>**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.
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.
Strengths
1. **Innovative Framework**: UDC integrates a novel training methodology that effectively addresses the challenge of sub-optimal divide policies, improving overall solution quality. 2. **Extensive Applicability**: The framework demonstrates broad applicability across various large-scale combinatorial problems, confirming its versatility and effectiveness. 3. **Strong Empirical Results**: UDC outperforms several baseline methods on a diverse set of problems, which strongly supports the utility and efficiency of the approach.
Weaknesses
**Dependence on Specific Architectures**: The success of the method heavily relies on the choice of graph neural networks and the specific configurations of constructive solvers, which might not generalize across all types of combinatorial optimization problems.
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?
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
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.
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.
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 raising the score.
Response to Rebuttal
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.
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.
Message to AC
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
Decision
Accept (poster)