- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes SUPL2I, a standalone preference-conditioned learning-to-improve (L2I) method for multi-objective combinatorial optimization problems (MOCOPs). Unlike existing L2I methods for MOCOPs \that learn components inside an external MOEA/local-search framework, SUPL2I is a single policy that refines complete solutions and serves all preferences and problem sizes. Its design addresses three questions: (1) objective-wise representation, one embedding stream per objective built from that objective's own node features, with a shared encoder, scoring local moves separately; (2) where to inject the preference, node positions remain preference-free, while the preference enters both node embeddings and the fusion; and (3) which candidates to explore, a nondominance-based transition accepting only dominating or incomparable candidates in training and inference. The paper also contributes SC-RoPE, a parameter-free positional encoding capturing the circular and (for multi-route) hierarchical structure of routing solutions, transferring across sizes. Validation covers Bi-/Tri-objective TSP and Bi-CVRP at n = 20/50/100, cross-size generalisation to 150/200, and TSPLIB benchmarks (KroAB100/150/200), against ~12 baselines (L2C, L2I, MOEAs, local search, and WS-LKH/WS-ORT).
Critical strengths
- A standalone, single-model L2I method that matches or beats both neural SOTA and a strong classical solver. SUPL2I refines complete solutions with one preference-conditioned policy across all preferences and problem sizes, without any external MOEA/local-search framework, and it delivers on this design: on Bi-/Tri-TSP and Bi-CVRP it attains the best hypervolume across sizes, and on MOTSP in-distribution it surpasses WS-LKH, a solver that optimises each weighted-sum subproblem near-optimally, while using less runtime. This matters because it shows that learned local search can replace the external search framework and even a near-optimal secularized classical solver, which is the payoff the paper claims.
- SC-RoPE: a parameter-free, size-transferable positional encoding. It encodes circularity, hierarchy, and size-alignment in a single rotary scheme derived from the current solution's positions, letting one model transfer to larger unseen sizes with no change in parameters, and its ablation shows it both speeds up training and improves final quality. Because it is parameter-free and position-defined, it applies directly to single-objective L2I and other cyclic/hierarchical tasks, a reusable contribution whose value extends beyond the MOCOP setting.
Critical weaknesses
- The central competitiveness claim rests on a self-referential metric, and one key comparison is asserted but not quantified. (a) The reported "Gap" is defined relative to the authors' own SUPL2I-Aug (T=5k) configuration , so that configuration is 0.00% by construction and serves as the reference for every other method. A gap against an absolute benchmark, a known or approximate Pareto front, would be far more convincing than a gap against one's own best configuration. As written it is also easy to misread, since baselines can have negative gaps (WS-LKH: −0.06%/−0.58% on Bi-TSP150/200, i.e., higher HV than SUPL2I-Aug). (b) The WS-LKH comparison is subtle but consequential: WS-LKH optimises each weighted-sum subproblem near-optimally, so SUPL2I attaining higher HV implies it recovers non-supported solutions that WS scalarization cannot express. This is a strong and interesting claim, but the paper asserts it without quantifying it; reporting, for example, the fraction of archived solutions that are non-supported (or that dominate the WS-only front) would substantiate the headline "beats LKH" result. Because the paper's main claim of superiority rides on these two points, they matters a lot.
- Limited technical novelty relative to DACT (Ma et al., 2021). Most of the learning machinery, the 2-opt MDP, the multi-head compatibility sub-layer, n-step PPO with a shared baseline, the curriculum warm-start, instance augmentation, and the C·tanh logit bound, is inherited from DACT/WRPN; the new components (objective-wise streams, the preference-injection point, the non-dominance transition, and SC-RoPE) are individually incremental, and their measured effects are small in absolute HV terms at the smaller sizes (on Bi-TSP20 the competitive methods cluster within ~0.4% HV). This bears on whether the paper clears the novelty bar and on how much of the gain is attributable to the new components versus the strong inherited base.
Questions for authors
- Why is the Gap defined relative to your own SUPL2I-Aug (T=5k)? Can you report a Gap against an absolute reference instead? And is the z_ref in Eq. (3) the same as the HV reference point in Table 4?
- On MOTSP, L2C baselines use 64 augmentations while SUPL2I-Aug uses only 8. Why not match them? Would giving SUPL2I 64 combinations change the conclusions, especially on Bi-TSP20 where the margin is only ~0.4%?
- Since WS-LKH solves each scalarised sub-problem near-optimally, your HV win implies you recover non-supported solutions it misses. Can you quantify this (e.g., the fraction of archived solutions that are non-supported)?
- On the runtime accounting, which numbers are on 4 GPUs and which on 1 GPU, and are the neural methods timed on the same footing as the CPU baselines (LKH, OR-Tools, MOEAs)? This matters because "less time" is one of the headline claims.
7 comments
Initial Responses to Reviewer XERf (Part 2/3)
W2: Technical novelty relative to DACT? Gain from the new components?
To our knowledge, SUPL2I is the first standalone L2I method for MOCOPs: a single policy performs the whole search, from random solutions to an approximation of the entire Pareto front. Developing a competitive method of this kind involves three major issues:
- Over long trajectories, a single policy needs to serve all preferences without drifting into unpromising regions of the search space.
- Preference conditioning needs to deal with positional information as well as node features.
- It is desirable that the positional encoding can capture the solution structure (e.g., circularity and hierarchy in routing) and, at the same time, transfer across problem sizes.
SUPL2I tackles these issues with three key components:
-
Nondominance-based acceptance: In MOCOPs, unlike in single-objective problems, a move can also lead to an incomparable solution. SUPL2I exploits this characteristic in both training and inference: it considers only superior and nondominated solutions, whereas existing multi-objective L2I methods [1-2] consider any solution.
-
Score-level fusion: A local move in MOCOPs can affect each objective differently. SUPL2I leaves the node positions free of the preference, and instead injects the preference into both the node embeddings and the fusion of per-objective scores.
-
SC-RoPE: Unlike existing positional encodings in single-objective and multi-objective L2I [1-4], SC-RoPE captures both the circularity and the hierarchy of routing solutions in a rotary form and keeps wavelengths comparable across sizes. It can also benefit existing single-objective L2I solvers. Please refer to our response to Reviewer e9FR (Q1) about the effectiveness of SC-RoPE on single-objective L2I.
Just like existing multi-objective L2C and L2I methods building upon single-objective NCO ones (POMO [5] and DACT [4]), the proposed SUPL2I builds upon the single-objective DACT. However, we use characteristics of MOCOPs (i.e., Pareto dominance and objective-specific features) to design a standalone multi-objective L2I method. To make this clearer, we have added what is inherited from DACT/WRPN in the revised manuscript and how our method differs from existing related techniques in Appendix I (see page 22).
Regarding the effectiveness of the proposed components, we compare SUPL2I with WRPN [1] on Bi-TSP. WRPN [1] directly conditions the single-objective DACT [4] on the preference by injecting a weight embedding into the node and positional embeddings, and leaves the rest of the network unchanged. As shown in Table D below, SUPL2I outperforms WRPN on all sizes, and its advantage becomes substantially larger on Bi-TSP150 and Bi-TSP200.
Table D: HV of WRPN and SUPL2I on Bi-TSP.
| Problem Size | WRPN | SUPL2I |
|---|---|---|
| Bi-TSP20 | 0.6285 | 0.6298 |
| Bi-TSP50 | 0.6399 | 0.6451 |
| Bi-TSP100 | 0.6978 | 0.7101 |
| Bi-TSP150 | 0.6622 | 0.7083 |
| Bi-TSP200 | 0.4517 | 0.7392 |
As for the small margin on Bi-TSP20 (as pointed out by the reviewer), we believe this is because the solutions obtained by SUPL2I are very close to the true Pareto front for this small-scale problem (leaving no/little room for improvement). This can be inferred from the facts that 1) the HV of SUPL2I's supported solutions equals that of WS-LKH (Table M in our response to W1(b)&Q3), and 2) SUPL2I with many more augmentations cannot improve its performance (see our response to Q2 about SUPL2I with 64 augmentations).
Initial Responses to Reviewer XERf (Part 3/3)
Q1 (Reference point): z_ref in Eq. (3) and its effect.
Very good question. Yes, z_ref in Eq. (3) is the same as the HV reference point in Table 4 (Table 5 in the revised manuscript). Your comment reminded us to examine how SUPL2I performs without this normalisation. We have now removed the need for z_ref in Eq. (3), i.e., replaced the equation with , and re-trained the MOCVRP model. As shown in Table N, without the normalisation, the HV is unchanged on Bi-CVRP20, and interestingly, higher on Bi-CVRP50 and Bi-CVRP100.
Table N: HV of SUPL2I without z_ref (Paper Results in Parentheses).
| Method | Bi-CVRP20 | Bi-CVRP50 | Bi-CVRP100 |
|---|---|---|---|
| SUPL2I (T=1k) | 0.4308 (0.4308) | 0.4107 (0.4101) | 0.4060 (0.4047) |
| SUPL2I (T=5k) | 0.4309 (0.4309) | 0.4113 (0.4110) | 0.4076 (0.4069) |
| SUPL2I-Aug (T=1k) | 0.4309 (0.4309) | 0.4114 (0.4112) | 0.4077 (0.4067) |
| SUPL2I-Aug (T=5k) | 0.4309 (0.4309) | 0.4116 (0.4115) | 0.4089 (0.4083) |
A possible reason for this occurrence is that the normalisation scales down the total distance much more than the makespan (by 80 vs. 4 on Bi-CVRP100), which makes most preferences focus on the makespan (although it is easy to optimise). Without the normalisation, more resources are allocated to the total distance, which yields shorter total distances and a higher HV.
For the MOTSP and MOKP, removing the normalisation is expected to have little effect, as the HV reference point has the same value for all objectives (see Table 5 in the revised manuscript), in which case the normalisation only rescales Eq. (3) by a constant. Due to the time constraint, we are unable to report their results here. We will update the paper when the results are ready. We thank the reviewer for raising this question, which helps improve our work.
Q2: Unmatched number of augmentations on MOTSP (8 vs. 64).
The L2C baselines use 64 augmentations whereas SUPL2I-Aug uses 8, which favours the L2C baselines. L2I methods usually use fewer augmentations than L2C methods [4], as each augmented instance requires a complete search and takes longer. Following the common practice in L2I [1], we used 8 for SUPL2I to compare the methods within a reasonable running time.
Following your suggestion, we ran SUPL2I with 64 augmentations on Bi-TSP20, and the HV is unchanged (0.6298). Furthermore, with the supported solutions only, the HV of SUPL2I without augmentation already equals that of WS-LKH (0.6270, see Table M in the response to W1(b) & Q3). These results may suggest that solutions obtained by the methods are very close to the true Pareto front on this small-scale problem, leaving little room for improvement.
Q4: Hardware settings of the reported running times (4 GPUs or 1 GPU)? Comparability between neural methods and CPU baselines?
In Tables 1-3 and 6 (200 instances per setting), the total running time of neural methods was reported for four GPUs; in Table 9 (one KroAB [6] benchmark instance per setting), it was for one GPU. For the classical solvers and the conventional methods, it was the total running time on a single CPU core.
We agree that the running times of different competitors are not comparable due to different hardware and parallelisation settings. We have thus removed the statements of "less time" in comparison with the CPU baselines (LKH, OR-Tools, MOEAs) throughout the paper (Abstract, Introduction, etc.).
[1] Solving multiobjective combinatorial optimization via learning to improve method, TETCI, 2025.
[2] Pareto Improver: Learning Improvement Heuristics for Multi-Objective Route Planning, T-ITS, 2024.
[3] Rethinking positional encoding for neural vehicle routing, arXiv:2605.11910, 2026.
[4] Learning to iteratively solve routing problems with dual-aspect collaborative transformer, in NeurIPS, 2021.
[5] POMO: Policy optimization with multiple optima for reinforcement learning, in NeurIPS, 2020.
[6] TSPLIB—A traveling salesman problem library, ORSA J. Comput., 1991.
Initial Responses to Reviewer XERf (Part 1/3)
Many thanks for your careful reading and valuable feedback on our paper. Below are our detailed responses to your comments, where W denotes Weakness (W1-W2) and Q denotes Question (Q1-Q4). All revisions to the original manuscript are marked in blue for your convenience.
W1(a) & Q1 (Gap): Gap against an absolute reference.
Valid point. Following your suggestion, we have now revised the manuscript to report the Gap relative to a classical solver on each problem: WS-LKH for MOTSP, WS-ORT for MOCVRP, and WS-DP (weighted-sum dynamic programming) for MOKP (we have tested another problem, the multi-objective knapsack, as suggested by Reviewer DMtk). The changes are marked in blue in the revised manuscript, including the Gap columns of the result tables, the definition of the Gap in Section 6.1, and the corresponding updates in Section 6.2.
W1(b) & Q3: Non-supported solutions missed by WS-LKH but found by SUPL2I.
Insightful comment - certainly helps us better understand the behaviour of the proposed method. We now report the percentage of non-supported solutions, and the HV of SUPL2I with and without them, below in Table M. As shown, 85%–95% of the solutions are non-supported. With the supported solutions only, the HV of SUPL2I equals that of WS-LKH on Bi-TSP20 and is lower on Bi-TSP50 and Bi-TSP100, meaning that SUPL2I can find many non-supported solutions that contribute substantially to the overall HV value.
In the manuscript, we have included Table M in Appendix G (page 21), and added the corresponding discussion in Section 6.2.
Table M: Non-supported Solutions of SUPL2I and HV on Bi-TSP.