acceptodds
Under review as a conference paper at ICLR 2027

Reduce-then-Solve: Iterative Search via Reduction for Combinatorial Optimization

23 views

Abstract

Neural combinatorial optimization (NCO) has emerged as a promising approach to combinatorial optimization problems (COPs). Existing Learning-to-Construct (L2C) methods have complementary limitations: global prediction (GP) provides scalable guidance but struggles with complex constraints, while local construction (LC) handles constraints well but incurs sequential solving overhead. We therefore propose Reduce-then-Solve (RS), a general framework that iteratively retains promising structures from an incumbent, reduces the COP to a residual subproblem, and re-solves it. For NCO, we instantiate RS as COReformer, a Learning-to-Search (L2S) method that couples GP and LC through problem reduction, with Perturbed Rectified Flow (PRF) as the global predictor and SymNCO as the local constructor. At each iteration, PRF identifies promising incumbent structures to induce a size-controllable LinkGraph, which SymNCO then solves to refine the incumbent. PRF adapts rectified flow to iterative search by transporting over perturbed-solution distributions rather than a single optimum. Extensive Experiments on TSP, CVRP, and CVRPTW show that COReformer achieves SOTA among learning-based solvers across prior L2C, L2S, and D&C comparisons. A learning-free RS instantiation on MCut further shows that the framework extends beyond neural routing.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Combinatorial Optimization, Rectified Flow, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Yj3HOpenReview ↗
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
AuthorsOpenReview ↗

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.


W1: Component Ablations.

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=1I_G=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=1I_G=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.

AuthorsOpenReview ↗

Author Response to Reviewer Yj3H (Page 2)

TSP-100 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
17.7910.450%0.013s7.7670.141%0.013s
37.7660.131%0.037s7.7580.022%0.035s
57.7620.080%0.062s7.7570.015%0.062s
107.7590.046%0.124s7.7570.011%0.117s
CVRP-50 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
110.5982.209%0.026s10.5131.394%0.026s
310.4560.860%0.203s10.4410.710%0.197s
510.4300.606%0.382s10.4280.591%0.378s
1010.4180.495%0.814s10.4160.472%0.804s
CVRPTW-50 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
116.5313.029%0.029s16.4932.798%0.028s
316.1520.684%0.360s16.1280.553%0.315s
516.1040.408%0.732s16.1000.375%0.700s
1016.0830.273%1.384s16.0800.255%1.319s
TSP-2K IGI_GRandom (Obj.↓\downarrow)Random (Drop$\downarrow$)Random (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
132.7651.014%0.093s32.7651.014%0.093s
332.7550.984%0.643s32.6510.660%0.656s
532.7480.962%1.118s32.6020.511%1.136s
1032.7460.955%2.309s32.5560.370%2.346s
2032.7290.903%4.773s32.5300.288%4.844s
CVRP-200 IGI_GRandom (Obj.↓\downarrow)Random (Drop$\downarrow$)Random (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
120.0992.402%0.052s20.0992.402%0.052s
320.0201.980%0.441s19.8681.221%0.447s
519.9511.630%0.759s19.8521.133%0.770s
1019.8911.316%1.735s19.7950.843%1.761s
2019.8551.140%3.426s19.7660.692%3.477s
CVRPTW-200 IGI_GRandom (Obj.↓\downarrow)Random (Drop$\downarrow$)Random (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
143.7034.890%0.083s43.7034.890%0.083s
343.0263.357%1.088s42.7022.586%1.092s
542.8652.984%2.009s42.5442.213%2.019s
1042.8062.850%4.521s42.5162.147%4.540s
2042.6652.512%9.124s42.3331.704%9.165s
AuthorsOpenReview ↗

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 v0−v1−v2−v3−v4−v5−v0v_0-v_1-v_2-v_3-v_4-v_5-v_0. Retaining the edge v2−v3v_2-v_3 forms a fragment represented by its two endpoints, so the residual size remains unchanged. If v3−v4v_3-v_4 is then retained, the fragment extends from v2v_2 to v4v_4, allowing v3v_3 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 LRL(θ)=−E[R]\mathcal{L}_{\mathrm{RL}}(\theta)=-\mathbb{E}[R] and estimating its gradient with −E[(R−b)∇θlog⁡πθ]-\mathbb{E}[(R-b)\nabla_\theta\log\pi_\theta].


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 ZZ as an explicit input, which bounds the decoding length of SymNCO and allows one heatmap to yield multiple LinkGraphs of different sizes.

Reviewer_6JWAOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a reduce-and-solve algorithm for combinatorial algorithm. In detail, it starts from a feasible solution, each time fix a part of it according to a heatmap from a flow matching model, then improves it use an auto-regressive model. The experiments demonstrate that the model achieves the SOTA performance on several problems at various scales.

Critical strengths
  1. Strong empirical performance. The empirical results are impressive. The proposed method achieves near-optimal solutions on several challenging, large-scale combinatorial optimization benchmarks, while maintaining competitive computational efficiency.

  2. Effective integration of global prediction and local construction. The combination of global prediction and local construction is an interesting design choice. Although the individual components build on existing methods, their integration through problem reduction offers some methodological novelty.

Critical weaknesses
  1. The difference between the proposed method and traditional Large Neighborhood Search (LNS) methods is over-stated. The proposed method is in essential still within the LNS framework (destroy + repair), and no LNS or neural LNS baselines are included in comparison. Leveraging traditional heuristics to enhance the performance of neural solvers itself does not lead to meaningful contribution.

  2. Weak motivation for perturbed Rectified Flow (PRF). I think PRF is just flow matching with a different design choice of the source and target distributions. I also do not understand the claim that leaving little crossing at intermediate states and preventing RF from learning a shared velocity field across diverse source-target pairs. I do not see any issue of RF here: if the model can perfectly fit the velocity field, then the generation would always land at the optimal solution. The failure to perfectly fit the objective does not mean the objective itself is problematic. The criticism from the paper clearly states the training objective of RF itself is not right.

Questions for authors
  1. How is your method compared to GenSCO? I think this is an important baseline and the algorithm side there is substantial overlap.

Li et al. Generation as search operator for test-time scaling of diffusion-based combinatorial optimization. NeurIPS 2025.

  1. The paper chooses Rectified Flow (RF) as the training method and later claims When RF is applied to COPs, each instance is associated with a single target solution, reducing the target distribution to one isolated sample. But in the original flow matching, setting the target distribution to be a perturbed distribution around the data sample is a standard practice. The source distribution could also be any distribution (not just random feasible solutions). So it seems like the authors choose a simplified setup and later claim it to be too simple and state they re-invent the original training method. Could you elaborate more about the difference between your perturbed RF with the general flow matching framework?
11 comments
AuthorsOpenReview ↗

Author Response to Reviewer 6JWA (Page 1)

Dear Reviewer 6JWA,

Thank you for your careful review and valuable advice! Here are our responses to the questions you raised.


W1: Positioning Relative to LNS, and the Contribution of Residual Contraction.

A-W1: Thank you for raising this important positioning issue. We agree that RS shares the retain-and-reoptimize principle with LNS and belongs to the broader LNS family. We will revise the paper to state this relationship more carefully. Building on this shared principle, RS turns retained structures into an explicit, size-controllable residual COP. This residual problem provides an interface between complementary solver paradigms and reduces the need for problem-specific neighborhood engineering.

  • Explicit residual contraction and size control. LNS commonly keeps the original problem and defines a neighborhood by fixing or releasing a subset of decisions. RS further contracts each retained fragment into a macro-structure and forms a residual COP, whose decision variables are the unresolved connections among fragments. It also controls the actual residual size z(G,S,y)z(G,S,\mathbf{y}) toward a target ZZ, so the number of retained or released decisions is not used as a proxy for the resulting problem size. For an autoregressive solver such as SymNCO, the decoding length then follows ZZ rather than the original instance size NN.

  • An interface for mature NCO paradigms. Generative global prediction and RL-based construction are two active directions in NCO, represented respectively by DIFUSCO [1], Fast-T2T [2], and GenSCO [3], and by the RL4CO [4] ecosystem. The residual COP connects the two: PRF supplies global retention guidance, and SymNCO performs constraint-aware construction on the reduced problem. Since both directions already provide modeling and training recipes for routing problems, applying RS to a new problem mainly requires adapting the problem features and the residual representation. The LinkGraph must still preserve the relevant constraints, so some problem-specific design remains, while a complete set of destroy and repair operators no longer needs to be designed for every problem.

  • Comparison with classical ALNS. We agree that this discussion should be supported by an LNS baseline. We therefore use the open-source ALNS package [5] and follow its official documentation. The TSP example uses random, path, and worst removal with greedy repair, and the CVRP example uses string removal with greedy repair. Both settings are evaluated under the same fewer and more budgets as COReformer. The results are summarized below.

AuthorsOpenReview ↗

Author Response to Reviewer 6JWA (Page 2)

TSP-500ALNS (Obj.↓\downarrow)ALNS (Drop$\downarrow$)ALNS (Time$\downarrow$)COReformer (Obj.↓\downarrow)COReformer (Drop$\downarrow$)COReformer (Time$\downarrow$)
fewer18.1169.491%0.202s16.5630.102%0.133s
more17.9538.507%0.502s16.5540.050%0.483s
TSP-1KALNS (Obj.↓\downarrow)ALNS (Drop$\downarrow$)ALNS (Time$\downarrow$)COReformer (Obj.↓\downarrow)COReformer (Drop$\downarrow$)COReformer (Time$\downarrow$)
fewer25.57710.636%1.005s23.1630.195%0.513s
more25.45910.125%2.005s23.1450.114%1.859s
TSP-2KALNS (Obj.↓\downarrow)ALNS (Drop$\downarrow$)ALNS (Time$\downarrow$)COReformer (Obj.↓\downarrow)COReformer (Drop$\downarrow$)COReformer (Time$\downarrow$)
fewer36.37512.145%2.013s32.6020.511%1.136s
more36.15111.453%5.014s32.5300.288%4.844s
CVRP-200ALNS (Obj.↓\downarrow)ALNS (Drop$\downarrow$)ALNS (Time$\downarrow$)COReformer (Obj.↓\downarrow)COReformer (Drop$\downarrow$)COReformer (Time$\downarrow$)
fewer22.86616.511%1.003s19.8521.133%0.770s
more21.61610.011%5.003s19.7660.692%3.477s
CVRP-500ALNS (Obj.↓\downarrow)ALNS (Drop$\downarrow$)ALNS (Time$\downarrow$)COReformer (Obj.↓\downarrow)COReformer (Drop$\downarrow$)COReformer (Time$\downarrow$)
fewer44.43619.761%5.011s37.8391.848%2.332s
more44.38619.614%10.011s37.6271.267%10.239s
CVRP-1KALNS (Obj.↓\downarrow)ALNS (Drop$\downarrow$)ALNS (Time$\downarrow$)COReformer (Obj.↓\downarrow)COReformer (Drop$\downarrow$)COReformer (Time$\downarrow$)
fewer51.30324.837%5.060s43.0754.629%2.095s
more51.29224.809%10.071s42.5773.426%8.416s
AuthorsOpenReview ↗

Author Response to Reviewer 6JWA (Page 3)

W2&Q2: Motivation for PRF and Its Relation to General Flow Matching.

A-W2&Q2: Thank you for this question. We do not regard RF itself as problematic. It was developed mainly for image generation, where samples are continuous and the target is usually a distribution. A COP solution in this paper is binary, and the optimum of an instance may be close to an isolated point, so the same setup can be less suitable for the following reasons. PRF keeps the RF interpolation and perturbs the source and target with these reasons in mind.

  • Possible information leakage. When many trajectories share one binary optimum, an intermediate state may already make the endpoint easier to infer. The learned field can then depend partly on this information.

  • Error accumulation during multi-step integration. If the predicted velocity were exact, a direct RF trajectory could follow its target without accumulating error. In practice, the prediction is imperfect, so multi-step integration needs to account for this error. A perturbed target leaves later steps some room to adjust an earlier mistake. Under a direct RF path, the predicted velocity tends to stay close to the velocities from earlier steps as τ\tau approaches 1, so an earlier error can carry into the subsequent steps.

  • Alignment with iterative search. Later iterations usually start from high-quality yet suboptimal incumbents, whereas a direct RF source is drawn from random feasible solutions. Mixing random feasible solutions with perturbed near-optimal solutions brings the PRF source closer to the states encountered during search.

  • Comparison between vanilla RF and PRF. These differences are expected to appear in the predicted heatmap and then in the structures retained for residual solving. We therefore keep progressive reduction, SymNCO, local search, and the incumbent update unchanged, and vary only the global predictor. The heatmap comparison is reported in Figure 2 of the paper, and the corresponding end-to-end results are given below. PRF tends to reach a better solution at a similar runtime.

TSP-100 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
17.7910.450%0.013s7.7670.141%0.013s
37.7660.131%0.037s7.7580.022%0.035s
57.7620.080%0.062s7.7570.015%0.062s
107.7590.046%0.124s7.7570.011%0.117s
CVRP-50 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
110.5982.209%0.026s10.5131.394%0.026s
310.4560.860%0.203s10.4410.710%0.197s
510.4300.606%0.382s10.4280.591%0.378s
1010.4180.495%0.814s10.4160.472%0.804s
CVRPTW-50 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
116.5313.029%0.029s16.4932.798%0.028s
316.1520.684%0.360s16.1280.553%0.315s
516.1040.408%0.732s16.1000.375%0.700s
1016.0830.273%1.384s16.0800.255%1.319s
Reviewer_ybpTOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Reduce-then-Solve, an iterative optimization framework that retains selected parts of an incumbent solution, contracts them into a smaller residual problem, and reconstructs a candidate solution. Its neural routing instantiation, COReformer, combines a perturbed rectified-flow predictor with a SymNCO constructor operating on LinkGraphs. PRF uses perturbed feasible solutions as training sources and targets to improve its usefulness during incumbent-based search. Evaluation covers TSP up to 10,000 nodes, CVRP up to 2,000 customers, CVRPTW, distribution shifts, and TSPLIB/CVRPLIB instances. A learning-free Max-Cut instantiation illustrates applicability beyond neural routing.

Critical strengths
  1. The reported quality/runtime trade-offs are substantial across several routing tasks. For example, on TSP-1K, COReformer (more) reports a 0.11% gap in 1.86 seconds, compared with SIL (PRC, more) at 0.92% in 57.43 seconds (Table 1). On CVRP-500, the corresponding gaps/times are 1.27%/10.24 seconds and 2.85%/49.37 seconds for LEHD (RRC, more) (Table 3). Together with the shared-hardware evaluation and additional batched results, these results provide a meaningful empirical reason.

  2. The residual representation offers a useful way to combine global guidance with constraint-aware construction. LinkGraphs preserve incumbent fragments while allowing a constructor to reorganize their connections at a controlled problem size. The extension from TSP to capacity and time-window constraints is consequential: it demonstrates that the design addresses a limitation of heatmap-only construction. The Max-Cut result provides additional, although narrower, evidence that residual re-optimization can be useful outside routing.

Critical weaknesses
  1. The framework's novelty over LNS is insufficiently established. Retaining incumbent decisions and re-optimizing the remainder is standard in LNS and fix-and-optimize. Section 2 does not clearly establish what LinkGraph contraction adds beyond a compact representation of this existing search pattern.

  2. The ablations do not establish which components drive the gains. Figure 2 measures heatmap scores rather than final solution quality, while Table 7 only varies search budgets. Matched-runtime comparisons with random retention and vanilla RF in the same search loop are missing.

Questions for authors
  1. At matched runtime on one constrained routing task, how does COReformer compare with random retention and with vanilla RF, keeping the constructor and local search fixed?

  2. Beyond representation size, what distinguishes the LinkGraph search neighborhood or reconstruction procedure from LNS with a comparable repair budget?

  3. What are the exact PRF loss and inference update? Please clarify why the induced velocity is fθ(Sτ,τ,G)−S0f_\theta(S_\tau,\tau,G)-S_0, rather than (fθ(Sτ,τ,G)−Sτ)/(1−τ)(f_\theta(S_\tau,\tau,G)-S_\tau)/(1-\tau), and whether the original source is an additional conditioning variable.

8 comments
AuthorsOpenReview ↗

Author Response to Reviewer ybpT (Page 1)

Dear Reviewer ybpT,

We appreciate your recognition of our work and the valuable suggestions you provided. Here are our responses to the questions you raised.


W1&Q2: Novelty Relative to LNS and the LinkGraph Reconstruction Interface.

A-W1&Q2: Thank you for pointing out this important connection. RS shares the retain-and-reoptimize principle with LNS and fix-and-optimize: both start from an incumbent solution, preserve part of its structure, and re-optimize the remaining decisions. We therefore view RS as closely related to the broader LNS family, rather than as an unrelated search principle. Building on this shared principle, RS further formulates retention as an explicit and size-controllable problem reduction, and uses the resulting residual COP as an interface between complementary solver paradigms. Beyond representation size, this leads to two further aspects of the residual neighborhood and reconstruction procedure.

  • Explicit residual contraction and size control. Standard LNS typically destroys a subset of decisions and repairs the remaining free variables on the original problem. In contrast, RS contracts each retained fragment into a macro-structure and forms a residual COP whose decision variables correspond to unresolved connections among fragments. The local constructor therefore searches over a reduced residual instance, rather than over the original node set with some variables merely marked as fixed. RS further controls the residual size z(G,S,y)z(G,S,\mathbf{y}) toward a target ZZ. The number of retained variables alone may not determine this residual size, since retained decisions with the same cardinality can form structures with different connectivity. For autoregressive solvers such as SymNCO, setting the residual size to ZZ makes the decoding length scale with ZZ rather than with the original problem size NN. When Z≪NZ \ll N, this substantially reduces the sequential construction overhead and keeps the residual solving budget manageable for large instances.

  • An interface for complementary solvers. By making residual contraction and the target residual scale explicit, RS provides a modular interface between retention scoring and residual solving. In COReformer, PRF provides scalable global guidance, LinkGraph reduces the problem to a residual COP, and SymNCO performs constraint-aware construction on that residual. This division of labor allows each component to specialize in what it does best.

AuthorsOpenReview ↗

Author Response to Reviewer ybpT (Page 2)

W2&Q1: Missing Component Ablations with Random Retention and Vanilla RF.

A-W2&Q1: Thank you for this valuable suggestion. We agree that global guidance should be assessed not only by predictor quality, but also by its effect on complete search. Below, we first clarify why Figure 2 reports ACC, and then present two complementary end-to-end ablations with the downstream search components fixed.

  • Why Figure 2 uses heatmap accuracy (ACC). Figure 2 isolates the quality of the predicted heatmap itself. ACC evaluates how well the heatmap recovers the ground-truth solution structure without introducing the effects of decoding and local search. Decoding turns a continuous heatmap into a discrete feasible solution, and local search can further correct suboptimal decisions, which often reduces the observable gap between predictors. ACC therefore provides a direct comparison of the intrinsic prediction quality of RF and PRF. To further examine whether this advantage transfers to final solution quality, we conduct the following complete-search ablations.

  • Comparison between vanilla RF and PRF. We keep progressive reduction, SymNCO, local search, and the incumbent-update rule unchanged, and vary only the global predictor gθg_\theta. The results are reported below. Across all three tasks and matched runtimes, PRF consistently improves final solution quality over vanilla RF. We attribute this gain to the higher-quality heatmaps produced by PRF, which retain more reliable incumbent structures for residual reconstruction. PRF yields better heatmaps because its multi-step flow restores trajectory crossing via perturbed source-target pairs and avoids the RF collapse in which the endpoint becomes readily inferable at intermediate states, especially at low τ\tau, and because its mixed source aligns the training distribution with the high-quality yet suboptimal incumbents encountered during iterative search.

  • Comparison between random retention and PRF-guided retention. Fully random initialization tends to produce a weaker initial incumbent and would confound initialization quality with retention quality. We therefore initialize both settings with the same PRF-generated solution. In later RS iterations, one setting replaces PRF-guided retention with random retention, while the other continues to use the PRF heatmap; all remaining components are kept unchanged. The two settings thus coincide at IG=1I_G=1, and later iterations mainly isolate the effect of retention guidance. Random retention does not distinguish which incumbent decisions are more informative, whereas PRF-guided retention tends to keep higher-confidence structures and provide more useful residual neighborhoods for SymNCO and local search. The results below are consistent with this view.

AuthorsOpenReview ↗

Author Response to Reviewer ybpT (Page 3)

TSP-100 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
17.7910.450%0.013s7.7670.141%0.013s
37.7660.131%0.037s7.7580.022%0.035s
57.7620.080%0.062s7.7570.015%0.062s
107.7590.046%0.124s7.7570.011%0.117s
CVRP-50 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
110.5982.209%0.026s10.5131.394%0.026s
310.4560.860%0.203s10.4410.710%0.197s
510.4300.606%0.382s10.4280.591%0.378s
1010.4180.495%0.814s10.4160.472%0.804s
CVRPTW-50 IGI_GRF (Obj.↓\downarrow)RF (Drop$\downarrow$)RF (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
116.5313.029%0.029s16.4932.798%0.028s
316.1520.684%0.360s16.1280.553%0.315s
516.1040.408%0.732s16.1000.375%0.700s
1016.0830.273%1.384s16.0800.255%1.319s
TSP-2K IGI_GRandom (Obj.↓\downarrow)Random (Drop$\downarrow$)Random (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
132.7651.014%0.093s32.7651.014%0.093s
332.7550.984%0.643s32.6510.660%0.656s
532.7480.962%1.118s32.6020.511%1.136s
1032.7460.955%2.309s32.5560.370%2.346s
2032.7290.903%4.773s32.5300.288%4.844s
CVRP-200 IGI_GRandom (Obj.↓\downarrow)Random (Drop$\downarrow$)Random (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
120.0992.402%0.052s20.0992.402%0.052s
320.0201.980%0.441s19.8681.221%0.447s
519.9511.630%0.759s19.8521.133%0.770s
1019.8911.316%1.735s19.7950.843%1.761s
2019.8551.140%3.426s19.7660.692%3.477s
CVRPTW-200 IGI_GRandom (Obj.↓\downarrow)Random (Drop$\downarrow$)Random (Time$\downarrow$)PRF (Obj.↓\downarrow)PRF (Drop$\downarrow$)PRF (Time$\downarrow$)
143.7034.890%0.083s43.7034.890%0.083s
343.0263.357%1.088s42.7022.586%1.092s
542.8652.984%2.009s42.5442.213%2.019s
1042.8062.850%4.521s42.5162.147%4.540s
2042.6652.512%9.124s42.3331.704%9.165s

Comments on the paper

5 comments

Dear Reviewers,

The authors have posted their responses. Please take a look and respond to the authors.

Best, AC

Dear Reviewers,

The authors have posted their responses. Please take a look and respond to the authors.

Best, AC

AuthorsOpenReview ↗

Summary of Rebuttal (Page 1)

Dear Area Chair n3Sp,

We sincerely appreciate the reviewers' thoughtful and constructive feedback, as well as the Area Chair's careful oversight of the discussion. The reviewers consistently recognize the strong experimental performance of our method and the effectiveness of the residual representation in integrating global guidance with constraint-aware construction. In the following, we summarize the main concerns raised by the reviewers during the rebuttal discussion.


1. Positioning relative to LNS

Reviewer traceability: Reviewer ybpT (W1, Q2); Reviewer 6JWA (W1)

Summary: We have clarified that RS belongs to the broader LNS family, sharing the retain-and-reoptimize principle with LNS and fix-and-optimize.

  • Residual construction. Each retained fragment is contracted into a macro-structure, and the unresolved connections among fragments form a residual COP. Its size is controlled toward a target ZZ, which a local constructor such as SymNCO then decodes.

  • Solver interface. RS provides an effective interface between the two mainstream solver paradigms in NCO: generative models and RL-based construction (RL4CO). By formulating a size-controllable residual problem, RS allows PRF to leverage its strength in global retention guidance, while SymNCO exploits its strength in sequential, constraint-aware solution construction. This division of roles enables the two paradigms to complement each other, with each focusing on what it does best.

  • ALNS comparison. We have additionally included comparisons with classical ALNS baselines. The results show that COReformer achieves substantially smaller optimality gaps while maintaining comparable runtime (Table 10, Appendix E).


2. Additional ablation studies

Reviewer traceability: Reviewer ybpT (W2, Q1, Q3); Reviewer 6JWA (W2, Q2); Reviewer Yj3H (W1 and the follow-up on local search)

Summary: During the rebuttal, we added the following ablation studies to further validate the effectiveness of individual components.

  • Ablation Study on PRF. Figure 2 evaluates heatmap accuracy to isolate the prediction quality and eliminate the influence of decoding and local search on the comparison. PRF consistently achieves higher heatmap accuracy than vanilla RF throughout training. We also provide a complementary comparison using the complete search pipeline, where only the global predictor is replaced. PRF achieves a smaller optimality gap than vanilla RF at a closely matched runtime (upper block of Table 8, Appendix E).

  • Ablation Study on PRF-Guided Retention. To investigate whether the learned heatmap provides effective guidance for retention, both settings start from the same PRF initialization, with only the retention strategy changed in subsequent iterations. PRF-guided retention achieves a smaller optimality gap than uniform random retention at a similar runtime (lower block of Table 8, Appendix E).

  • Ablation Study on vθ\mathbf{v}_\theta. We compare vθ=S^1−S0\mathbf{v}_\theta=\hat{S}_1-S_0 with the remaining-displacement form vθ′(Sτ,τ,G)=(S^1−Sτ)/(1−τ)\mathbf{v}'_\theta(S_\tau,\tau,G)=(\hat{S}_1-S_\tau)/(1-\tau). The two definitions coincide when the predicted target remains unchanged and SτS_\tau follows the corresponding linear interpolation, as (S^1−Sτ)/(1−τ)=S^1−S0(\hat{S}_1-S_\tau)/(1-\tau)=\hat{S}_1-S_0. Both yield similar solution quality and runtime on TSP, CVRP, and CVRPTW. We adopt vθ\mathbf{v}_\theta by default for its slightly better overall performance and direct alignment with the RF objective (Table 9, Appendix E).

  • Ablation Study on Local Search. To isolate the contribution of LocalSearch(⋅)\mathrm{LocalSearch}(\cdot), we remove it under both the fewer and more budgets while keeping the remaining solver unchanged. The results show that local search effectively improves solution quality, albeit at the cost of additional runtime (Table 13, Appendix E).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.