acceptodds
Under review as a conference paper at ICLR 2027

SUPL2I: Standalone Learning to Improve for Multi-Objective Combinatorial Optimisation

Abstract

Neural methods have shown strong performance on single-objective combinatorial optimisation problems (SOCOPs), through both learning to construct solutions from scratch (L2C) and learning to improve complete solutions with local moves (L2I). However, existing neural methods for multi-objective combinatorial optimisation problems (MOCOPs) are predominantly based on the L2C paradigm. The few existing L2I methods for MOCOPs are integrated into external search frameworks (e.g., an MOEA or local search). When designing a standalone L2I method for MOCOPs, there are several issues worth exploring: 1) different objectives may relate to different features (e.g., node coordinates or costs in multi-objective TSP), so a single representation of all these features may not reflect the effect of local moves on each objective separately; 2) unlike L2C, L2I additionally needs to consider node positions, so where to inject the preference is non-trivial; 3) in SOCOPs, a local move typically makes a solution either better or worse, whereas in MOCOPs, a local move can lead to an incomparable solution (i.e., one that is nondominated to the original solution). In this paper, we look at these three issues and propose a standalone preference-conditioned L2I method unified across problem sizes. Specifically, the proposed method 1) builds one representation per objective from its related node features, with a shared encoder, and scores local moves under each objective separately; 2) keeps node positions preference-free while injecting the preference into both the node embeddings and the fusion of the per-objective scores; and 3) considers the nondominance relation (i.e., only accepting superior and incomparable solutions) in training and inference. Moreover, we introduce a positional encoding that captures the cyclic and hierarchical structure of routing solutions and transfers across problem sizes. Experiments show that our method substantially outperforms state-of-the-art neural and conventional methods in both in-distribution and cross-size generalisation settings. Notably, in the in-distribution setting, it even outperforms the strong classical solver LKH with weighted-sum scalarisation while requiring less time.

Primary area:
reinforcement learning
Keywords:
neural multi-objective combinatorial optimisation, learning to optimise, deep reinforcement learning, positional encoding

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_XERfOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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?
  2. 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%?
  3. 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)?
  4. 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
AuthorsOpenReview ↗

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.

ProblemNon-supportedWS-LKHSUPL2I (supported only)SUPL2I (all)
Bi-TSP2084.9%0.62700.62700.6298
Bi-TSP5093.5%0.64150.64120.6451
Bi-TSP10095.4%0.70900.70550.7101
AuthorsOpenReview ↗

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:

  1. Over long trajectories, a single policy needs to serve all preferences without drifting into unpromising regions of the search space.
  2. Preference conditioning needs to deal with positional information as well as node features.
  3. 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 SizeWRPNSUPL2I
Bi-TSP200.62850.6298
Bi-TSP500.63990.6451
Bi-TSP1000.69780.7101
Bi-TSP1500.66220.7083
Bi-TSP2000.45170.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).

AuthorsOpenReview ↗

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 gλ(f(x))=max⁡1≤i≤mλifi(x)+ρ∑i=1mλifi(x)g_\lambda(f(x)) = \max_{1\le i\le m} \lambda_i f_i(x) + \rho \sum_{i=1}^{m} \lambda_i f_i(x), 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).

MethodBi-CVRP20Bi-CVRP50Bi-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.

Reviewer_DMtkOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper propose a learning-to-improve method (SUPL2I ) for multi-objective combinatorial optimisation problems. it mainly consists of three components: an objective-wise representation with preference conditioning at both the encoder and score-fusion stages, a size-aligned cyclic rotary positional encoding to capture the circular and hierarchical structures of routing solutions, and a nondominance-based acceptance rule which allows moves to incomparable or superior solutions. The method is evaluated on multi-objective TSPs and multi-objective CVRPs, and compared with neural constructive methods, existing L2I methods, multi-objective evolutionary algorithms, local search methods, and classical solvers. Experimental results show that SUPL2I achieves competitive or even better hypervolume performance in most tested settings, and it can also generalise to larger TSP instances. Ablation studies are further conducted to verify the contributions of the representation, preference conditioning, positional encoding, and acceptance rule.

Critical strengths
  1. SUPL2I provides a standalone L2I method for multi-objective combinatorial optimisation, which does not rely on external search frameworks.
  2. Experimental results on MOTSP and MOCVRP demonstrate promising performance.
  3. Ablation studies are conducted to verify the effectiveness of the proposed components.
Critical weaknesses
  1. The experiments are only conducted on MOTSP and MOCVRP, so the effectiveness of SUPL2I on other MOCOPs is still unclear.

  2. The generalisation of SUPL2I to larger MOCVRP instances needs further validation.

  3. Compared with learning-to-construct methods, SUPL2I requires more inference time, which may limit its efficiency in practical use.

  4. The ablation of the acceptance rule is only performed on Bi-TSP100, so its effectiveness under other problem settings remains to be verified.

  5. The advantages of SC-RoPE on problems other than the evaluated routing problems are not demonstrated.

  6. Infeasible MOCVRP solutions are handled with penalty terms, but the sensitivity of the results to the penalty settings is unclear.

  7. The robustness of the proposed method under different preference distributions needs further investigation.

Questions for authors
  1. Can the authors evaluate SUPL2I on other types of MOCOPs to verify its broader applicability?

  2. How does SUPL2I perform when applied to MOCVRP instances larger than the training sizes?

  3. How large is the inference-time gap between SUPL2I and learning-to-construct methods under the same experimental settings?

  4. Can the authors report the memory usage as the number of objectives increases, and discuss the practical scalability of the method?

  5. Were SUPL2I and classical solvers tested under the same hardware and parallelisation conditions? Could the authors clarify these details?

  6. Does the nondominance-based acceptance rule still show its advantage on other problem instances and problem families?

  7. Can the authors provide evidence that SC-RoPE is also effective on tasks other than the routing problems evaluated in this paper?

  8. How sensitive is the performance on MOCVRP to the penalty settings for infeasible solutions?

  9. How robust is SUPL2I when the distribution of preference vectors changes during training and evaluation?

5 comments
AuthorsOpenReview ↗

Initial Responses to Reviewer DMtk (Part 1/3)

We appreciate your careful reading and insightful comments. Below are our detailed responses to your comments, where W denotes Weakness (W1–W7) and Q denotes Question (Q1–Q9). All revisions to the original manuscript are marked in blue for your convenience.

W1 & Q1: Effectiveness on other MOCOPs?

SUPL2I is expected to work on other MOCOPs, since the proposed components are generic and use general knowledge of MOCOPs (e.g., the Pareto dominance relation and objective-specific features), except for the component SC-RoPE, which is specifically designed for routing problems.

To confirm this and address your comment, we have now added another problem commonly used in multi-objective NCO [1-2], the multi-objective knapsack problem [3], to the paper (the full results are reported in Table 3 and discussed in Section 6.2).

For your convenience, Table E below summarises the Bi-KP results. As shown, SUPL2I consistently outperforms the baselines on all three sizes.

Table E: HV on Bi-KP Instances.

Problem SizeWS-DPNSGA-IIEMNHWE-CASUPL2I
Bi-KP500.35840.35920.35870.35820.3593
Bi-KP1000.44400.44320.44450.44400.4458
Bi-KP2000.35580.35060.35600.35580.3571

W2 & Q2: Generalisation to larger MOCVRP instances?

As SC-RoPE encodes relative positions with a consistent local resolution across problem sizes, the proposed L2I method is expected to generalise well to larger MOCVRP instances.

To verify this, we have now added experiments on larger Bi-CVRP with 150/200 nodes (each with 200 randomly generated instances). As shown in Table F below, SUPL2I consistently outperforms WE-CA on Bi-CVRP150 and Bi-CVRP200.

We revised the paper to incorporate the above results and discussion in Appendix F.1 (page 20).

Table F: HV on Larger Bi-CVRP.

Problem SizeWE-CAWE-CA-AugSUPL2ISUPL2I-Aug
Bi-CVRP1500.41960.42080.42030.4215
Bi-CVRP2000.42670.42820.42720.4283

It is worth noting that L2I methods (as well as multi-objective NCO methods) usually evaluate generalisation on problems with up to 200 nodes [2, 4]. This contrasts with L2C in the single-objective case, where substantially larger problems (e.g., 10,000 nodes or more) are considered (through dedicated designs such as divide-and-conquer [5]).

W3 & Q3: Inference time gap between SUPL2I and L2C methods.

Good point. L2I methods usually take significantly longer inference time than L2C methods. For example, on the single-objective TSP100, DACT (T=5k) [4] requires 1.5h, whereas POMO [6] needs 12s (Table 1 of the DACT paper [4]). Likewise, SUPL2I requires significantly longer inference time than multi-objective L2C methods. For example, on Bi-TSP100, SUPL2I (T=5k) takes 1.2h while multi-objective L2C methods take about 6s (both on a single GPU).

In the revised paper, we have made this limitation of L2I methods clearer (Section 7).

Q4: Memory usage and practical scalability with more objectives.

SUPL2I keeps one embedding stream per objective, and all streams share one encoder. As the number of objectives increases, the model architecture does not need to change. As each additional objective adds one embedding stream, the memory is expected to grow linearly with the number of objectives.

To confirm this, we have now reported the memory usage and model size with 2-5 objectives in Table G. As shown, with growing numbers of objectives, the model size barely changes. Each additional objective adds about 4 GB of GPU memory in training on 100-node instances.

Table G: Model Size and Memory Usage of SUPL2I with Different Numbers of Objectives.

#Obj.ParametersGPU Usage (100 nodes)
20.299M20.9 GB
30.299M24.9 GB
40.300M29.0 GB
50.300M33.1 GB

Q5: Hardware and parallelisation settings of SUPL2I and classical solvers.

Very good point. SUPL2I and other neural methods were run on four GPUs in parallel, while classical solvers were run on a single CPU core. Their running times are not comparable due to different hardware and parallelisation settings. We have now removed the statements of "less time" in comparison with classical solvers throughout the manuscript (Abstract, Introduction, etc.).

AuthorsOpenReview ↗

Initial Responses to Reviewer DMtk (Part 2/3)

W4 & Q6: Ablation of the nondominance-based acceptance rule beyond the Bi-TSP100 validation.

We now report the ablation results of the acceptance rule on other problems and sizes. Table H below summarises the results on Bi-TSP50 and Bi-CVRP50/100. As shown, nondominance-based acceptance shows an advantage over the Always-accept rule, which is commonly used in L2I [4, 7-9]. Notably, on Bi-CVRP50/100, the Always-accept rule is unstable during training.

Table H: HV of Different Acceptance Rules at Each Epoch.

ProblemAcceptance ruleEpoch 1Epoch 50Epoch 100Epoch 150Epoch 200
Bi-TSP50Always-accept0.55160.62460.63020.63120.6317
Bi-TSP50Nondominance-based0.57790.62190.63270.63350.6337
Bi-CVRP50Always-accept0.22910.37610.35440.34360.3606
Bi-CVRP50Nondominance-based0.37850.40210.40350.40400.4041
Bi-CVRP100Always-accept0.06410.29770.16650.14950.1641
Bi-CVRP100Nondominance-based0.29880.36020.36550.36640.3668

These results, together with the discussion, are now included in Appendix J (page 24) of the revised manuscript.

W5 & Q7: SC-RoPE beyond the evaluated routing problems?

Since SC-RoPE encodes relative positions with a consistent local resolution, it is expected to work well on other routing problems (independent of the number of objectives). To confirm this, it would be ideal to compare SC-RoPE with existing positional encodings on other multi-objective routing problems. However, existing multi-objective L2I methods primarily address MOTSP and MOCVRP [8-9], and extending them to other multi-objective routing problems would take considerable time. Given the time constraint in the rebuttal period, we evaluated SC-RoPE on another routing problem using an existing single-objective L2I solver, whose code and pretrained models are publicly available.

Specifically, we considered the pickup and delivery travelling salesman problem (PDTSP) [10], in which each pickup node is paired with a delivery node and must be visited before it, a precedence constraint absent from TSP and CVRP. We took N2S [11], a representative single-objective L2I solver for PDTSP, replaced its cyclic positional encoding with SC-RoPE, and re-trained it with all other settings unchanged. The results are reported below in Table I. As shown, SC-RoPE outperforms the original cyclic positional encoding of N2S on instances with different sizes.

Table I: Gap with SC-RoPE and without SC-RoPE on PDTSP Instances.

Gap to LKH (%) ↓N2S (original)N2S+SC-RoPE
PDTSP200.060.03
PDTSP502.442.32
PDTSP1004.493.26

W6 & Q8: Sensitivity to the penalty settings for inference and training on MOCVRP?

Good question. The penalised objectives are defined as f1p=f1(1+v/f2)f_1^p = f_1 (1 + v/f_2) and f2p=f2+vf_2^p = f_2 + v in Eq. (14), where vv is the total overload; the coefficient of vv can be seen as 1.0.

For inference, we changed the penalty coefficient from 1.0 to 0.5 and 2. As shown in Table J, on Bi-CVRP20 the results remain unchanged, and on the larger problems Bi-CVRP50/100, the penalty coefficient of 0.5 performs best. A possible explanation is that a smaller penalty makes the search visit infeasible solutions more often, which helps it move between feasible solutions [12]. For example, on Bi-CVRP100, 8%, 5% and 2% of the search steps are used in infeasible solutions with coefficients 0.5, 1.0 and 2, respectively.

Table J: HV of SUPL2I with Different Penalty Coefficients (trained with coefficient 1.0, inference).

Coefficient0.51.0 (paper)2
Bi-CVRP200.43090.43090.4309
Bi-CVRP500.41110.41100.4107
Bi-CVRP1000.40720.40690.4067

For training, we re-trained the model with coefficients 0.5 and 2, and tested each model with the coefficient it was trained with. As shown in Table K, a similar pattern is observed: the model with the smaller coefficient 0.5 achieves better HV results on Bi-CVRP50 and Bi-CVRP100.

Table K: HV of SUPL2I with Different Penalty Coefficients (training and inference).

Coefficient0.51.0 (paper)2
Bi-CVRP200.43080.43090.4309
Bi-CVRP500.41130.41100.4109
Bi-CVRP1000.40750.40690.4072

Thank you for this useful comment, which enables us to find something we did not think about previously. We have included the above discussion together with Tables J-K in Appendix H (page 22) of the revised manuscript.

AuthorsOpenReview ↗

Initial Responses to Reviewer DMtk (Part 3/3)

W7 & Q9: Robustness to different preference distributions?

We believe SUPL2I can be more robust to different preference distributions (compared to other multi-objective neural methods), as it considers not only the preferences but also the Pareto dominance relation (the nondominance-based acceptance); the latter is independent of preference distributions.

To verify this, in addition to the uniform preferences used in the paper (i.e., Dir(1, 1)), we now add two other Dirichlet distributions: Dir(2, 2), which places most preferences in the middle (Middle), and Dir(0.5, 0.5), which places most of them near the two ends (Extreme). Table L summarises the results for both inference and training.

For inference, we test the model in the paper under Middle and Extreme (the row "trained with Uniform" in Table L). As shown, the HV of SUPL2I decreases only slightly, whereas that of the L2C baseline WE-CA decreases more substantially.

For training, we re-train SUPL2I with Middle and Extreme (the rows "trained with Middle" and "trained with Extreme" in Table L). As shown, the three models achieve similar HV, with differences of at most 0.0003 in each column.

Table L: HV of SUPL2I under Different Preference Distributions on Bi-TSP100.

MethodUniform (paper)MiddleExtreme
WE-CA0.70340.70230.7017
SUPL2I, trained with Uniform (paper)0.71010.70990.7092
SUPL2I, trained with Middle0.71000.70980.7090
SUPL2I, trained with Extreme0.70980.70970.7090

[1] Pareto set learning for neural multi-objective combinatorial optimization, in ICLR, 2022.

[2] Rethinking neural multi-objective combinatorial optimization via neat weight embedding, in ICLR, 2025.

[3] Behavior of Multiobjective Evolutionary Algorithms on Many-Objective Knapsack Problems, TEVC, 2015.

[4] Learning to iteratively solve routing problems with dual-aspect collaborative transformer, in NeurIPS, 2021.

[5] UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems, in NeurIPS, 2024.

[6] POMO: Policy optimization with multiple optima for reinforcement learning, in NeurIPS, 2020.

[7] Learning improvement heuristics for solving routing problems, TNNLS, 2021.

[8] Solving multiobjective combinatorial optimization via learning to improve method, TETCI, 2025.

[9] Pareto Improver: Learning Improvement Heuristics for Multi-Objective Route Planning, T-ITS, 2024.

[10] A survey on pickup and delivery problems, Journal für Betriebswirtschaft, 2008.

[11] Efficient Neural Neighborhood Search for Pickup and Delivery Problems, in IJCAI, 2022.

[12] A tabu search heuristic for the vehicle routing problem, Manage. Sci., 1994.

Reviewer_e9FROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SUPL2I, a standalone preference-conditioned learning-to-improve framework for multi-objective combinatorial optimization. The method introduces objective-wise representations, preference conditioning at both the embedding and score-fusion stages, size-aligned cyclic rotary positional encoding (SC-RoPE), and a nondominance-based acceptance strategy. Experiments on multi-objective TSP and CVRP demonstrate competitive performance against neural and conventional solvers in terms of hypervolume (HV), including cross-size generalization.

Critical strengths
  1. SUPL2I achieves competitive hypervolume results across multiple multi-objective routing benchmarks, outperforming several neural and conventional baselines. The reported improvements over existing learning-to-improve methods are particularly encouraging.

  2. The paper develops a single model that supports different preferences and problem sizes without relying on an external evolutionary algorithm. This is a useful direction for extending neural L2I methods to multi-objective optimization

Critical weaknesses
  1. Many components of SUPL2I build upon established techniques from single-objective L2I and multi-objective optimization, including preference conditioning, local improvement operators, and Pareto-based acceptance. Although multi-objective optimization introduces additional challenges, it remains unclear whether the proposed adaptations constitute substantial methodological advances beyond combining existing techniques.

  2. Although SUPL2I is described as standalone, inference involves parallel preference-conditioned trajectories, elite preservation, and periodic elite sharing. These search mechanisms may contribute substantially to the reported performance, but their individual effects are not sufficiently isolated.

  3. Limited evaluation on larger problem instances. The experiments mainly focus on problems with 20–100 nodes, while cross-size generalization is evaluated only up to 200 nodes. The current evaluation is insufficient to establish scalability and robustness on substantially larger instances.

Questions for authors
  1. SC-RoPE captures cyclic, hierarchical, and size-aligned structures that are also present in single-objective routing problems. Could the authors evaluate whether it provides similar benefits for existing single-objective L2I solvers?

  2. Given the extensive development of single-objective L2I methods, could the authors clarify which components specifically address challenges unique to multi-objective optimization and why existing L2I frameworks cannot be adapted in a relatively straightforward manner?

2 comments
AuthorsOpenReview ↗

Initial Responses to Reviewer e9FR (Part 1/2)

Many thanks for your time and valuable feedback on our paper. Below are our detailed responses to your comments, where W denotes Weakness (W1–W3) and Q denotes Question (Q1–Q2). All revisions to the original manuscript are marked in blue for your convenience.

W1: Contribution beyond established techniques?

To our knowledge, the proposed SUPL2I is the first standalone L2I method for multi-objective combinatorial optimisation problems (MOCOPs), i.e., a single policy performs the whole search from random solutions to approximate the entire Pareto front. In contrast, existing methods [1-2] rely on an external search framework (e.g., an MOEA or local search): the learned policy only improves a given solution for a small number of steps (e.g., 4 or 50 local refinements). Three major issues are in the way when developing a competitive standalone multi-objective L2I method:

  1. A single policy needs to serve all preferences over long trajectories without drifting into unpromising regions of the search space.
  2. Preference conditioning needs to handle positional information in addition to node features.
  3. It is desirable that the positional encoding can transfer across problem sizes while capturing the solution structure (e.g., circularity and hierarchy in routing).

SUPL2I addresses these issues with three key components:

  • Nondominance-based acceptance: Unlike in single-objective problems, a move in MOCOPs can also lead to an incomparable solution. SUPL2I uses this characteristic to make training and inference more efficient: it only considers superior solutions and nondominated ones, which contrasts with existing multi-objective L2I methods [1-2] that consider any solution.

  • Score-level fusion: In MOCOPs, a local move can affect each objective differently. SUPL2I keeps the node positions free of the preference, and injects the preference not only into the node embeddings but also into the fusion of per-objective scores.

  • SC-RoPE: Unlike existing positional encodings in L2I (both single-objective and multi-objective L2I) [2-3], SC-RoPE not only captures the circularity and hierarchy of routing solutions but also keeps wavelengths comparable across sizes. Notably, SC-RoPE can also benefit existing single-objective L2I solvers. Please refer to our response to Q1 about the effectiveness of SC-RoPE on single-objective L2I.

To make this clearer, we have revised the manuscript to explain the similarities and differences between the proposed components and related existing techniques in Appendix I (page 22).

W2: Effects of the inference mechanisms (parallel trajectories, elite preservation and elite sharing) on the performance?

Regarding parallel trajectories and elite preservation, they are standard practices in the inference of neural combinatorial optimisation (NCO) [4-6], which we simply followed.

As for elite sharing, it is the one proposed in this work. We have now added an ablation study on Bi-TSP as an example. As shown in Table A below, elite sharing indeed improves HV. Notably, the proposed method without elite sharing already outperforms the best L2C baseline WE-CA [6] and the L2I baseline MOGLS+WRPN [2].

Table A: Results (HV) of SUPL2I with and without Elite Sharing on Bi-TSP.

ProblemWE-CAMOGLS+WRPNSUPL2I w/o elite sharingSUPL2I w/ elite sharing
Bi-TSP200.62700.62970.62980.6298
Bi-TSP500.63920.64380.64490.6451
Bi-TSP1000.70340.70560.70720.7101

W3: Limited evaluation on larger problems.

Since the proposed SC-RoPE encodes relative positions with a consistent local resolution across problem sizes, our method is expected to generalise well to larger problems.

To confirm this, we have added experiments on larger Bi-TSP with 300/500/1000 nodes. Due to the time constraint, we generate 5 random instances for each size. As shown in Table B, SUPL2I consistently outperforms the baseline WE-CA on all three sizes, with its advantage increasing with the problem size.

We have added this, along with results on other larger problems, to Appendix F.1 (page 20) in the revised manuscript.

Table B: HV on Larger Bi-TSP.

Problem SizeWE-CASUPL2I
Bi-TSP3000.77240.7772
Bi-TSP5000.77990.8022
Bi-TSP10000.76930.7937

It is worth noting that L2I methods (as well as multi-objective NCO methods) usually evaluate generalisation on problems with up to 200 nodes [5-6]. This contrasts with L2C in the single-objective case, where substantially larger problems (e.g., 10,000 nodes or more) are considered (through dedicated designs such as divide-and-conquer [7]).

AuthorsOpenReview ↗

Initial Responses to Reviewer e9FR (Part 2/2)

Q1: SC-RoPE also benefits existing single-objective L2I?

Good question. Yes, SC-RoPE should also work in the single-objective setting, as it is independent of the number of objectives. To confirm this, we have conducted experiments by replacing the cyclic positional encoding (CPE) of DACT [5], a representative single-objective L2I solver, with SC-RoPE and re-trained the model. As shown in Table C below, SC-RoPE consistently outperforms the original CPE of DACT.

Table C: Gap of Different Positional Encodings of DACT on Single-Objective TSP & CVRP.

Gap to LKH (%) ↓CPE (original)SC-RoPE (ours)
TSP500.010.00
TSP1000.730.49
CVRP500.760.74
CVRP1001.931.90

Q2: Which components are specific to MOCOPs? Why not directly adapt existing L2I frameworks?

The score-level fusion and nondominance-based acceptance are two components specific to MOCOPs; please see our response to W1 about the contributions of the proposed work.

A direct adaptation of existing L2I methods may not work well on multi-objective problems. WRPN [2] is such an adaptation: it conditions the single-objective DACT [5] on the preference by injecting a weight embedding into the node and positional embeddings, and leaves the rest of the network unchanged. To further address your concern, we compare SUPL2I with WRPN on Bi-TSP as an example. As shown in Table D, SUPL2I consistently outperforms WRPN on all sizes, with its advantage increasing with the problem size.

Table D: HV of WRPN and SUPL2I on Bi-TSP.

Problem SizeWRPNSUPL2I
Bi-TSP200.62850.6298
Bi-TSP500.63990.6451
Bi-TSP1000.69780.7101
Bi-TSP1500.66220.7083
Bi-TSP2000.45170.7392

[1] Pareto improver: Learning improvement heuristics for multi-objective route planning, T-ITS, 2024.

[2] Solving multiobjective combinatorial optimization via learning to improve method, TETCI, 2025.

[3] Rethinking positional encoding for neural vehicle routing, arXiv:2605.11910, 2026.

[4] Learning improvement heuristics for solving routing problems, TNNLS, 2021.

[5] Learning to iteratively solve routing problems with dual-aspect collaborative transformer, in NeurIPS, 2021.

[6] Rethinking neural multi-objective combinatorial optimization via neat weight embedding, in ICLR, 2025.

[7] UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems, in NeurIPS, 2024.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Responses and Revisions

Dear Area Chair and Reviewers,

We thank all reviewers for their helpful comments. We have uploaded a revised manuscript, with all revisions marked in blue. The main changes are:

  • New results: the multi-objective knapsack problem (Section 6, Table 3), and larger instances (Appendix F.1).
  • New analyses: non-supported solutions (Section 6.2, Appendix G), sensitivity to the penalty coefficient (Appendix H), relation to existing techniques (Appendix I), and the acceptance rule on more problems (Appendix J).
  • Revised reporting: the Gap is now relative to classical solvers (Section 6 and the result tables), the statements of "less time" are removed, and the inference-time limitation is clarified (Section 7).

Section, equation and table numbers in our responses refer to the revised manuscript. Please see the individual responses for details and further results.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.