- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes FWNCO, which employs a Frank–Wolfe decomposition to transform neural network outputs into a sparse distribution over feasible discrete solutions. The network is trained by optimizing the weighted expectation of a discrete objective, and the best candidate solution is selected during inference. Compared to GeoNCO and the Birkhoff Extension, the primary change lies in a unified decomposition process that allows network outputs to reside outside the feasible polytope, thereby reducing the need for problem-specific projection and decomposition designs. Experiments cover the Maximum Coverage (MC) problem, the Quadratic Assignment Problem (QAP), and the Euclidean Traveling Salesperson Problem (TSP)—with the latter utilizing subtour LP features and integrating a solution process composed of spanning trees and matchings into training. Results indicate improvements in solution quality or efficiency over some neural baselines, though a consistent advantage over strong solvers has yet to be established.
Critical strengths
- The unified decomposition interface can reduce the need for problem-specific projection and decomposition designs, provided that an efficient Linear Maximization Oracle (LMO) is available.
- The improvements over GeoNCO in the MC problem, along with the results from the "GreedyTrap" experiment, suggest that the model is capable of learning effective problem structures.
Critical weaknesses
- In a similar way to tackle similar problems (similarly uses neural predictions of edge or node probabilities to construct solutions for TSP, MIS, and MCl), GenSCO’s "Training with Suboptimal Supervision" approach has already demonstrated the effectiveness of using inexpensive supervision. Compared to this line of work, the practical advantages of the self-supervised method proposed in this paper—in terms of total training cost and solution performance—remain unclear.
- The performance gains in the main experiments are limited: for the Maximum Coverage (MC) problem, the proposed method underperforms the Greedy baseline across all six experimental settings while also being slower; for the Traveling Salesperson Problem (TSP), both solution quality and speed lag behind COExpander and LKH3.
Questions for authors
- For the Quadratic Assignment Problem (QAP), the average gap improves only marginally—from 26.8% (SAWT) to 26.4%. Could the experiments be re-run on consistent hardware to verify the claimed speed advantages?
- Could you provide a comparison for BiQAP and PLMA based on a fixed time budget, while distinguishing between settings without TTO and search-enhanced settings?
- Could you include results for the Capacitated Vehicle Routing Problem (CVRP) or the TSP with Time Windows (TSPTW), and clarify the construction process and computational overhead of the Linear Maximization Oracle (LMO) under resource constraints?
- Does the greedy oracle for QAP satisfy Equation (8)? Furthermore, does Theorem 3.3 still apply to the entropy-regularized update for TSP?
- There is a discrepancy between the fixed geometric instance pool mentioned in Appendix D.1 and the online random integer matrix generation used in train.py. Which configuration was actually employed for training?
5 comments
Responce 2
The performance gains in the main experiments are limited: for the Maximum Coverage (MC) problem, the proposed method underperforms the Greedy baseline across all six experimental settings while also being slower; for the Traveling Salesperson Problem (TSP), both solution quality and speed lag behind COExpander and LKH3.
We agree with both observations as statements about Tables 1 and 3, and we add the context needed to interpret them.
Gain in Maximum Coverage. FWNCO lies on the neural quality–runtime Pareto frontier in five of the six settings in Table 1; Rail with is the exception. It is also faster than GeoNCO in every setting.
Greedy carries a guarantee and is a strong baseline on these instances: its coverage is within 1.2% of the 120-second Gurobi solution in every setting and exceeds it on Rail with . No learning-based method in Table 1 exceeds Greedy in any setting. However, on GreedyTrap instances, designed to challenge Greedy, FWNCO improves coverage over Greedy by 21.3% on average (Table 5). With test-time optimization, FWNCO also exceeds Greedy in all four Random settings (Table 16).
Gain in TSP. Every neural method in Table 3 trails LKH3 on TSP-500 and TSP-1000, including COExpander, which is trained with supervision on up to about 1.5M labeled instances. FWNCO uses no labels and trains in under one hour, and on TSP-500 and TSP-1000 it has a lower gap than the supervised DIFUSCO and the RL-based DIMES.
Gain in QAP and CVRP. On QAP, FWNCO has the lowest gap among the compared methods that do not optimize on the test instance, including the classical solvers SM, RRWM, and SK-JA (Appendix D.5). On CVRP, added in the revision, it improves on the Clarke–Wright heuristic from 7.13% to 5.13%.
A unified framework for all the studied cases. Greedy for Maximum Coverage, LKH3 for TSP, and Clarke–Wright for CVRP are each designed for one problem. FWNCO is a single method: the same decomposition and expected-objective loss are applied to cardinality, permutation, spanning-tree, and capacity constraints, with the oracle as the main problem-specific component. This line of work studies whether learned, constraint-aware models can be built in a problem-agnostic way, and is evaluated accordingly. Our contribution is this general framework, and we do not claim that it outperforms specialized classical solvers on problems where they are near-optimal.
For the Quadratic Assignment Problem (QAP), the average gap improves only marginally—from 26.8% (SAWT) to 26.4%. Could the experiments be re-run on consistent hardware to verify the claimed speed advantages?
We have implemented the required evaluation adapters and evaluated the following methods on QAPLIB, consistent with the benchmark used by NGM, RGM, SAWT, and our original experimental setup. All methods use the same 108 instances of sizes 12–64 across 14 categories, matching the test set in our original main table. All experiments use the same machine, equipped with an AMD Ryzen 9 9950X CPU and an NVIDIA RTX 4090 GPU.
| Method | Category-mean gap (%) ↓ | Time per instance (s) ↓ |
|---|---|---|
| SM | 67.36 | 0.0018 |
| RRWM | 64.23 | 0.1683 |
| NGM | 46.76 | 1.8310 |
| SK-JA | 42.08 | 42.0689 |
| Adapted SAWT, 2000 improvement steps | 39.37 | 11.1633 |
| Adapted SAWT, 10000 improvement steps | 35.49 | 50.3622 |
| FWNCO | 26.34 | 0.7184 |
Our response to Reviewer 82dq also details the data sources and training and evaluation protocols, and explains how missing QAPLIB-specific code, configurations, and checkpoints prevent us from reproducing certain published results on the same hardware.
Response 3
Could you include results for the Capacitated Vehicle Routing Problem (CVRP) or the TSP with Time Windows (TSPTW), and clarify the construction process and computational overhead of the Linear Maximization Oracle (LMO) under resource constraints?
We have added CVRP as a new problem, described in Appendix I of the revised paper. We evaluate on all 10,000 XML100 instances, a public CVRPLIB benchmark with proven optimal solutions. Rebuttal time constraints prevented a comprehensive comparison with all CVRP solvers. All methods run on the same machine (AMD Ryzen 9 9950X CPU, NVIDIA RTX 4090 GPU), with fixed weights and their native decoders, without augmentation, beam search, local search, or test-time training. Gaps are relative to the optimal values and averaged over instances. Timing covers in-memory preprocessing, transfers, neural inference, decoding, candidate selection, and final feasibility and objective verification.
| Method | Network use and decoding | Mean gap (%) ↓ | Time per instance (ms) ↓ |
|---|---|---|---|
| Clarke–Wright | savings heuristic | 7.13 | 0.70 |
| GNARKD-AM | one pass, greedy | 28.93 | 29.56 |
| GNARKD-POMO | one pass, multi-start greedy | 18.15 | 34.17 |
| POMO | autoregressive, 100 starts | 9.28 | 73.86 |
| ReLD | autoregressive, 100 trajectories | 2.88 | 84.67 |
| FWNCO | one pass, up to 32 FW updates | 5.13 | 6.35 |
FWNCO achieves a lower gap than Clarke–Wright, both GNARKD variants, and POMO. ReLD achieves the lowest gap, at about 13.3 times FWNCO's inference time.
Baselines. Clarke–Wright merges routes according to distance savings while respecting capacity. GNARKD distills AM and POMO into non-autoregressive models; we use the authors' implementation and checkpoints. GNARKD-AM uses one network pass followed by greedy decoding, and GNARKD-POMO decodes greedily from its multiple native starting customers and returns the best solution. POMO and ReLD construct solutions autoregressively, calling the decoder at every construction step: POMO from 100 starting customers, and ReLD with the authors' greedy decoder over 100 parallel trajectories. Each returns its best solution. Both use the released CVRP100 checkpoints.
FWNCO setup. A single model is trained on generated CVRP20/50/100 instances with uniform and four-cluster layouts; XML100 is used only for testing. Inference uses one network pass and up to 32 FW updates, and returns the best of the feasible solutions generated by the decomposition. The architecture, input features, and training schedule are given in Appendix I.
Representation and LMO. Removing the depot from a feasible set of routes leaves disjoint customer paths, each with total demand at most ; connecting each path's endpoints to the depot recovers the routes. Let be the edge-incidence vectors of these capacity-feasible path forests. FW approximates the network output by a convex combination of vectors in . With residual , the linear subproblem is
Our greedy approximate LMO starts from single-customer paths and processes positive-scoring edges in decreasing order. An edge is accepted only when
where is the component containing and is its total demand. These checks prevent branching, cycles, and capacity violations, so every output is feasible. With the savings as scores, this routine is the parallel Clarke–Wright algorithm; FWNCO replaces the fixed savings with learned scores and uses the FW residuals to generate several feasible solutions from one network output.
For symmetric costs , the route cost is affine in this representation,
so the FW mixture-weighted expected-cost objective is retained.
Overhead. With customer pairs, each oracle call builds a max-heap in and extracts edges at each, for a worst case of per call. Component membership uses parent pointers, cached loads make each capacity check , and route recovery takes .
Response 1
We thank the reviewer for the careful reading and the constructive questions. They prompted new experiments on QAP, TSP, and CVRP and several clarifications that have improved the paper; we respond to each point below.
Thank you for pointing us to GenSCO, which we have added to the related work. It is a strong method, and we do not claim an advantage over it in TSP solution quality: with its search loop and 2-opt post-processing it reports gaps below 0.1% on TSP-500 and TSP-1000. The two methods address different settings, and the practical advantages of our approach lie elsewhere.
Supervision and training cost. GenSCO's suboptimal-supervision experiment replaces Concorde labels with 2-opt labels on TSP-100 and TSP-500. This is cheaper supervision, but it is still supervision: it needs a solution for every training instance (128K to 1.28M instances in its TSP experiments), a heuristic that already produces good feasible solutions, and problem-specific local-search moves to build the training pairs. Its reported training cost is one to two days on an RTX 4090. FWNCO uses no solutions of any quality, only the objective and a linear oracle, and its TSP model trains in under one hour on a single GPU.
Inference setting. GenSCO is a test-time search method. Each of its cycles (10–160 for TSP, 500–16,000 for MIS) perturbs the current solution with local-search moves, re-samples, and decodes. Under the protocol of Appendix F this is search-enhanced inference, whereas FWNCO is evaluated with one network pass and no search.
Training–inference alignment. GenSCO trains its network to regress reference solutions. The greedy decoding that turns its output into a feasible solution, the optional 2-opt, and the search loop are applied only at inference and are not part of the training objective. In FWNCO, the combinatorial steps are inside the training loop: the loss is the expected objective of the feasible solutions produced by the decomposition, and gradients pass through the mixture weights. The network is therefore trained directly for the objective values of the solutions it returns, without labels.
Scope. GenSCO is demonstrated on TSP, MIS, and MCl, using heatmap prediction, greedy decoding, and problem-specific disruption operators. FWNCO applies one decomposition to cardinality, permutation, spanning-tree, and capacity constraints, and returns only feasible candidates by construction.