acceptodds
Under review as a conference paper at ICLR 2027

Self-Supervised Combinatorial Optimization with Constraints via Frank–Wolfe

Abstract

Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending combinatorial objectives to convex domains is a powerful technique, yet existing approaches often require projection steps that constrain neural network outputs to lie inside the feasible polytope and rely on ad-hoc and problem-specific constructions. We propose a general framework in which the neural network is allowed to predict arbitrary continuous vectors that could potentially lie outside of the feasible polytope. These predictions are then approximated by sparse convex combinations of feasible solutions using a geometric decomposition algorithm based on Frank–Wolfe methods and approximate Carath'eodory results. This decomposition induces a differentiable, self-supervised loss defined as the expected value of the discrete objective. The same procedure provides an automatic rounding guarantee at inference time. We demonstrate strong empirical performance across multiple combinatorial problems, including the Quadratic Assignment Problem, Maximum Coverage, and the Traveling Salesperson Problem.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Constraints, Self-supervised Learning, Frank-Wolfe decomposition, Differentiable Extension

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_vdRQOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  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.
Questions for authors
  1. 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?
  2. 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?
  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?
  4. Does the greedy oracle for QAP satisfy Equation (8)? Furthermore, does Theorem 3.3 still apply to the entropy-regularized update for TSP?
  5. 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
AuthorsOpenReview ↗

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.

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.

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.

AuthorsOpenReview ↗

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 k=50k=50 is the exception. It is also faster than GeoNCO in every setting.

Greedy carries a 1−1/e1-1/e 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 k=50k=50. 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.

MethodCategory-mean gap (%) ↓Time per instance (s) ↓
SM67.360.0018
RRWM64.230.1683
NGM46.761.8310
SK-JA42.0842.0689
Adapted SAWT, 2000 improvement steps39.3711.1633
Adapted SAWT, 10000 improvement steps35.4950.3622
FWNCO26.340.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.

AuthorsOpenReview ↗

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.

MethodNetwork use and decodingMean gap (%) ↓Time per instance (ms) ↓
Clarke–Wrightsavings heuristic7.130.70
GNARKD-AMone pass, greedy28.9329.56
GNARKD-POMOone pass, multi-start greedy18.1534.17
POMOautoregressive, 100 starts9.2873.86
ReLDautoregressive, 100 trajectories2.8884.67
FWNCOone pass, up to 32 FW updates5.136.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 QQ; connecting each path's endpoints to the depot recovers the routes. Let Vcap\mathcal{V}_{\mathrm{cap}} be the edge-incidence vectors of these capacity-feasible path forests. FW approximates the network output xx by a convex combination of vectors in Vcap\mathcal{V}_{\mathrm{cap}}. With residual rt=x−ut−1r_t = x - u_{t-1}, the linear subproblem is

max⁡v∈Vcap∑i<jrt,ijvij.\max_{v\in\mathcal{V}_{\mathrm{cap}}} \sum_{i<j} r_{t,ij} v_{ij}.

Our greedy approximate LMO starts from single-customer paths and processes positive-scoring edges in decreasing order. An edge (i,j)(i,j) is accepted only when

deg⁡(i)<2,deg⁡(j)<2,Ci≠Cj,L(Ci)+L(Cj)≤Q,\deg(i)<2,\qquad \deg(j)<2,\qquad C_i\ne C_j,\qquad L(C_i)+L(C_j)\le Q,

where CiC_i is the component containing ii and L(C)L(C) 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 dijd_{ij}, the route cost is affine in this representation,

f(v)=2∑i=1nd0i−∑i<j(d0i+d0j−dij)vij,f(v)=2\sum_{i=1}^{n}d_{0i}-\sum_{i<j}(d_{0i}+d_{0j}-d_{ij}) v_{ij},

so the FW mixture-weighted expected-cost objective is retained.

Overhead. With m=n(n−1)/2m=n(n-1)/2 customer pairs, each oracle call builds a max-heap in O(m)O(m) and extracts edges at O(log⁡m)O(\log m) each, for a worst case of O(mlog⁡m)O(m\log m) per call. Component membership uses parent pointers, cached loads make each capacity check O(1)O(1), and route recovery takes O(n)O(n).

Reviewer_ekuwOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a self-supervised framework for constrained combinatorial optimization using a Frank-Wolfe decomposition layer. A neural network outputs a continuous vector that need not lie in the feasible polytope. The layer approximates it by a sparse convex combination of feasible vertices, defining a distribution whose expected discrete objective provides a training loss, optionally augmented by a reconstruction penalty. Under the stated oracle assumptions, the decomposition coefficients are almost everywhere differentiable and satisfy approximation guarantees. At inference, the method selects the best feasible candidate in the support. The framework is evaluated on Maximum Coverage, Quadratic Assignment, and TSP, with problem-specific linear optimization oracles and recovery procedures.

Critical strengths
  1. The common oracle-based construction is a useful methodological contribution. Allowing predictions outside the polytope removes a theoretical requirement of earlier geometric-extension methods, and Frank-Wolfe provides a simple decomposition procedure with an explicit oracle budget. The resulting distribution connects training and feasible solution recovery; selecting its best support element also gives a direct guarantee relative to its expected objective. This combination makes the framework more reusable across constraint families.

  2. The empirical study covers several substantially different combinatorial settings and includes informative ablations. Maximum Coverage, QAP, and TSP test different feasible structures, while the projection and iteration-budget experiments reveal meaningful practical trade-offs. The reported results support the usefulness of the framework sufficiently for a weak acceptance, provided the computational and theoretical claims are stated with the qualifications below.

Critical weaknesses
  1. The single-pass characterization understates the iterative decoding computation and weakens the interpretation of the runtime comparison. The method uses one neural forward pass, but its QAP inference procedure then runs a Frank-Wolfe decoder with T=3000 oracle calls, using greedy assignment at each step and selecting the best resulting permutation. Appendix D.4 shows that both quality and runtime depend materially on this budget. The accurate description is therefore one neural forward pass followed by iterative deterministic decoding. The no-test-time-training protocol is clear, but counting neural forward passes does not by itself control total inference work or isolate the value of the learned representation. Appendix D.3 also notes that some baseline timings are quoted from prior work on different hardware. These qualifications should accompany the headline efficiency claims, with matched end-to-end comparisons where possible.

  2. The practical scope of projection-free operation and the connection between the QAP oracle and the guarantees need clearer evidence. The theory allows unrestricted outputs, and the Maximum Coverage and TSP ablations support removing explicit projection. For QAP, however, the paper reports fragile out-of-distribution behavior and adds 20 Sinkhorn iterations to obtain approximately doubly stochastic outputs. This is a reasonable stabilization, but the paper should distinguish theoretical freedom from projection from empirical success without it. A quantitative QAP ablation is needed to establish how much robustness depends on Sinkhorn. The incremental contribution over GeoNCO would also be clearer with matched combinations of feasible versus unrestricted outputs and the respective decomposition procedures. Finally, Corollary 3.4 assumes a delta-relative Frank-Wolfe-gap oracle. The QAP implementation uses greedy assignment, and it is not established that this routine satisfies that condition on the residual matrices encountered. A guarantee for assignment weight alone would not automatically imply the required gap guarantee. This limits the applicability of the stated convergence bound, while leaving the construction of feasible candidates intact.

Questions for authors
  1. Can you describe QAP inference explicitly as one network pass plus T iterative oracle calls, and compare total inference time and solution quality under matched hardware and compute budgets where possible? Please include Sinkhorn, decomposition, candidate evaluation, and final selection in the timing.

  2. How much do QAPLIB objective gaps and runtime change when the 20-step Sinkhorn normalization is removed, with the rest of training and decoding held fixed? Reporting the effect by instance class would help establish whether projection-free operation is robust under distribution shift.

  3. Can you separate the gains over GeoNCO by comparing feasible-output plus Frank-Wolfe, unrestricted-output plus Frank-Wolfe, and the previous decomposition on inputs in its supported domain? If unrestricted inputs cannot be used with the previous decomposition, please make that limitation explicit and compare on their common feasible-input setting.

  4. Does the greedy QAP assignment routine satisfy the delta-relative Frank-Wolfe-gap condition in Corollary 3.4? If so, what delta is justified? If not, please distinguish which feasibility, differentiability, rounding, and convergence statements apply to the reported implementation.

6 comments
AuthorsOpenReview ↗

Response to Reviewer ekuw (1)

We thank the reviewer for the thoughtful comments. The questions on inference cost, projection, and the oracle assumptions led to new ablations and clearer statements in the paper; we respond to each point below.

The single-pass characterization understates the iterative decoding computation and weakens the interpretation of the runtime comparison. The method uses one neural forward pass, but its QAP inference procedure then runs a Frank-Wolfe decoder with T=3000 oracle calls, using greedy assignment at each step and selecting the best resulting permutation. Appendix D.4 shows that both quality and runtime depend materially on this budget. The accurate description is therefore one neural forward pass followed by iterative deterministic decoding. The no-test-time-training protocol is clear, but counting neural forward passes does not by itself control total inference work or isolate the value of the learned representation. Appendix D.3 also notes that some baseline timings are quoted from prior work on different hardware. These qualifications should accompany the headline efficiency claims, with matched end-to-end comparisons where possible.

We agree with this description and have adopted it: QAP inference is one neural forward pass followed by T=3000T=3000 deterministic FW decomposition steps. We have revised the wording in Section 4.2 and Appendix D.2 accordingly. Three points put this decoding in context.

Exploring many feasible solutions is common to these methods, and ours does not call the network to do it. GeoNCO decomposes its output into a set of feasible candidates and returns the best one. SAWT applies 2,000–10,000 improvement steps, visits one feasible permutation per step, and evaluates its network at every step. Our 3,000 candidates come from oracle calls on a fixed network output: the network is evaluated once, with no sampling, search, or parameter updates.

Total inference work is measured end to end. The runtimes reported in the paper are total inference times per instance, not network-pass times. For FWNCO, the 1.56 s in Table 2 already covers the network pass, Sinkhorn, the full T=3000T=3000 decomposition, candidate evaluation, and selection. The same-hardware comparison in our answer to your first question uses the same definition: 0.72 s per instance for FWNCO, against 11.2 s and 50.4 s for SAWT with 2,000 and 10,000 steps. Appendix D.4 also shows that the budget is not critical: T=1000T=1000 already reaches 99.2% of the quality obtained at T=10000T=10000.

Training and inference are aligned. The same decomposition is used during training: the loss is the expected objective over the candidates it produces, and gradients pass through the mixture weights. Training therefore optimizes the objective values of the very candidates from which inference selects. Heatmap-based methods, in contrast, apply their decoding (greedy, MCTS, 2-opt) only at test time. That decoding is itself a combinatorial optimization subroutine, and because it takes no part in training, the network is never optimized for the solutions it finally returns (Appendices E.2 and F).

AuthorsOpenReview ↗

Response to Reviewer ekuw (2)

The practical scope of projection-free operation and the connection between the QAP oracle and the guarantees need clearer evidence. The theory allows unrestricted outputs, and the Maximum Coverage and TSP ablations support removing explicit projection. For QAP, however, the paper reports fragile out-of-distribution behavior and adds 20 Sinkhorn iterations to obtain approximately doubly stochastic outputs. This is a reasonable stabilization, but the paper should distinguish theoretical freedom from projection from empirical success without it. A quantitative QAP ablation is needed to establish how much robustness depends on Sinkhorn. The incremental contribution over GeoNCO would also be clearer with matched combinations of feasible versus unrestricted outputs and the respective decomposition procedures. Finally, Corollary 3.4 assumes a delta-relative Frank-Wolfe-gap oracle. The QAP implementation uses greedy assignment, and it is not established that this routine satisfies that condition on the residual matrices encountered. A guarantee for assignment weight alone would not automatically imply the required gap guarantee. This limits the applicability of the stated convergence bound, while leaving the construction of feasible candidates intact.

We address the three points in our answers in the questions section.

Projection-free operation. We have added the requested QAP ablation by instance class (second answer below, Appendix D.6), and the revised paper now separates the two claims.

Contribution over GeoNCO. The matched comparison of feasible and unrestricted outputs with the two decompositions is in our third answer below.

Greedy oracle for QAP and Corollary 3.4.

We agree with the reviewer that greedy matching is not guaranteed to satisfy Eq. (8). Corollary 3.4 explicitly assumes this relative FW-gap condition Eq. (8). We do not claim that the greedy QAP oracle satisfies this condition or inherits the corollary’s convergence rate. The greedy routine is an empirical choice, and the positive-weight 0.50.5-approximation statement concerns matching scores; it is not used to establish Eq. (8).

Additionally, we have added QAP results using an exact matching oracle, with the same iteration budget and Algorithm 1’s original line search. This variant uses Hungarian assignment at initialization and every subsequent oracle call, and therefore satisfies the exact-oracle requirements of Theorem 3.3. Please see the updated version of Table 2 and updated draft. The variants using exact matching (Hungarian) and approximate matching (greedy) achieve the lowest and second-lowest reported average gaps, respectively, across all evaluated learning-based and classical methods. Both variants also have lower reported runtimes than the other neural baselines.

Compared with FWNCO-Greedy, the Hungarian variant reduces the reported average QAP gap from 26.4% to 24.7%, an improvement of 1.7 percentage points, and reduces the gap in 10 of the 14 classes. The greedy variant reduces inference time from 1.86 to 1.56 seconds per instance, a 16.1% reduction on the hardware of Table 2.

Can you describe QAP inference explicitly as one network pass plus T iterative oracle calls, and compare total inference time and solution quality under matched hardware and compute budgets where possible? Please include Sinkhorn, decomposition, candidate evaluation, and final selection in the timing.

QAP inference consists of one network forward pass, including Sinkhorn normalization, followed by FW decomposition with T = 3000 oracle calls, as in Algorithm 1. We evaluate the original QAP objective on all T resulting permutations and return the best one. The network is evaluated only once.

Timing includes input reading, preprocessing, device transfers, the network pass and Sinkhorn, decomposition, candidate evaluation, final selection, and verification of the returned objective.

To provide additional controlled evidence, 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.

MethodCategory-mean gap (%) ↓Time per instance (s) ↓
SM67.360.0018
RRWM64.230.1683
NGM46.761.8310
SK-JA42.0842.0689
Adapted SAWT, 2000 improvement steps39.3711.1633
Adapted SAWT, 10000 improvement steps35.4950.3622
FWNCO26.340.7184

Our response to Reviewer 82dq provides the code and checkpoint sources, training and evaluation protocols, and QAPLIB-specific implementation details for the baselines.

AuthorsOpenReview ↗

Response to Reviewer ekuw (3)

How much do QAPLIB objective gaps and runtime change when the 20-step Sinkhorn normalization is removed, with the rest of training and decoding held fixed? Reporting the effect by instance class would help establish whether projection-free operation is robust under distribution shift.

We conducted a controlled normalization ablation by training two models one with 20-step Sinkhorn and the other one with elementwise sigmoid without row/column normalization.

QAPLIB classSinkhorn gap (%) ↓Without Sinkhorn gap (%) ↓Sinkhorn time (s/instance) ↓Without Sinkhorn time (s/instance) ↓
bur2.113.300.68380.7067
chr113.96205.910.70210.7276
esc13.6064.940.71560.7437
had2.827.260.70740.7394
kra24.3633.080.72120.7496
lipa13.6214.880.73450.7794
nug10.9719.800.72120.7332
rou10.4119.090.69990.7333
scr27.3841.100.70420.7326
sko15.5218.500.73010.7729
ste83.46108.850.72950.7494
tai20.1630.710.73550.7559
tho21.1528.400.75530.7488
wil9.2010.140.72240.7968
Avg26.3443.280.71840.7441

QAPLIB contains highly heterogeneous instance classes, making generalization from geometric training data challenging. Sinkhorn provides useful structure to the network output: removing it increases the average gap by 16.94 percentage points, although FW continues to produce feasible permutations. Prior methods also address this heterogeneity through category-specific training on QAPLIB: NGM and BiQAP train on instance pools that include their evaluation instances, while RGM trains separate category-specific models using a within-category training/test split. Our model is trained on geometric instances and applied to QAPLIB without category-specific retraining.

Can you separate the gains over GeoNCO by comparing feasible-output plus Frank-Wolfe, unrestricted-output plus Frank-Wolfe, and the previous decomposition on inputs in its supported domain? If unrestricted inputs cannot be used with the previous decomposition, please make that limitation explicit and compare on their common feasible-input setting.

GeoNCO's decomposition requires its input to belong to the feasible polytope. For maximum coverage, this is the hypersimplex: entries lie in [0,1] and sum to k. An input outside this polytope cannot be represented as a convex combination of feasible k-subset vertices. Using unrestricted inputs would therefore violate the assumptions underlying GeoNCO's decomposition and its theoretical guarantees.

We conducted three controlled comparisons:

  • Feasible output + GeoNCO decomposition: apply GeoNCO's output projection and its author-provided decomposition.
  • Feasible output + FW: retain the same output projection and replace the decomposition with FW.
  • Unprojected output + FW: use sigmoid outputs without enforcing the sum-to-k constraint, followed by FW.

All three experiments use the same network architecture and train/test methods. Each configuration is evaluated on the same 100 test instances.

Coverage reports the mean raw weighted-coverage objective (higher is better). Time reports the mean total inference time in seconds per instance (lower is better).

Random500

MethodTime (s, k=10)Coverage (k=10)Time (s, k=50)Coverage (k=50)
Feasible + GeoNCO0.171414642.420.120539320.01
Feasible + FW0.070015110.640.066342003.88
Unprojected + FW0.069415268.300.066241976.96

Random1000

MethodTime (s, k=20)Coverage (k=20)Time (s, k=100)Coverage (k=100)
Feasible + GeoNCO0.194828896.260.158479262.82
Feasible + FW0.094229770.760.093283891.97
Unprojected + FW0.093930177.480.095584039.49

Replacing GeoNCO's decomposition with FW increases mean coverage by 468.22, 2683.87, 874.50, and 4629.15, respectively, while achieving a 1.70–2.45× speedup. Thus, the decomposition itself improves both solution quality and runtime while retaining the output projection.

Removing the projection within FW changes mean coverage by +157.66, −26.92, +406.72, and +147.52, respectively. The larger gains come from replacing the decomposition; removing the projection provides a smaller additional quality benefit in three of the four configurations.

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

The authors propose a general framework that allows a neural network to predict an arbitrary continuous vector. Its central mechanism maps arbitrary continuous network outputs to a sparse mixture of feasible discrete solutions through a finite number of Frank–Wolfe decomposition steps. Training uses the expected discrete objective of the candidate solutions together with a reconstruction regularizer, without requiring optimal-solution labels. Under the assumption of stable oracle decisions, the mixture coefficients are differentiable almost everywhere. At inference, the best solution in the candidate set is selected, guaranteeing an objective value no worse than the mixture's expectation. The paper provides a geometric convergence analysis for exact oracles and approximate oracles satisfying a relative FW-gap condition, and evaluates the method on MC, QAP, and TSP using spanning-tree and matching components.

Critical strengths

S1. Feasibility and the training objective are connected through the same decomposition mechanism. Each candidate is already a feasible discrete solution, so training can evaluate the discrete objective directly, and inference can reuse the same candidate set. This reduces the burden of designing a separate differentiable surrogate loss and rounding procedure for each objective. A fixed oracle budget also provides a direct way to control computational cost. (pp. 4–6)

S2. The empirical evaluation across problems and the existing ablations are valuable. MC, QAP, and TSP involve different objectives and structures, and the TSP experiments also demonstrate joint learning with spanning-tree and matching modules. The ablations on projection, decomposition budget, transfer across problem sizes, and matching show that the authors consider more than a single favorable configuration. Comparisons with GreedyTrap and several neural baselines also indicate potential. (§4, Appendices C–G)

Critical weaknesses

W1. The approximation guarantee for greedy matching in QAP does not establish the applicability of the FW convergence theorem

Corollary 3.4 requires the direction selected at each step to achieve a linear improvement over the current point that is at least a specified fraction of the improvement achieved by the best direction (Eq. (8)). However, QAP uses greedy matching. The 0.5-approximation guarantee cited in the appendix states that, for positive weights, the total matching score is at least half the optimal total score. A total score close to optimal does not imply sufficient improvement over the current point. Therefore, this matching approximation guarantee does not directly imply the condition required by the theorem.

The residual weights may also be negative. Even shifting all weights by the same constant to make them nonnegative does not establish the guarantee in Eq. (8). In a counterexample involving a 3×3 doubly stochastic matrix, the standard greedy rule of selecting the largest remaining edge at each step yields a linear improvement (FW gap) of −0.022, whereas an exact solution yields 0.118. Under the original update rule, the step size for the greedy direction becomes 0 (see §5.2 of this preliminary review for the construction). This shows that the existing argument does not establish the theorem's applicability to this greedy method; it does not show that the core theorem itself is incorrect. In addition, the TSP appendix introduces an entropy mechanism without clarifying whether it merely adds a training loss term or changes the FW step sizes or mixture weights. If it changes the update procedure, the proof for Algorithm 1 cannot be applied directly. The paper needs to state the actual training objective explicitly and clarify which theoretical results apply to the methods used in the experiments. (pp. 6, 20, 22, 29)

W2. Some experimental details are inconsistent with the descriptions in the main text

  1. The training conditions and averaging procedures in the QAP comparison are not consistent. Table 2 states that all models are pretrained on QAP32, but the cited SAWT results come from QAP50. Appendix D.3 also states that the runtimes of some baselines were obtained on different hardware. The table reports gaps of 26.4% versus 26.8%; equally weighting the results across the 14 categories instead gives 26.407 versus 26.457. This does not necessarily mean that the numbers were calculated incorrectly, but the paper needs to explain how the averages were computed. Without consistent test instances and aggregation procedures, the magnitude of the solution-quality advantage is difficult to assess. Runtimes measured on different hardware also do not directly establish a speed advantage. (p. 8, Table 2; p. 21, D.3; Table 2 in the original SAWT paper)

  2. The descriptions of the TSP matching algorithm in the main text and appendix do not agree. The main text states that minimum-weight perfect matching is used (p. 8, lines 421–424), whereas the appendix states that greedy matching is used by default (p. 25, lines 1307–1312). Greedy matching does not guarantee minimum weight. The paper needs to clarify which method was actually used for the tabulated results and which theoretical conclusions apply to it.

  3. Claims of consistent superiority are contradicted by counterexamples in the tables. The MC discussion claims that the method is consistently on the Pareto frontier. However, on Rail with k=50, RL achieves a coverage value of 7456.67, higher than the proposed method's 7393, and takes 0.219s, less than the proposed method's 1.931s. Thus, RL provides both better solution quality and faster execution in this setting. The TSP discussion claims that the method consistently outperforms unsupervised neural baselines, including RL, but on TSP50, Sym-NCO achieves a gap of 1.23%, better than the proposed method's 1.81% and 1.40%. These claims should be restricted to the settings actually supported by the tables. (pp. 7, 9; Tables 1 and 3)

W3. The comparison with related work is insufficient

SparseMAP (2018) already includes the same quadratic optimization problem and allows differentiation through an output supported on a small number of discrete solutions. DFWLayer (2023) already constructs a differentiable optimization layer by unrolling FW steps. GeoNCO and BE already involve distributions over feasible solutions, average objectives, and rounding guarantees. The paper therefore needs to clarify what each of the following design choices adds: finite-step decomposition, gradient propagation through mixture weights, and allowing temporarily infeasible inputs. BE, which is already cited, should also be prioritized for inclusion in the QAP comparison to assess the proposed method's improvements. More recent works, PLUME (2025-03-25), Structure As Search (2025-07-05), and C2TSP (2026-07-13), study self-supervised QAP, direct generation of feasible TSP solutions, and learning distributions over TSP structures, respectively. None is cited or compared in this manuscript. Additional discussion is recommended.

Questions for authors

Please focus primarily on weaknesses W1–W3.

  1. What is the exact rule used for greedy assignment in the implementation, and does it satisfy Eq. (8)? If this cannot be guaranteed, could you explicitly delimit the scope of Corollary 3.4 and provide a comparison with an exact Hungarian oracle under the same time budget?
  2. In which equation is the entropy mechanism introduced, and does it change the FW step sizes or mixture weights? Does the base variant in the main table use exact minimum-weight matching or greedy matching, and which theoretical guarantees apply to that configuration?
  3. Could you provide a common QAP instance list, the aggregation formula for Avg, the actual training problem sizes of all baselines, and runtimes measured on the same hardware, and then reassess the quality and speed advantages accordingly? Please also revise the uses of "consistently" in the MC and TSP discussions that go beyond what the tables support.
  4. What new properties and mechanisms does this paper introduce relative to SparseMAP, DFWLayer, GeoNCO, and BE? Could you add a controlled comparison with BE or an adapted version of one of the recent closely related methods listed above, while distinguishing the budgets for direct decoding, selecting the best candidate, and additional search?
8 comments
AuthorsOpenReview ↗

Response to Reviewer 82dq (1)

We thank the reviewer for the detailed and careful review; we respond to each point below.

W1. The approximation guarantee for greedy matching in QAP does not establish the applicability of the FW convergence theorem Corollary 3.4 requires the direction selected at each step to achieve a linear improvement over the current point that is at least a specified fraction of the improvement achieved by the best direction (Eq. (8)). However, QAP uses greedy matching. The 0.5-approximation guarantee cited in the appendix states that, for positive weights, the total matching score is at least half the optimal total score. A total score close to optimal does not imply sufficient improvement over the current point. Therefore, this matching approximation guarantee does not directly imply the condition required by the theorem. The residual weights may also be negative. Even shifting all weights by the same constant to make them nonnegative does not establish the guarantee in Eq. (8). In a counterexample involving a 3×3 doubly stochastic matrix, the standard greedy rule of selecting the largest remaining edge at each step yields a linear improvement (FW gap) of −0.022, whereas an exact solution yields 0.118. Under the original update rule, the step size for the greedy direction becomes 0 (see §5.2 of this preliminary review for the construction). This shows that the existing argument does not establish the theorem's applicability to this greedy method; it does not show that the core theorem itself is incorrect.

We agree with the reviewer that greedy matching is not guaranteed to satisfy Eq. (8). Corollary 3.4 explicitly assumes this relative FW-gap condition Eq. (8). We do not claim that the greedy QAP oracle satisfies this condition or inherits the corollary’s convergence rate. The greedy routine is an empirical choice, and the positive-weight 0.50.5-approximation statement concerns matching scores; it is not used to establish Eq. (8).

The review correctly distinguishes these approximation notions. Its counterexample therefore demonstrates why the convergence guarantee cannot automatically be extended to greedy matching, a guarantee we have not asserted. Feasibility and the best-support rounding guarantee remain valid independently of Eq. (8).

For completeness, we have added QAP results using an exact matching oracle, with the same iteration budget and Algorithm 1’s original line search. This variant uses Hungarian assignment at initialization and every subsequent oracle call, and therefore satisfies the exact-oracle requirements of Theorem 3.3.

Both variants use the same trained checkpoint on the same 108 QAPLIB instances of sizes 12–64 across 14 categories. Both are evaluated on an AMD Ryzen 9 9950X CPU and an NVIDIA RTX 4090 GPU. Gap is the equally weighted mean of the category-level mean gaps; time is the mean end-to-end inference time per instance, including preprocessing, transfers, network inference, Sinkhorn normalization, decomposition, candidate evaluation, final selection, and objective verification.

MethodCategory-mean gap (%) ↓Total time per instance (s) ↓
FWNCO-Greedy26.340.7184
FWNCO-Hungarian24.740.8474

Replacing Greedy with the exact Hungarian oracle reduces the category-mean gap by 1.60 percentage points, with an 18.0% increase in total inference time, using the same checkpoint without retraining. We have updated the text, including Appendix D.4 and the matching-oracle discussion, to explicitly state that the convergence bound is not established for the greedy implementation.

AuthorsOpenReview ↗

Response to Reviewer 82dq (2)

In addition, the TSP appendix introduces an entropy mechanism without clarifying whether it merely adds a training loss term or changes the FW step sizes or mixture weights. If it changes the update procedure, the proof for Algorithm 1 cannot be applied directly. The paper needs to state the actual training objective explicitly and clarify which theoretical results apply to the methods used in the experiments. (pp. 6, 20, 22, 29)

Thank you for your comment. The entropy-regularized line search is an empirical choice for TSP. Section 3.1 explicitly notes that several step-size choices are possible.

We have revised the text to specify the line-search objective and its numerical computation. Specifically, our variant retains the exact spanning-tree oracle. Given the current coefficients α(t−1)\boldsymbol\alpha^{(t-1)}, it approximately minimizes, over γ∈[0,1]\gamma\in[0,1],

-\tau H\bigl((1-\gamma)\boldsymbol\alpha^{(t-1)},\gamma\bigr), \qquad H(a)=-\sum_i a_i\log a_i.$$ Thus, entropy changes the step size and mixture weights; through the next residual, it can also change subsequent selected trees. Entropy is computed over coefficient entries, with repeated trees retained separately. The implementation uses $\tau=2$ and 20 Newton iterations in the logit variable. **The outer training objective remains the expected tour length plus the reconstruction loss. Entropy enters only the inner line search**, through which we differentiate the outer objective. Theorem 3.3 does not directly apply to this modified line search, and we do not claim its convergence rate for the entropy variant. We have revised Appendix E.1 to specify the procedure and clarify this distinction. We evaluated three TSP inference settings: greedy matching with entropy-regularized line search, greedy matching without entropy, and exact matching without entropy. The two variants without entropy use Algorithm 1’s original line search and the exact spanning-tree oracle, so their FW decompositions satisfy the setup of Theorem 3.3 for the reconstruction objective. All experiments below were conducted on the same machine with an AMD Ryzen 9 9950X CPU and an NVIDIA RTX 4090 GPU. Greedy matching without entropy is fastest at every scale. Adding entropy yields modest gap reductions of 0.05–0.30 percentage points on TSP50–500, but increases runtime and does not improve the gap on TSP1000. Exact matching achieves the lowest gaps across all four datasets. Compared with greedy matching without entropy, it reduces the gap by 1.96 and 2.23 percentage points on TSP500 and TSP1000, respectively, but requires approximately 10.6 and 26.2 times the runtime. **Mean gap (%), averaged over instances; lower is better.** | Dataset | Greedy, with entropy | Greedy, without entropy | Exact matching, without entropy | |---|---:|---:|---:| | TSP50 | 1.81 | 1.86 | **1.525** | | TSP100 | 3.48 | 3.66 | **3.043** | | TSP500 | 7.30 | 7.60 | **5.637** | | TSP1000 | 8.27 | 8.23 | **5.999** | **Mean end-to-end time (seconds per instance); lower is better.** | Dataset | Greedy, with entropy | Greedy, without entropy | Exact matching, without entropy | |---|---:|---:|---:| | TSP50 | 0.185 | **0.062** | 0.104 | | TSP100 | 0.224 | **0.095** | 0.266 | | TSP500 | 1.280 | **1.155** | 12.276 | | TSP1000 | 5.627 | **5.537** | 145.185 |
AuthorsOpenReview ↗

Response to Reviewer 82dq (3)

W2. Some experimental details are inconsistent with the descriptions in the main text

  1. The training conditions and averaging procedures in the QAP comparison are not consistent. Table 2 states that all models are pretrained on QAP32, but the cited SAWT results come from QAP50. Appendix D.3 also states that the runtimes of some baselines were obtained on different hardware. The table reports gaps of 26.4% versus 26.8%; equally weighting the results across the 14 categories instead gives 26.407 versus 26.457. This does not necessarily mean that the numbers were calculated incorrectly, but the paper needs to explain how the averages were computed. Without consistent test instances and aggregation procedures, the magnitude of the solution-quality advantage is difficult to assess. Runtimes measured on different hardware also do not directly establish a speed advantage. (p. 8, Table 2; p. 21, D.3; Table 2 in the original SAWT paper)

Thank you for identifying these inconsistencies. We address the three points separately.

1. QAP training sizes, aggregation, and runtime comparison.

The SAWT values in Table 2, including its average of 26.8%, are quoted from Table 2 of Tan and Mu (2024). We agree with your computation: the 14 displayed class means average to 26.407% for FWNCO and 26.457% for SAWT. Rounding accounts for our 26.4% but not for SAWT’s published 26.8%. Furthermore, recomputing the percentage gaps from the per-instance objective and reference values in SAWT’s Table 13, using the 14 reported classes within the stated size range of 12–64 and averaging equally across classes, yields 27.03%, which differs from both 26.457% and 26.8%. Some per-instance gaps also disagree with their listed objective and reference values: esc32g has a reference value of 6 and a reported objective of 10, giving a gap of 66.67%, whereas Table 13 reports 63.3%.

We therefore do not treat the published 0.4-percentage-point difference as evidence of a solution-quality advantage. We have removed the statement that all models are pretrained on QAP32 from the caption of Table 2; Appendix D.5 now gives the training setup of each baseline.

To provide additional controlled evidence, 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.

MethodCategory-mean gap (%) ↓Time per instance (s) ↓
SM67.360.0018
RRWM64.230.1683
NGM46.761.8310
SK-JA42.0842.0689
Adapted SAWT, 2000 improvement steps39.3711.1633
Adapted SAWT, 10000 improvement steps35.4950.3622
FWNCO26.340.7184

Our same-hardware numbers differ from the published ones (e.g., adapted SAWT at 35.49% against the published 26.8%). We cannot trace this difference, because the QAPLIB evaluation code behind the published results is not released, and the published aggregates are not internally consistent: for every baseline row, the printed Avg differs from the mean of the printed class values (SM 181.2 vs 131.7, RRWM 169.5 vs 141.7, SK-JA 93.2 vs 54.9, NGM 62.4 vs 45.8, RGM 35.8 vs 31.9, SAWT 26.8 vs 26.5). We therefore report our measurements alongside the published values and do not treat either as authoritative. We have added these results in Appendix D.5 of the revised paper.

The code and checkpoint sources are as follows:

  • SM and RRWM: We use the algorithms from pygmtools, version 0.6.0, using matrix-free affinity operations followed by Hungarian discretization.

  • SAWT: We use the publicly released models/pg-QAP50.pt checkpoint from the official repository. Since the release does not include QAPLIB-specific evaluation code, we adapt its input processing and evaluation loop to QAPLIB. Coordinate features are constructed from the input matrices, while the 2000-step and 10000-step swap searches and final verification use the original QAP objective.

(response continued in the following comment)

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.