- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes Reduce-then-Solve (RS), an overall framework for learning for combinatorial optimization. The framework builds on global prediction, which predicts retention scores. These scores are used to reduce the problem into residual subproblems, which are re-solved with a local constructor. The whole process is then looped across a number of global and local steps. The authors instantiate their framework for the TSP, CVRP and CVRPTW, using SymNCO for the local component and PRF for the global component, and show clear improvements in performance in comparison to baselines.
Critical strengths
-
The overall method is exceptionally sound, combining strengths of several paradigms to mitigate their individual weaknesses. The role of the global predictor as an edge-retention predictor, together with the LinkGraph construction and local constructor repairing the solution is novel to the best of my knowledge. The framework is also agnostic to the instantiation of the individual components, even showing promising results in a non-learned context. Thus the overall framework seems genuinely useful for the community, and I believe there are multiple ideas to build further on.
-
Empirical performance is strong, with both clear runtime and quality improvements across a wide suite of problems and setups. The experimental design also seems sound, with key choices motivated well in the text.
Critical weaknesses
-
My main weakness concerns ablation. Since the framework includes many components, both learned and classical, it is difficult to establish what drives performance. In particular, the three local search stages and random perturbations (see Algorithm 2) are not ablated. To what extend do these contribute to the performance? Similarly, are the neural components even needed? Given that the method relies so much on local search, what happens if you replace learned components with weaker classical heuristics? The MCut experiments, while showing the broad applicability of the framework, also supports the conclusion that learned components are not necessary. Finally, I would also have liked to see clearer runtime-vs-quality curves compared to baselines (perhaps presented as figures) rather than the somewhat artificial "fewer" vs "more" variants.
-
The presentation could be improved throughout. For instance, it would help to focus on one problem, e.g., the TSP, through the main text and description of the method. The text is also notation dense and at places jargon-heavy. In particular, the Progressive Reduction and LinkGraph sections are hard to follow. The former also seems to contradict itself, to my understanding, since it says that the size of the retention always increases by 1, but also depends on the problems (lines 222-225). Equation 2 is also wrong: taking the gradient of the expression on the right does not yield the REINFORCE estimator.
I do not believe these concerns prevent acceptance, but a more detailed response to the first point would improve the paper significantly.
Questions for authors
- This ICLR 2026 paper seems similar in idea (L2Seg): https://arxiv.org/pdf/2507.01037. It also retains tour segments and aggregates them into hypernodes. Please explain how your method is different compared to this one.
- Does not the LinkGraph construction require some effort to not lose information? E.g., CVRPTW seems quite more complex compared to the TSP due to its time windows. A comment on the difficulty of this construction in more general cases would be helpful.
9 comments
Author Response to Reviewer Yj3H (Page 2)
| TSP-100 | RF (Obj.) | RF (Drop$\downarrow$) | RF (Time$\downarrow$) | PRF (Obj.) | PRF (Drop$\downarrow$) | PRF (Time$\downarrow$) |
|---|---|---|---|---|---|---|
| 1 | 7.791 | 0.450% | 0.013s | 7.767 | 0.141% | 0.013s |
| 3 | 7.766 | 0.131% | 0.037s | 7.758 | 0.022% | 0.035s |
| 5 | 7.762 | 0.080% | 0.062s | 7.757 | 0.015% | 0.062s |
| 10 | 7.759 | 0.046% | 0.124s | 7.757 | 0.011% | 0.117s |
| CVRP-50 | RF (Obj.) | RF (Drop$\downarrow$) | RF (Time$\downarrow$) | PRF (Obj.) | PRF (Drop$\downarrow$) | PRF (Time$\downarrow$) |
|---|---|---|---|---|---|---|
| 1 | 10.598 | 2.209% | 0.026s | 10.513 | 1.394% | 0.026s |
| 3 | 10.456 | 0.860% | 0.203s | 10.441 | 0.710% | 0.197s |
| 5 | 10.430 | 0.606% | 0.382s | 10.428 | 0.591% | 0.378s |
| 10 | 10.418 | 0.495% | 0.814s | 10.416 | 0.472% | 0.804s |
| CVRPTW-50 | RF (Obj.) | RF (Drop$\downarrow$) | RF (Time$\downarrow$) | PRF (Obj.) | PRF (Drop$\downarrow$) | PRF (Time$\downarrow$) |
|---|---|---|---|---|---|---|
| 1 | 16.531 | 3.029% | 0.029s | 16.493 | 2.798% | 0.028s |
| 3 | 16.152 | 0.684% | 0.360s | 16.128 | 0.553% | 0.315s |
| 5 | 16.104 | 0.408% | 0.732s | 16.100 | 0.375% | 0.700s |
| 10 | 16.083 | 0.273% | 1.384s | 16.080 | 0.255% | 1.319s |
| TSP-2K | Random (Obj.) | Random (Drop$\downarrow$) | Random (Time$\downarrow$) | PRF (Obj.) | PRF (Drop$\downarrow$) | PRF (Time$\downarrow$) |
|---|---|---|---|---|---|---|
| 1 | 32.765 | 1.014% | 0.093s | 32.765 | 1.014% | 0.093s |
| 3 | 32.755 | 0.984% | 0.643s | 32.651 | 0.660% | 0.656s |
| 5 | 32.748 | 0.962% | 1.118s | 32.602 | 0.511% | 1.136s |
| 10 | 32.746 | 0.955% | 2.309s | 32.556 | 0.370% | 2.346s |
| 20 | 32.729 | 0.903% | 4.773s | 32.530 | 0.288% | 4.844s |
| CVRP-200 | Random (Obj.) | Random (Drop$\downarrow$) | Random (Time$\downarrow$) | PRF (Obj.) | PRF (Drop$\downarrow$) | PRF (Time$\downarrow$) |
|---|---|---|---|---|---|---|
| 1 | 20.099 | 2.402% | 0.052s | 20.099 | 2.402% | 0.052s |
| 3 | 20.020 | 1.980% | 0.441s | 19.868 | 1.221% | 0.447s |
| 5 | 19.951 | 1.630% | 0.759s | 19.852 | 1.133% | 0.770s |
| 10 | 19.891 | 1.316% | 1.735s | 19.795 | 0.843% | 1.761s |
| 20 | 19.855 | 1.140% | 3.426s | 19.766 | 0.692% | 3.477s |
| CVRPTW-200 | Random (Obj.) | Random (Drop$\downarrow$) | Random (Time$\downarrow$) | PRF (Obj.) | PRF (Drop$\downarrow$) | PRF (Time$\downarrow$) |
|---|---|---|---|---|---|---|
| 1 | 43.703 | 4.890% | 0.083s | 43.703 | 4.890% | 0.083s |
| 3 | 43.026 | 3.357% | 1.088s | 42.702 | 2.586% | 1.092s |
| 5 | 42.865 | 2.984% | 2.009s | 42.544 | 2.213% | 2.019s |
| 10 | 42.806 | 2.850% | 4.521s | 42.516 | 2.147% | 4.540s |
| 20 | 42.665 | 2.512% | 9.124s | 42.333 | 1.704% | 9.165s |
Author Response to Reviewer Yj3H (Page 3)
W2: Presentation Clarifications and Correction.
A-W2: Thank you for these careful comments. We clarify the two points below.
-
Retention count and residual size. Increasing the number of retained variables does not necessarily reduce the residual size at every step. For example, consider the TSP tour . Retaining the edge forms a fragment represented by its two endpoints, so the residual size remains unchanged. If is then retained, the fragment extends from to , allowing to be reduced and the residual size to decrease. Thus, the retained-variable count increases by one at each step, whereas the residual size is only non-increasing.
-
REINFORCE equation. Thank you for catching this error. The submitted version incorrectly presented the REINFORCE gradient estimator as the training objective. We have corrected Eq. 2 by defining and estimating its gradient with .
Q1: Comparison with L2Seg and Its Hypernode-Based Segment Retention.
A-Q1: Thank you for pointing us to L2Seg. Both L2Seg and RS contract retained incumbent segments into a smaller problem and expand the re-optimized result back. The key difference lies in the role of the learned models.
-
Role of the learned models. In L2Seg, the NAR and AR models are used only for prediction. They identify unstable edges to decide which segments are aggregated, while solving and re-optimizing the reduced problem still rely on an existing backbone solver such as LKH-3, LNS, or L2D. In COReformer, the learned models are themselves the solvers. PRF predicts a global heatmap that is decoded into global candidates and guides retention, and SymNCO constructs the solution of the residual LinkGraph under feasibility masks. RS therefore serves as the interface through which a global predictor and a local constructor solve the problem together.
-
Retention criterion and size control. L2Seg is trained by imitating a look-ahead backbone solver and predicts which edges this solver is likely to change, so the reduced size is determined implicitly by the predicted unstable edges. PRF is trained toward perturbed high-quality solutions and predicts which incumbent edges are worth retaining. Progressive reduction then takes the residual size as an explicit input, which bounds the decoding length of SymNCO and allows one heatmap to yield multiple LinkGraphs of different sizes.
Author Response to Reviewer Yj3H (Page 1)
Dear Reviewer Yj3H,
We appreciate your recognition of our work and the valuable suggestions you provided. Here are our responses to the questions you raised.
A-W1: Thank you for this suggestion. To test whether the neural components are necessary, the revision adds two end-to-end ablations inside the same search loop, together with a runtime-quality curve on TSP-2K. In both ablations, progressive reduction, SymNCO, local search, and the incumbent update stay fixed, so only the learned signal changes. The tables are given at the end of this response.
Vanilla RF versus PRF. Only the global predictor is replaced. Across TSP, CVRP, and CVRPTW, PRF reaches a smaller gap than vanilla RF at a closely matched runtime. The margin is already visible at IG=1 and remains as further iterations are allowed. The difference lies in the heatmap. PRF retains more reliable incumbent structure, and the residual neighborhood passed to SymNCO is more informative than the one induced by vanilla RF.
PRF-guided retention versus random retention. This comparison removes learned guidance from the retention step itself. Both settings start from the same PRF solution, so a weaker initialization cannot explain the later difference, and the two columns coincide at IG=1. From the next iteration on, one setting still retains edges according to the PRF heatmap, while the other retains incumbent edges uniformly at random. At nearly the same runtime, PRF-guided retention keeps closing the gap, whereas random retention improves more slowly and finishes at a larger gap on TSP-2K, CVRP-200, and CVRPTW-200. The heatmap favors higher-confidence incumbent structure and leaves a residual that the same constructor can still improve. Uniform retention treats those edges alike, so the residual it leaves is less useful.
Local search. The local search in Algorithm 2 is a light heuristic of the kind standard for these problems: 2-opt on TSP, and feasibility-preserving improvement on CVRP and CVRPTW. No heavier procedure, such as MCTS, is involved. The same operator is used on both sides of the ablations above, so the gaps between them come from the predictor and the retention rule.
Runtime-quality curve. An iterative method improves as its budget grows, which is why GLOP, UDC, LEHD, and SIL are each reported at two analogous operating points, fewer and more. Those two points summarize the trade-off. To show the trade-off across the budget, the revision samples several operating points on TSP-2K within about 30s and connects them into a line chart. The data and the figure are given in Appendix E, Table 11 and Figure 4.