Thank you for your valuable comments.

Q1: I would've thought that for combinatorial optimization which indeed has precise rewards, using preferences (which is imprecise) can be worse.

We agree that precise rewards are also crucial to combinatorial optimization. Meanwhile, we would like to clarify that POCO, unlike standard preference optimization techniques used in LLM, incorporates the precise objective value (i.e., reward in RL) into our loss function. As highlighted in our submission, this key contribution stems from our insight into the critical role of precise rewards in combinatorial optimization.

Specifically, the proposed POCO loss is $\log\sigma\left(\frac{g(y_l)}{g(y_w)}\left(\frac{\log\pi_\theta(y_w|x)}{|y_w|}-\frac{\log\pi_\theta(y_l|x)}{|y_l|}\right)\right)$, where $\frac{g(y_l)}{g(y_w)}$ is a scaling factor derived from precise objective values for the best solution and the inferior one.

The results in Table 6 and discussions in Section 5.4 demonstrate the effectiveness of incorporating precise objective values into the POCO loss, e.g., POCO reduces the gap to 12.9% on the DMU benchmark, outperforming its variant without this scaling factor (gap 13.2%).

Q2: I'm inclined to think of possible subtle numeric effects which led to this result.

While we acknowledge that numerical artifacts can sometimes confound comparisons, we emphasize that our core contribution, a novel preference-based training framework, is not attributable solely to such effects.

• By leveraging preference learning between the best solution and diverse inferior ones, POCO guides the model toward promising decision trajectories and discern suboptimal choices, demonstrating its clear advantage against RL methods. POCO exhibits significantly superior solution quality and higher training efficiency ($48\times$ speedup for JSP), as shown in the response to Reviewer upvg Q5 and Q1, respectively. Note that POMO, a REINFORCE-based method, uses terminal rewards and computes baselines via means, eliminating value-head estimation and minimizing numeric effect risks.
  • Here is a closer look at policy gradient. POMO uses a baseline to distinguish positive/negative optimization signals for each sample: $(g(y) - b) \nabla_\theta \log \pi_{\theta}(y|x).$ In contrast, POCO directly distinguishes based on exact preferences: $\frac{g(y_l)}{g(y_w)}\frac{(1-\sigma(z))}{|y_w|}\nabla_\theta\log\pi_\theta(y_w|x)-\frac{g(y_l)}{g(y_w)}\frac{(1-\sigma(z))}{|y_l|}\nabla_\theta \log\pi_\theta(y_l|x),$ where $z=\frac{g(y_l)}{g(y_w)}\left(\frac{1}{|y_w|}\log \pi_\theta(y_w|x)-\frac{1}{|y_l|}\log\pi_\theta(y_l|x)\right)$. The optimization signal strength correlates with the log-likelihood difference $z$, requiring the model to maximize the probabilities gap between $y_w$ and $y_l$. This results in faster convergence and better performance.
• POCO's advantage primarily stems from pairwise preference learning, rather than simply being a RL variant with the proposed filtering method. To demonstrate this point, we compare POCO with a POMO variant employing our Hybrid Rollout and Uniform Filtering (denoted as POMO+). The key difference lies in the loss: while POCO uses pairwise loss, POMO+ calculates a standard POMO loss based on the filtered $K$ solutions, as it lacks the pairwise mechanism. Results in Table H show that POMO+ is inferior to POCO, demonstrating the effectiveness of the preference learning of POCO. Moreover, POMO+ is even inferior to POMO, underscoring that the filtering method is tightly adapted to POCO and may not be applicable to general RL methods.

Based on the above two points, we would like to reiterate that POCO's unique advantages stem from its preference learning and the two tightly coupled designs (the pair construction method and the loss function based on objective values), rather than simply relying on subtle numeric effects.

Table H: Gaps (%) on TSP

Q3: Mainly Section C, to verify what types of RL losses are being used.

We have stated typical RL losses in Section 3.1, including REINFORCE for routing problems and PPO for scheduling problems. According to your suggestions, we will add a detailed description and analysis of these RL losses to Appendix C.

Q4: The current presentation of the paper makes the contribution incremental and not fundamental ...

Our main contribution is a novel training framework, distinctly different from traditional RL, that not only improves performance but also convergence speed. We will thoroughly proofread the paper to highlight this core contribution.

Q5: ..., the gains are fairly incremental, and overall combinatorial optimization has become very saturated.

In the NCO field, such improvements are considered significant. POCO delivers substantial performance gains and faster convergence, as demonstrated in our responses to Reviewer upvg Q5 and Q1, respectively.

Thank you for your valuable comments.

Q1: I recommend to also includes SL-based POMO as baseline.

We have added results from the SL-based method [1] to the table E. Since all methods use the same model, differences stem from training algorithms.

POCO achieves comparable or better performance than SL-based methods without requiring labeled optimal solutions, further demonstrating the superiority of POCO. Results show that on TSP20, SL-based and POCO perform identically. On TSP50, SL-based slightly outperforms POCO (0.001% vs 0.01%). However, on TSP100, POCO is superior (0.04% vs 0.05%).

Table E: Gaps (%) on TSP Instances

[1] Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem. ACM Transactions on Evolutionary Learning, 2024.

Q2: the preparation stage for POCO can be time-consuming compared to RL-based methods. Can you provide a preparation time for each instance?

This problem is mainly caused by us sampling more solutions (larger $B$). We provide the following clarification:

1. POCO does not necessarily require sampling a large number of solutions to maintain performance. As noted in our response to Reviewer upvg Q4, POCO still achieved superior performance when sampling the same number of solutions as POMO, although we recommend an best value of 256 for $B$.
2. Training time does not significantly increase with larger $B$. Table F shows the approximate training time per epoch for different problem scales and $B$. For small-scale problems, the training time has hardly changed. For larger problems like TSP100, even if $B$ is increased by 2.5 times, the training time only increases by 1.6 times.

Table F: Training Time Per Epoch

Q3: As far as I know, there is not much work using PPO in NCO training, so is this part of the description a bit redundant?

We acknowledge that REINFORCE is the dominant training algorithm for routing problems. However, as noted in our paper, PPO is a typical method for scheduling problems [2-4]. We remain open to further refinements to enhance clarity and relevance.

[2] Learning to dispatch for job shop scheduling via deep reinforcement learning. NeurIPS 2020.

[3] Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 2023.

[4] Solving flexible job shop scheduling problems via deep reinforcement learning. Expert Systems with Applications, 2024.

Q4: Will using raw scaling factors lose stability on different problems? Can rank-based factors or factors after normalization be better?

This is a very interesting question. We agree this is a valuable direction for future research.

1. We observed that scaling factors vary across different problems, with distributions differing significantly. For some challenging problems, such as those where objective values have large or minimal gaps, raw scaling factors might fail. This is an important area for further exploration.
2. Rank-based factors offer stability in any scenario but may not accurately reflect true solution differences, potentially leading to suboptimal performance. Normalized factors, however, seem promising, with techniques like normalization, clipping, or compression functions offering potential improvements.

Q5: Can POCO generalize to NCO models other than POMO on TSP?

We would like to emphasize that POCO, like POMO, is a general and fundamental training algorithm. POMO serves as the backbone for most SOTA methods, so naturally, the backbone of these SOTA methods can also be replaced with the superior POCO. To further showcase this potential, we conducted additional experiments on InViT [5].

Specifically, we adopt POCO to train InViT, but due to memory constraints, we set the batch size to 64 for InViT (also $B$ for InViT+POCO), with $K=8$. We retrained InViT with identical parameters. Results in Table G shows that InViT+POCO outperformes InViT on various distributions and larger-scale problems.

Table G: Gaps (%) on TSP

Distribution: Uniform (U), Cluster (C), Explosion (E), Implosion (I). The numbers behind represent the problem scales. Note that we report the results both for 300 epochs due to extended training time. Full results for 800 epochs will be provided in the subsequent discussion phase.

[5] InViT: A generalizable routing problem solver with invariant nested view transformer. ICML 2024.

We thank the reviewer for the encouraging feedback and incisive questions.

Q1: Concorde is not used for TSP.

We have included Concorde's results from POMO [1] and added them to the table C for comparison. Concorde, LKH3, and Gurobi are traditional iterative search-based algorithms with identical performance (0.0% gap), differing only in solving time.

LKH3, being a strong heuristic solver, can offer fast approximate solutions for large-scale problems and even delivery the optimal solutions for small-scale problems. Including Concorde's results does not alter our existing conclusions, as we have already incorporated other strong heuristic methods.

Table C: Gaps (%) on TSP Instances

[1] POMO: Policy optimization with multiple optima for reinforcement learning. NeurIPS 2020.

Q2: Subpar results when compared to SOTA heuristic Concorde. In general, what is the advantage of using this NCO when compared to LKH3 and Concorde?

Unlike traditional iterative search-based methods, NCO without expert knowledge balances solving time and performance, so its contribution should not be evaluated solely based on performance.

• A key advantage of NCO is its ability to achieve near-optimal solutions with significantly shorter solving times, especially for large-scale problems：
  • For TSP100, POCO achieves a near-optimal gap of 0.04% while reducing solving time dramatically (17m for LKH3 vs. 18s for POCO).
  • On large-scale JSP problems (TA 100x20), NCO demonstrates clear advantages. Exact algorithms like Gurobi and OR-Tools, within 1 hour (see Table 12 in Appendix D), achieve 11% and 3.9% gap (see Table 1), respectively, which are inferior to the 1.4% gap POCO achieves in just 8 seconds (see Table 12 and Table 1, respectively).
• Another advantage of NCO is that it does not require expert knowledge to design complex algorithms, thereby expanding its applicability to a wider range of scenarios.

Q3: How about TSP-1000? Can the authors test their trained model on instances where the ILP fails?

To further showcase the potential of POCO on large-scale problems, we conducted additional experiments on InViT [2] framework, which is designed to solve large-scale problems where the ILP fails. Note that POMO is not designed for large-scale problems, but we have also demonstrated the superiority of POCO with generalization experiments on TSPLIB (see Table 3).

Main results generalizing to various distributions and larger-scales are shown in Table D. InViT+POCO outperformes InViT on all distributions and scales, underscoring its superiority. At these scales, Gurobi and LKH3 require 30 minutes to 1.5 days to solve, whereas NCO needs only up to approximately 10 minutes.

Table D: Gaps (%) Across Different Distributions and Scales

"U": Uniform, "C": Cluster, "E": Explosion, "I": Implosion distributions. The numbers behind represent the problem scales. Note that we report the results both for 300 epochs due to extended training time. Full results for 800 epochs will be provided in the subsequent discussion phase.

[2] InViT: A generalizable routing problem solver with invariant nested view transformer. ICML 2024.

Thank you for your valuable comments.

Q1: it remains unclear precisely how sample efficiency is enhanced.

We have analyzed POCO's higher sample efficiency in Section 5.4. We further precisely demonstrate significant improvements in sample efficiency by supplementing quantitative results. Note that we retrained models on TSP20/50 with $B=20/50$ & $K=8$, ensuring a fair comparison.

POCO achieves faster convergence than RL when using the same numbers of samples and gradient steps:

1. POCO achieves approximately $48\times$, $20\times$, and $3\times$ higher training efficiency than RL methods on JSP, TSP20, and TSP50, respectively. Specifically, POCO requires only 2500 training steps, 10 epochs, and 70 epochs to match the gaps achieved by RL methods, which take 120000 steps, 200 epochs, and 200 epochs, respectively.
2. POCO achieves significantly superior solution quality within the same number of training epochs. On JSP, POCO attains 0.76%/4.12% lower gaps than RL/SLIM in just 5 epochs. For TSP20/50, POCO achieves 0.0076%/0.0687% lower gaps than POMO in 100 epochs.

Q2: it remains unclear what specific advantages can be achieved by increasing the values of $B$ and $K$.

The advantages of increasing $B$ and $K$ under the same time and computational resources can be seen in Section 5.5.

1. Increasing $B$ improves performance while increasing memory usage. As shown in Figure 4(a), the gap reduces from 8.3% to 7.9% as $B$ increases from 32 to 512, plateauing at $B=256$. Beyond this point, increasing $B$ provides negligible improvement, as sampling more from $\pi$ rarely yields better solutions. This result demostrates our reasonable setting of $B=256$.
2. As presented in Figures 4(b-c), the recommended value for $K$ is 16, and it should scale proportionally with $B$.

Q3: comparison with recent SOTA studies.

We would like to emphasize that POCO, like POMO, is a general and fundamental training algorithm. POMO serves as the backbone for most SOTA methods, so naturally, the backbone of these SOTA methods can also be replaced with the superior POCO. To further showcase this potential, we conducted additional experiments on InViT, which has demonstrated superior performance over LEHD and Pointerformer in its paper.

Specifically, we adopt POCO to train InViT, but due to memory constraints, we set the batch size to 64 for InViT (also $B$ for InViT+POCO), with $K=8$. We retrained InViT with identical parameters. Results in Table A shows that InViT+POCO outperformes InViT on various distributions and larger-scale problems.

Table A: Gaps (%) on TSP

Distribution: Uniform (U), Cluster (C), Explosion (E), Implosion (I). The numbers behind represent the problem scales. Note that we report the results both for 300 epochs due to extended training time. Full results for 800 epochs will be provided in the subsequent discussion phase.

Q4: Due to this discrepancy in the number of solutions generated by each method per instance, it is difficult to consider this experiment as a fair comparison.

For a fair comparison, we retrained models on TSP20/50 with $B=20/50$ & $K=8$, ensuring it samples the same number of solutions during training as POMO.

Despite reducing $B$, POCO maintains performance comparable to $B=128$, with superior solution quality (see Table B), higher training efficiency (see response to Q1), and better generalization (see response to Q3).

Table B: Gaps (%) on TSP.

Q5: the performance gap is too small to be considered a meaningful difference.

1. For well-optimized small-scale or easy problems, such as TSP20, achieving further improvement, e.g., 0.0013% gap to the optimal solution, is quite challenging. However, the improvements become more pronounced for larger-scale or harder problems: (1) On larger-scale TSP100, POCO's gap 0.04% vs POMO's 0.14% (see Table 2); (2) On the harder JSP, POCO's gap 12.9% vs $SLIM_{MGL}$'s 16.5% on DMU benchmark (see Table 1); (3) On much larger-scale unseen TSPLIB instances with 500-1000 nodes, POCO's gap 22.44% vs POMO's 30.14% (see Table 3).
2. In the NCO field, such improvements are considered significant, as evidenced by literature from top AI conferences [1,2]. In [1], among 12 TSP cases, 10 cases (83%) show improvements over the second-best neural method smaller than 0.1%. Similarly, in [2], 6 out of 12 TSP cases (50%) have similar improvement levels.

[1] Collaboration! Towards Robust Neural Methods for Routing Problems. NeurIPS 2024.

[2] Learning encodings for constructive neural combinatorial optimization needs to regret. AAAI 2024.