- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes NEPF for neural routing on multigraphs: it first generates a node permutation from compressed edge information, then selects one edge per segment with a lightweight network. It matches or improves prior multigraph methods while being much faster and more scalable.
Critical strengths
- Faster inference without compromising solution quality: NEPF is one to two orders of magnitude faster than GMS-EB and 2-3x faster than GMS-DH, while matching or improving solution quality.
- Broad experimental coverage: it is evaluated on six problem variants, several multigraph distributions, larger instances, real-world road networks, and different backbones.
Critical weaknesses
- The core idea, a learned two-stage decomposition, is not shown to be useful. On MOTSP and MOCVRP, edges are chosen greedily, so the good results there only support edge compression and the node policy. For the learned edge stage, the only evidence is one ablation on MOTSPTW against a per-edge greedy baseline that is myopic by construction, with no comparison to the classical dynamic program. Also, all 4 of NEPF’s losses in Table 1 occur on MOTSPTW/MOOP, the problems that use the learned edge stage.
- The scalability claim is overstated relative to GMS-DH. The decoder is still O(N³), and memory still grows with M, so invariance to M holds for runtime only. The regime where N and M are both large is never tested, and Appendix B.3 says M is usually small in practice, which is in tension with the Introduction’s motivation.
- The cross-backbone results do not support the claim of compatibility with foundation models: quality degrades on RCTSP, only the encoder is swapped in the multi-objective setting, and no pretrained GOAL/URS is used.
Questions for authors
- Can the authors compare the learned edge stage with the classical FSASP dynamic program on small instances, and report the optimality gap of the learned selection for a fixed node order, on problems where edge choice matters (MOTSPTW, RCTSP)?
- The existing ablation only removes the learned edge stage. Can the authors add a variant without the node-edge split to separate the effect of decomposition from that of compression?
- How accurate is the state estimator, and how much would an oracle state improve results on RCTSP, OP and MOOP?
- How do solution quality and runtime behave when N and M are both large (for example N=500 with M=20)?
- Can the authors show a second problem class beyond routing, such as flexible job-shop scheduling, to support the claim that the factorization is a general principle?
5 comments
W3. The cross-backbone results do not support the claim of compatibility with foundation models: quality degrades on RCTSP, only the encoder is swapped in the multi-objective setting, and no pretrained GOAL/URS is used.
To better illustrate the compatibility with cross-task models, we fine-tuned the pretrained GOAL [1] multi-task checkpoint and the URS [2] unified checkpoint (available online) with NEPF on RCTSP and OP (FLEX2, FIX2). Results have been added to Table 8 and Appendix D.4 (together with experimental setup).
Results for GOAL (see updated manuscript for URS):
| GOAL backbone | OP FLEX2 ↑ | OP FIX2 ↑ | RCTSP FLEX2 ↓ | RCTSP FIX2 ↓ |
|---|---|---|---|---|
| pretrained, 20 epochs | 41.5 | 34.3 | 4.7 | 13.9 |
| from scratch, 200 epochs | 41.6 | 32.6 | 6.87 | 15.8 |
Initializing NEPF's node stage from the pretrained GOAL checkpoint improves on training from scratch. The pretrained URS checkpoint also transfers stably. Moreover, when the original tasks are rehearsed during fine-tuning, the models keep their original capabilities, and only degrade very marginally across their rehearsed tasks.
We now consider the results to show much better that NEPF can be applied on top of these foundation models, keeping their cross-task generalization capabilities while extending them to our multigraph problems.
Regarding the multi-objective case, the foundation models were not trained there, and the number of applicable literature backbones (for asymmetric multi-objective problems) with verified performance is small, hence we are limited there in the experiments we can perform. We consider encoder-only swapping, and note that it illustrates the principle well.
Questions For Authors:
Q1. Can the authors compare the learned edge stage with the classical FSASP dynamic program on small instances, and report the optimality gap of the learned selection for a fixed node order [...]?
We have added such a direct comparison in Appendix F.9. See our response to W1 above. On the investigated settings, the learned stage matches the exact one well, while remaining substantially faster.
Q2. [...] Can the authors add a variant without the node-edge split to separate the effect of decomposition from that of compression?
We admit that we are somewhat uncertain about what is meant here exactly. Let us know if the below interpretation is not correct, and we will happily extend the experiment.
To answer the question, we trained two additional NEPF variants: NEPF-joint (the same aggregation and node encoder, but an edge head picks the edge immediately after each node, meaning state is exact) and NEPF without aggregation (only pre-encoding aggregation is removed). Together with existing models this gives a full 2×2 table (split × compression). Results for OP (higher-is-better), RCTSP (lower-is-better) and MOTSPTW (higher-is-better):
| Split | Compression | OP FLEX2 | OP FIX2 | RCTSP FLEX2 | RCTSP FIX2 | MOTSPTW FLEX2 | MOTSPTW FIX2 | |
|---|---|---|---|---|---|---|---|---|
| GMS-EB | – | – | 44.0 | 36.2 | 5.44 | 15.0 | 0.63 | 0.64 |
| NEPF w/o pre-enc. agg. | ✓ | – | 44.6 | 35.4 | 4.12 | 11.4 | 0.925 | 0.942 |
| NEPF-joint | – | ✓ | 44.5 | 36.3 | 4.28 | 10.5 | 0.927 | 0.949 |
| NEPF | ✓ | ✓ | 44.7 | 35.3 | 4.23 | 11.5 | 0.928 | 0.942 |
We can draw two conclusions: 1) NEPF compression barely affects solution quality, while it enables significantly improved scaling in memory and runtime; 2) NEPF-joint is often neutral in terms of quality, with some advantage over vanilla NEPF on the FIX distribution. However, our split additionally allows parallel edge sampling per node order, exact or heuristic FSASP solvers at inference (see W1 above), and node-only backbones such as the pretrained GOAL/URS encoders (W3). The split also scales better computationally than the joint variant. We have added this 2×2 table in Appendix F.9.
References:
[1] GOAL: A Generalist Combinatorial Optimization Agent Learner. ICLR, 2025.
[2] URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization. ICML, 2026.
(continued in next comment)
Q3. How accurate is the state estimator, and how much would an oracle state improve results on RCTSP, OP and MOOP?
Following this suggestion, we expanded Appendix D.2 with Table 12, which contains the estimator accuracy and NEPF’s sensitivity to its error. Note that injecting the ground-truth state is not possible, as it both depends on and affects the selected nodes, thereby creating a circular dependency. Instead, to measure how much a perfect state would help, we injected Gaussian noise at 1× and 2× the measured error at inference and re-evaluated.
In short: The estimator is accurate (R² 0.95–0.996), and NEPF is robust to the residual error: doubling it changes the objective minimally. Extrapolating to zero error, an oracle state would therefore add little in these settings. At the same time, Table 11 (already included in the original manuscript) establishes the necessity of this component.
Q4. How do solution quality and runtime behave when N and M are both large (for example N=500 with M=20)?
See our response to W2 above. We have extended Appendix F.2 (quality) and F.3 (memory and runtime) to cover this setting.
Q5. Can the authors show a second problem class beyond routing, such as flexible job-shop scheduling, to support the claim that the factorization is a general principle?
We implemented NEPF for flexible job-shop scheduling (FJSP), presented in new Section 5.4 with details in Appendix F.7. The node stage orders operations, with job precedence enforced by masking. The parallel alternatives are each operation's eligible machines, aggregated with the same Deep Sets pre-encoding. The edge stage assigns a machine to each operation given the order.
Results:
| 10×5 Obj. | Gap | Time | 20×10 Obj. | Gap | Time | Brandimarte [3] Obj. | Gap | Time | |
|---|---|---|---|---|---|---|---|---|---|
| CP-SAT (60 s limit) | 96.3 | 0.03% | (16m) | 200.3 | 3.40% | (1.7h) | 174.1 | 1.41% | (2.4m) |
| CP-SAT (1 h limit) | 96.2 | 0.00% | (18m) | 193.7 | 0.00% | (100h) | 172.9 | 0.41% | (2.0h) |
| MWKR | 117.4 | 22.01% | (<1s) | 220.3 | 13.76% | (<1s) | 203.3 | 21.79% | (<1s) |
| HGNN [4] | 111.7 | 16.13% | (40s) | 215.8 | 11.41% | (2.5m) | 201.0 | 28.13% | (10s) |
| HGNN (sampling) | 105.6 | 9.75% | (3.1m) | 214.8 | 10.87% | (14m) | 190.9 | 19.90% | (58s) |
| NEPF | 102.9 | 6.98% | (12s) | 196.4 | 1.37% | (45s) | 197.7 | 21.69% | (3.1s) |
On both synthetic sets, NEPF-FJSP outperforms HGNN [4] (a dedicated neural FJSP solver) with considerable runtime advantage. On Brandimarte instances [3] it lies between the two HGNN variants. On 20×10, it comes within 1.4% of the best CP-SAT solutions found with a one-hour limit per instance.
This supports the factorization as a general principle for problems with a structural decision and parallel local alternatives. Remark that we do not claim state-of-the-art performance here (it is not our goal), as we have not benchmarked against more recent neural baselines. We simply show empirically that the principle is extendable to other problems, with promising and useful results.
We hope these clarifications and additional experiments address the reviewer's concerns and would be grateful if they were reflected in the assessment. We are happy to discuss further or run additional experiments.
References:
[3] Routing and Scheduling in a Flexible Job Shop by Tabu Search. Annals of Operations Research, 1993.
[4] Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning. IEEE Transactions on Industrial Informatics, 2023.
We thank Reviewer Jr1K for their specific and very constructive questions. We have answered all five questions and the weaknesses with new experiments, which we detail below. We also updated the original manuscript, with changes in blue. Overall, the manuscript has been significantly strengthened by the new additions in our opinion (especially the pretrained foundation model experiments and the FJSP extension).
Critical Weaknesses:
We thank the reviewer for suggesting further experiments targeting the learned edge stage.
As a clarification first: on the MOTSP and MOCVRP, greedy selection is exact for linearly scalarized edge cost, so the learned edge stage is largely unnecessary. We would argue this shows exactly the usefulness of the decomposition, which exposes the simplicity of the second stage for these two problems. We have moved the edge stage configuration into the main text for further transparency.
New experiments (added to Table 7 and Appendix F.9, Table 28): For the two suggested problems (RCTSP and MOTSPTW) we compare the per-edge greedy approach, NEPF learned edge stage and Gurobi exact edge selection:
The learned edge stage is close to optimal for these configurations. It is also substantially faster (more than 5x for MOTSPTW) compared to the exact variant. In contrast, the myopic per-edge greedy collapses on MOTSPTW and is infeasible on 5% of RCTSP FIX2 instances. We also tested a more advanced non-myopic heuristic, which does not match the learned stage for the MOTSPTW (beam label setting, see Appendix F.9).
We note that learning the edge stage is what makes joint training practical, since using an exact solver there would slow down training considerably. However, a further benefit of the factorization is modularity. If a fast exact FSASP solver exists, it can replace the learned stage at inference. Without augmentation, NEPF + exact edges reaches 0.953 HV on MOTSPTW FIX2, above the best GMS result (0.951, GMS-DH with augmentation), while remaining 2.7× faster (1.8 vs. 4.9 min).
We agree with the reviewer that the manuscript can be made more precise regarding computational scaling. We have revised the wording in the Introduction, Section 5.2 and Appendix C accordingly. Overall though our conclusion still stands: NEPF's runtime is nearly invariant to M, and its dependence on M in memory is confined to the shallow pre-encoding and edge stages (which can be computed in chunks with almost no runtime penalty), whereas GMS carries the O(MN²) representation through the entire encoder.
High M and N: we supplement the results already in the paper (Appendix F.2, MOTSP) by testing N ∈ {200, 500, 1000} × M ∈ {10, 20}, zero-shot with GMS-DH and GMS-EB as baselines. The new results are in Table 19. In summary, NEPF beats GMS-DH in all cells. While it trails GMS-EB in some cells, it runs up to 19 times quicker. GMS-EB also fails to run in 6/12 configurations due to the graph size.
We additionally extend the scalability stress test in Table 20. With M=20, GMS-EB and GMS-DH fail at N>500, while NEPF (with chunked pre-encoding) handles up to N=2000.
We note that extending the main tables to the M=20 and N=500 setting is not feasible, as training GMS for M=5, N=100 is already very time consuming. However, Appendix F.2 + F.3 and Figure 2 now show the dense large N regime.
Finally, we have revised Appendix B.3 somewhat. It now cites the available evidence in literature more precisely: M is moderate (<=5) considering two edge attributes. With more conflicting attributes M will grow, often exponentially, motivating the high M regime. We note also that GMS already struggles computationally for M=5 and high node counts.
(continued in next comment)