acceptodds
Under review as a conference paper at ICLR 2027

Fast and Parallel Algorithm for Neural Combinatorial Optimization with Constraints

Abstract

Self-supervised learning for combinatorial optimization offers a promising way to train neural solvers without requiring optimal solutions as supervision. This requires informative gradients while respecting discrete feasibility. Recent geometric approaches use Carath\'eodory decompositions to decompose a neural network output into a distribution over feasible solutions, but the resulting decomposition procedures can be sequential and computationally expensive. We propose a parallel alternative based on linear optimization oracles. A neural network generates multiple query directions, whose samples are passed independently through the oracle to produce feasible solutions in parallel. We then obtain a probability distribution over these feasible solutions through a regularized simplex-constrained quadratic program and use its KKT conditions to derive the gradients of the designed loss, without differentiating through the discrete oracle. The resulting method relies mainly on parallel oracle calls and GPU-friendly linear algebra. Experiments across constrained combinatorial optimization problems show that it produces high-quality feasible solutions while substantially reducing the computational cost of decomposition-based self-supervised learning.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Constraints, Self-supervised Learning, Parallel Caratheodory 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_2USDOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a self-supervised framework for constrained neural combinatorial optimization using the LMOs in parallel. Instead of sequentially decomposing a neural prediction into feasible vertices, the network generates multiple query directions q1,…,qmq_1,\dots,q_m, which are independently passed through LMOs to obtain feasible candidates v1,…,vmv_1,\dots,v_m. The mean query $ x_\theta=\frac{1}{m}\sum_{i=1}^m q_i$ is then associated (but not decomposed) with a probability vector over the generated candidates by solving a regularized simplex-constrained quadratic program. Gradients are obtained from the corresponding KKT system without differentiating through the discrete LMO.

Critical strengths
  • Simple but useful parallelization idea: Independent LMO calls remove an important sequential bottleneck of previous decomposition-based methods. The inference procedure is especially efficient: generate feasible solutions in parallel and directly select the best candidate.

  • Broad empirical applicability: The framework is demonstrated on several structurally different combinatorial optimization problems. The reported experimental results are promising.

Critical weaknesses
  • The loss is not naturally a global function of xθx_\theta alone: The actual state is the full query tuple Q=(q1,…,qm)Q=(q_1,\ldots,q_m), since x(Q)=1m∑iqix(Q)=\frac{1}{m}\sum_i q_i and V(Q)=[LMO(q1),…,LMO(qm)]V(Q)=[\mathrm{LMO}(q_1),\ldots,\mathrm{LMO}(q_m)]. Two query collections can have the same mean xx while generating completely different candidate sets VV. Therefore, the more faithful formulation seems to be L(Q)=FV(Q)(x(Q))L(Q)=F_{V(Q)}(x(Q)), rather than a globally well-defined function F(x)F(x). Proposition 1 establishes local gradient correctness when V(Q)V(Q) remains fixed, but this is weaker than establishing a globally meaningful extension over xθx_\theta.

  • The mean aggregation introduces a large local nullspace and weak query-specific credit assignment: Within a region where VV is fixed, the loss depends on the queries only through x=1m∑iqix=\frac{1}{m}\sum_i q_i. Therefore, ∇qiL=1m∇xFV(x)\nabla_{q_i}L=\frac{1}{m}\nabla_x F_V(x) for every ii. Any perturbation satisfying ∑iδqi=0\sum_i \delta q_i=0 is thus locally invisible to the gradient. This defines an n(m−1)n(m-1)-dimensional nullspace. However, such zero-mean perturbations can substantially change individual queries and eventually move them across different LMO regions, thereby changing the generated candidates. Hence, the directions that control candidate diversity can be precisely the directions that receive no first-order training signal. So I think using some different aggregations may be important.

  • The geometric and probabilistic interpretation is weaker than in previous decomposition-based methods: In previous geometric approaches, the coefficients describe a probability distribution arising from a decomposition of the neural output itself. Here, the candidates v1,…,vmv_1,\ldots,v_m are generated independently first, and the QP subsequently projects xθx_\theta onto their restricted convex hull. There is no guarantee that xθx_\theta is close to conv{v1,…,vm}\mathrm{conv}\{v_1,\ldots,v_m\}. If xθx_\theta is far from this hull, the QP still returns a probability vector α\alpha, but its interpretation becomes less convincing: it is merely the best regularized projection onto a potentially unrelated candidate set. This may weaken both interpretability and reliability of the training signal. I would like to see the residual ∥xθ−Vα(xθ)∥\|x_\theta-V\alpha(x_\theta)\| reported and analyzed empirically.

Some Minor Suggestions:

  • The theoretical assumptions and some experimental oracle choices are not fully aligned: Proposition 1 assumes a deterministic, locally stable LMO with fixed tie-breaking, while the framework also allows approximate LMOs and some experiments use heuristic or approximate oracle procedures. It would be helpful to state clearly which experimental settings satisfy the assumptions of Proposition 1 and which fall outside the current theoretical guarantee.

  • In line 44, the "both..and" seems confusing, I guess it's a typo?

  • State the representation power of the method directly, i.e., share the same optimal solution as the original problem.

Questions for authors
  1. How do the authors interpret the n(m−1)n(m-1)-dimensional zero-mean nullspace induced by xθ=1m∑iqix_\theta=\frac{1}{m}\sum_i q_i? In particular, what mechanism provides query-specific credit assignment for changing candidate diversity? (Randomness? different aggregations?)

  2. How large is the projection residual ∥xθ−Vα(xθ)∥\|x_\theta-V\alpha(x_\theta)\| during training? Is this quantity correlated with training stability or solution quality?

  3. I would like to increase my score if two of the critical weaknesses above are addressed. I think it serves as a good empirical framework and would like to recommend acceptance if the weaknesses are addressed.

6 comments
AuthorsOpenReview ↗

Response to Reviewer 2USD - I

We thank the reviewer for the thoughtful feedback and positive assessment of our work. We updated the manuscript significantly and address the reviewer's concerns in detail below.

The loss is not naturally a global function of xθx_\theta alone: The actual state is the full query tuple Q=(q1,…,qm)Q = (q_1, \ldots, q_m), since x(Q)=1m∑iqix(Q) = \frac{1}{m}\sum_i q_i and V(Q)=[LMO⁡(q1),…,LMO⁡(qm)]V(Q) = [\operatorname{LMO}(q_1), \ldots, \operatorname{LMO}(q_m)]. Two query collections can have the same mean xx while generating completely different candidate sets VV. Therefore, the more faithful formulation seems to be L(Q)=FV(Q)(x(Q))L(Q) = F_{V(Q)}(x(Q)), rather than a globally well-defined function F(x)F(x). Proposition 1 establishes local gradient correctness when V(Q)V(Q) remains fixed, but this is weaker than establishing a globally meaningful extension over xθx_\theta.

We thank the reviewer for this observation. We agree that the full training objective is more precisely written as L(Q)=FV(Q)(x(Q))L(Q)=F_{V(Q)}(x(Q)). This dependence is already reflected in our notation FV(xθ)F_V(x_\theta) in Eq. (4), and Section 3 explicitly describes our construction as a local surrogate extension. We do not claim a globally defined extension depending only on xθx_\theta.

Importantly, under the local stability assumption in Proposition 1, V(Q)V(Q) remains constant in a neighborhood almost everywhere. Therefore, the gradient of the full objective satisfies ∇qiL(Q)=1m∇xFV(Q)(x(Q))\nabla_{q_i}L(Q)=\frac{1}{m}\nabla_x F_{V(Q)}(x(Q)). Hence, our KKT-based computation gives the exact gradient of the actual training objective almost everywhere, without requiring a global extension over xθx_\theta.

We have updated the manuscript to explicitly state the query-dependent objective and clarify the scope of Proposition 1.

AuthorsOpenReview ↗

Response to Reviewer 2USD - II

The mean aggregation introduces a large local nullspace and weak query-specific credit assignment: Within a region where VV is fixed, the loss depends on the queries only through x=1m∑iqix = \frac{1}{m}\sum_i q_i. Therefore, ∇qiL=1m∇xFV(x)\nabla_{q_i} L = \frac{1}{m}\nabla_x F_V(x) for every ii. Any perturbation satisfying ∑iδqi=0\sum_i \delta q_i = 0 is thus locally invisible to the gradient. This defines an n(m−1)n(m-1)-dimensional nullspace. However, such zero-mean perturbations can substantially change individual queries and eventually move them across different LMO regions, thereby changing the generated candidates. Hence, the directions that control candidate diversity can be precisely the directions that receive no first-order training signal. So I think using some different aggregations may be important. How do the authors interpret the n(m−1)n(m-1)-dimensional zero-mean nullspace induced by xθ=1m∑iqix_\theta = \frac{1}{m}\sum_i q_i? In particular, what mechanism provides query-specific credit assignment for changing candidate diversity?(Randomness? different aggregations?)

We agree that mean aggregation introduces a local nullspace. However, this does not imply that the network receives a zero gradient or that different queries cannot explore distinct candidate regions. When VV remains locally fixed, the chain rule gives

∇qiL=1m∇xθFV(xθ),\nabla_{q_i}L=\frac{1}{m}\nabla_{x_\theta}F_V(x_\theta),

and consequently,

\frac{1}{m}\sum_{i=1}^{m} \left(\frac{\partial q_i}{\partial\theta}\right)^\top \nabla_{x_\theta}F_V(x_\theta).$$ Thus, **although the gradients with respect to individual queries are identical, their contributions to the network parameter gradient can differ through their respective Jacobians**. Moreover, Gaussian sampling and Sobol directions encourage exploration of different LMO regions, allowing diverse feasible candidates to be generated. Importantly, **the mean is a design choice, not a restriction of our framework**. As noted in Section 3, any differentiable aggregation rule $x_\theta=g(q_1,\ldots,q_m)$ can be used. For instance, a weighted aggregation $x_\theta=\sum_i w_iq_i$ would provide different gradient weights to individual queries. More generally, reducing $m$ query vectors to a single $n$-dimensional representation necessarily introduces a local nullspace, regardless of the aggregation rule. In practice, **simple averaging already achieves strong empirical results across our benchmarks**, without additional complexity. We have updated the manuscript to clarify these points and discuss alternative aggregations as a direction for improving query-specific credit assignment. To further assess the reliability of these design choices, we conducted additional controlled experiments examining the effects of removing Gaussian sampling and changing the aggregation rule. We implement a direct variant of our method, in which the neural network directly outputs the query vectors without Gaussian sampling. This variant tests whether the learned query generator itself can maintain candidate diversity without relying on injected Gaussian noise. For learnable aggregation, a shared scoring network assigns a scalar score to each query based on its normalized statistics. Softmax converts these scores into weights, giving $x=\sum_i w_i(Q)q_i$. The scorer adds 96 trainable parameters and is initialized to uniform weights, so training starts from mean aggregation. It is optimized jointly with the query generator, introducing query-dependent gradient paths through both the weights and the queries. | Query generation | Aggregation | MC coverage ↑ | QAP mean class gap (%) ↓ | |---|---|---:|---:| | Gaussian | Mean | 29932.85 | 26.39 | | Gaussian | Learned | **30045.10** | **25.84** | | Direct | Mean | 29950.36 | 26.61 | Learnable aggregation improves MC coverage by 0.375% and reduces the QAP gap by 0.550% relative to mean aggregation. Direct variant achieves slightly higher MC coverage than Gaussian generation, But scored a worse QAP gap. These results demonstrate the practicality of alternative aggregations. We favor Gaussian query generation for its scalability and flexible candidate budget. Once the network predicts the distribution parameters, additional queries can be generated through parallel sampling while reusing those parameters and the encoded instance representation. This allows the candidate budget to grow without adding a separate learned output for every additional query, making the approach well suited to large instances and large candidate pools. We retain mean aggregation as a practical trade-off between solution quality and time. Mean aggregation requires only a simple reduction, whereas learnable aggregation adds a scoring network. Given the modest quality gains observed here, mean aggregation provides an efficient default.
AuthorsOpenReview ↗

Response to Reviewer 2USD - III

The geometric and probabilistic interpretation is weaker than in previous decomposition-based methods: In previous geometric approaches, the coefficients describe a probability distribution arising from a decomposition of the neural output itself. Here, the candidates v1,…,vmv_1, \ldots, v_m are generated independently first, and the QP ... that xθx_\theta is close to conv⁡{v1,…,vm}\operatorname{conv}\{v_1, \ldots, v_m\}. If xθx_\theta is far from this hull, the QP still returns a probability vector α\alpha, but its interpretation becomes less convincing: it is merely the best regularized projection onto a potentially unrelated candidate set. This may weaken both interpretability and reliability of the training signal. I would like to see the residual ∥xθ−Vα(xθ)∥\|x_\theta - V\alpha(x_\theta)\| reported and analyzed empirically.

Our approach constructs a probability distribution over feasible candidates generated in parallel, without requiring an exact decomposition of xθx_\theta. The coefficients remain valid probabilities since α∈Δm\alpha\in\Delta_m, regardless of whether xθx_\theta lies inside conv⁡(V)\operatorname{conv}(V). Moreover, Proposition 1 does not require the projection residual to be small.

This also removes a restriction of previous decomposition-based methods, such as Karalias et al. (2025), which require the neural network output to lie within the feasible polytope. Enforcing this condition can require additional, problem-specific constructions, particularly for more complex polytopes such as matroid and spanning-tree polytopes. Our framework avoids this requirement while preserving feasibility through the LMOs.

Importantly, the projection residual is not necessarily indicative of solution quality. For an exact LMO, scaling all queries by c>0c>0 leaves the generated candidates unchanged, i.e., LMO⁡(cqi)=LMO⁡(qi)\operatorname{LMO}(cq_i)=\operatorname{LMO}(q_i), while the residual ∥xθ−Vα(xθ)∥\|x_\theta-V\alpha(x_\theta)\| can grow arbitrarily large. Conversely, a small residual does not guarantee high-quality candidates. Our method directly optimizes a surrogate over the generated solutions during training and selects the best feasible candidate at inference.

We have updated the manuscript to clarify this interpretation and the role of the projection residual in our framework.

An aggregate xθx_\theta far from the candidate hull can still correspond to queries that lead the LMO to high-quality feasible solutions. Likewise, an aggregate close to or inside the hull can correspond to solutions with different objective values. The geometric position of xθx_\theta therefore provides limited information about the optimization outcomes associated with the queries.

To assess whether training guides the queries toward better feasible solutions, we track the mean objective value of their LMO solutions together with our combinatorial loss. Let vi=LMO⁡(qi)v_i=\operatorname{LMO}(q_i). We compute

f‾LMO=1m∑i=1mf(vi),FV(xθ):=∑i=1mαi(xθ)f(vi).\begin{aligned}\overline{f}_{\mathrm{LMO}}&=\frac{1}{m}\sum_{i=1}^{m}f(v_i),\\ F_V(x_\theta)&:=\sum_{i=1}^{m}\alpha_i(x_\theta)f(v_i).\end{aligned}

The mean LMO objective gives each query equal weight and measures the average quality of the generated feasible solutions. The loss weights these same solutions using the coefficients returned by the QP. Tracking both quantities allows us to examine how optimizing the weighted objective translates into improvements in the quality of the query set.

Figures 6 and 7 in the updated draft show these quantities together with the projection residual throughout training. For MC, MaxCut, and DkS, the plotted weighted objective corresponds to the negative combinatorial loss, so higher values indicate better solutions. For QAP, it corresponds to the combinatorial loss itself, with lower values indicating better solutions. Across these experiments, the mean LMO objective quality improves alongside the weighted objective under different residual behaviors. This provides empirical evidence that the training updates guide the queries toward better feasible solutions, including when the projection residual remains large or fluctuates.

  • MC: Mean coverage and the negative combinatorial loss increase and then stabilize, while the projection residual increases before leveling off.
  • MaxCut: The mean normalized cut and the negative combinatorial loss improve overall, while the projection residual decreases toward zero.
  • DkS: Mean density and the negative combinatorial loss increase, while the projection residual also increases overall.
  • QAP: Both mean cost and the combinatorial loss decrease, while the projection residual shows a substantial overall increase.

These observations provide empirical support that the training signal improves the objective quality of the solutions associated with the network's queries. Such improvements occur across different residual behaviors, consistent with the theoretical result accommodating aggregates both inside and outside the polytope.

Reviewer_67oCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

In this paper the authors propose an NCO algorithm that follows self-supervised learning rule for constrained combinatorial optimization. Moreover, the algorithm contributes with advancements in the efficiency of self-supervised learning.

Critical strengths
  • The paper addresses an aspect that is very relevant in NCO, that is, efficiency.
  • The paper is not focused only in obtaining better results than previous counterparts, but tries to give relevant mathematical machinery in CO to support the proposal.
Critical weaknesses
  • One of the premises on which this work is based is that there exists a neural solver whose performance is competitive with state-of-the-art algorithms for many combinatorial optimisation problems. In my view, this premise is not true, or at least that is what the no-free-lunch theorem (Wolpert and McReady, 2011) suggests. If we take this idea to its extreme, is there a single model that is optimal for any optimisation problem? The answer is no; in fact, it is not true even for a single problem. Is there a model that is the best for any instance of the problem? Once again, the answer is no. Whilst this does not invalidate the work, I believe it is necessary to reword this point in the introduction.

  • The authors note that usual techniques to handle restrictions in NCO imply problem-specific loss designs. However, I would say that those extensions that deal with the discrete objetive constructed from geometry of the feasible set do so too. I request clarification in this point.

  • When self-supervision is described in the introduction, it is not clear what is the difference with respecto to pure RL. In fact, supervised approaches in NCO are not majority, RL is the majority. So it is not clear what the motivation is.

  • The motivation in the abstract and introduction is not clear enough. What is the aim of this project? What is the intended outcome of the improvements proposed in this project?

  • The algorithms included in the experimentation do not include some important algorithms. For instance, in the QAP, Robust Tabu Search (RoTS) has been for decades one of the best algorithms (metaheuristic in this case) for optimization instances of the QAP. My concern regarding the experimentation is that the reference algorithms used to scale the Y-axis of the plots can be further improved. I am aware that the efficiency is the scope of the paper, however if we do not set the Y-axis correctly, we may give the mistaken impression that the proposed algorithm is one of the most competitive algorithms available, which may be completely incorrect. I request including the reference algorithms for each problem (going beyond NCO).

  • The idea of working in the arena of polytopes sounds good, however, I think more insights should be given to the reader. For instance, sentences such as "admit efficient linear optimization over P" is not clear enough. If optimizing linearly over P is optimum, then... is the problem NP-hard? Please provide more insights in this regard. The same lack of insights is observed two paragraphs below in "Self-Supervised CO and traning". Please, improve this part as well.

  • The paper is hard to read. I understand the limitation of pages, however, for a CO researcher that is not familiarized with the idea of optimizing in the polytope of the problem, might find the explanations in the abstract and introduction hard to understand. For the same reason, then in section 2 it feels that the paper goes very fast on the background that is key to understand the proposal. If the experimental part is devoted to validate the algorithm, I would reduce it to 1-2 pages at most, and dedicate more space to sections 2-3.

Questions for authors

Address my doubts/question/requests in the weaknesses.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 67oC - I

We thank the reviewer for the constructive feedback. We have revised the manuscript to address the concerns and clarify the motivation, theoretical foundations, and methodology.

One of the premises on which this work is based is that there exists a neural solver whose performance is competitive with state-of-the-art algorithms for many combinatorial optimisation problems. In my view, this premise is not true, or at least that is what the no-free-lunch theorem (Wolpert and McReady, 2011) suggests. If we take this idea to its extreme, is there a single model that is optimal for any optimisation problem? The answer is no; in fact, it is not true even for a single problem. Is there a model that is the best for any instance of the problem? Once again, the answer is no. Whilst this does not invalidate the work, I believe it is necessary to reword this point in the introduction.

The no-free-lunch theorem concerns performance averaged over all possible objective functions and does not rule out effective solvers for specific structured problems or instance distributions. This is also reflected in the success of deep learning across diverse tasks, such as computer vision and natural language processing, where models are trained separately for their respective tasks.

Similarly, our framework does not assume a single universal neural solver. We train a separate model for each combinatorial optimization problem, using problem-specific architectures and LMOs. Our contribution is a general training framework that improves computational efficiency while maintaining competitive solution quality across different problems.

The authors note that usual techniques to handle restrictions in NCO imply problem-specific loss designs. However, I would say that those extensions that deal with the discrete objetive constructed from geometry of the feasible set do so too. I request clarification in this point.

We agree that geometric extension methods can also require problem-specific constructions. However, there is an important distinction between problem-specific loss design and problem-specific decomposition procedures. Our discussion of loss design refers primarily to approaches requiring tailored penalty terms or constraint-handling objectives.

Geometric methods generally construct losses from the original discrete objective, but may rely on specialized decomposition algorithms. Our framework uses the same QP-based loss and gradient computation across different combinatorial problems, requiring only a suitable problem-specific LMO.

When self-supervision is described in the introduction, it is not clear what is the difference with respecto to pure RL. In fact, supervised approaches in NCO are not majority, RL is the majority. So it is not clear what the motivation is. The motivation in the abstract and introduction is not clear enough. What is the aim of this project? What is the intended outcome of the improvements proposed in this project?

We agree that RL is widely used in NCO and, like self-supervised approaches, does not require optimal solution labels. The main distinction lies in how training gradients are obtained and constraints are handled. Many RL-based methods rely on policy-gradient estimators, which can have high variance, and may require problem-specific reward penalties, action constraints, or solution-repair procedures such as rounding to handle hard constraints. In contrast, our framework constructs a differentiable surrogate from feasible solutions, computes its gradient through the KKT conditions, and enforces feasibility directly through the LMO during both training and inference, without separate rounding.

Our primary motivation is to substantially improve the computational efficiency of constrained NCO while maintaining competitive or better solution quality. By replacing sequential decomposition procedures with independent parallel LMO calls and GPU-friendly linear algebra, our framework enables efficient training and fast inference. Our experiments demonstrate substantial improvements over leading neural methods, including over 800$\times$ faster inference on MaxCut with better solution quality and approximately 43$\times$ lower reported inference time on QAP while matching FWNCO's solution quality. Similar improvements are observed across Maximum Coverage and DKS.

We updated the draft to better reflect your concern; in particular, we added a short discussion to the intro on RL-based approaches.

AuthorsOpenReview ↗

Response to Reviewer 67oC - II

The algorithms included in the experimentation do not include some important algorithms. For instance, in the QAP, Robust Tabu Search (RoTS) has been for decades one of the best algorithms (metaheuristic in this case) for optimization instances of the QAP. My concern regarding the experimentation is that the reference algorithms used to scale the Y-axis of the plots can be further improved. I am aware that the efficiency is the scope of the paper, however if we do not set the Y-axis correctly, we may give the mistaken impression that the proposed algorithm is one of the most competitive algorithms available, which may be completely incorrect. I request including the reference algorithms for each problem (going beyond NCO).

Thank you for emphasizing the importance of strong classical baselines for interpreting the quality–runtime comparisons. We have expanded the experiments with Robust Tabu Search (RoTS) for QAP and Breakout Local Search (BLS) for MaxCut, complementing the strong non-learning baselines already included for MC and DkS.

For MC, Greedy is a particularly strong reference algorithm that exploits the marginal-gain structure of the coverage objective. It combines a (1−1/e)(1-1/e) approximation guarantee with excellent empirical performance: across all eight main-table settings, it achieves at least 98.5% of the best reported coverage, closely matching the solutions obtained by Gurobi while running very fast.

For DkS, we include FW-DL, L-ADMM, and EP-Prox, three specialized non-learning optimization methods tailored to the densest-subgraph problem. Their strength is evident in our experiments: FW-DL attains the best observed objective on six of the twelve graphs, and all three methods attain the provable optimum of 4,950 edges on com-DBLP for k=100k=100. On soc-LiveJournal1, L-ADMM and EP-Prox obtain 4,948 and 4,944 edges, respectively, approaching the optimum of 4,950.

For the additional experiments, we used Taillard’s publicly released C implementation for RoTS and implemented BLS for MaxCut following the algorithm and parameter settings described by Benlic and Hao (2013).

We evaluated RoTS on the same 108 QAPLIB instances, recording the objective attained at 1 and 10 seconds. Gaps are measured against the QAPLIB reference values and averaged equally across the 14 classes.

MethodTime (s) ↓Mean class gap (%) ↓
Ours0.03626.3931
RoTS1.0000.0439
RoTS10.0000.0109

We evaluated BLS on the same 35 Gset graphs, recording the best cut attained at each time budget. Mean cuts and percentage gaps weight all graphs equally, with gaps measured against the published BLS reference cuts.

MethodTime (s) ↓Mean cut ↑Mean gap (%) ↓
Ours0.20708908.830.8711
BLS1.00008967.130.2245
BLS10.00008975.770.1371

These baselines provide strong references through algorithms that exploit the structure of their respective problems. Our method follows a unified design across MC, DkS, MaxCut, and QAP, sharing the same parallel oracle-based solution-generation and differentiable training framework, with representations, objectives, and oracles adapted to each problem. The experiments therefore evaluate this unified framework alongside strong, problem-specific non-learning solvers in both solution quality and efficiency.

To address the reviewer's concern about the Y-axis interpretation, we have incorporated RoTS and BLS into the quality-runtime plots (Figures 2 and 3) and clarified the normalization references in their captions. Additional experimental details are provided in Appendices D and E.

AuthorsOpenReview ↗

Response to Reviewer 67oC - III

The idea of working in the arena of polytopes sounds good, however, I think more insights should be given to the reader. For instance, sentences such as "admit efficient linear optimization over P" is not clear enough. If optimizing linearly over P is optimum, then... is the problem NP-hard? Please provide more insights in this regard. The same lack of insights is observed two paragraphs below in "Self-Supervised CO and traning". Please, improve this part as well.

We thank the reviewer for this suggestion. Efficient linear optimization over PP does not imply that the original combinatorial problem is easy. The LMO solves an auxiliary linear problem, max⁡v∈P⟨q,v⟩\max_{v\in P}\langle q,v\rangle, which differs from the original objective max⁡v∈Cf(v)\max_{v\in\mathcal C}f(v). For example, linear optimization over the MaxCut hypercube reduces to coordinate-wise sign selection, while MaxCut remains NP-hard. Similarly, linear assignment is polynomial-time solvable, whereas QAP is NP-hard.

Our framework exploits this distinction: the LMO efficiently generates feasible candidates, which are then evaluated using the original combinatorial objective. Regarding the self-supervised training procedure, the network generates query directions, the LMOs produce feasible solutions, and their objective values are used to construct a differentiable surrogate through the regularized QP. The resulting KKT-based gradients are backpropagated to the network without differentiating through the discrete oracles or requiring optimal solution labels.

We have revised Sections 2 and 3 to explain these concepts and the training procedure more clearly.

The paper is hard to read. I understand the limitation of pages, however, for a CO researcher that is not familiarized with the idea of optimizing in the polytope of the problem, might find the explanations in the abstract and introduction hard to understand. For the same reason, then in section 2 it feels that the paper goes very fast on the background that is key to understand the proposal. If the experimental part is devoted to validate the algorithm, I would reduce it to 1-2 pages at most, and dedicate more space to sections 2-3.

We thank the reviewer for this feedback. We have revised the introduction and expanded Sections 2 and 3 to improve clarity and provide more background. We devoted substantial space to the experiments because our very strong empirical results across four distinct combinatorial problems are a central contribution of this work.

Reviewer_1f9COpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper describes a method for training and evaluating a neural network for solving combinatorial optimization problems. The main challenge is the discrete nature of such a problem as it is a priori unclear how to train a model for this using standard continuous optimization techniques.

To overcome this, the paper considers the convex hull of the discrete feasible points. The role of the neural network is to output some tuples that are (1) associated with points in the polytope and (2) used to evaluate the loss function. The step (1) is done by computing an optimal vertex of the linear program over the convex hull of the feasible set with an output of the neural network as objective function. For step (2), a distribution over vertices is computed from the objective functions of step 1.

This builds on earlier work by Karalias et al. (2022 & 2025) on convex extensions by taking suitable convex combinations of the discrete feasible points. The crucial point of the paper under consideration is to say that step (1) can be modified to be done for all directions in parallel. Therefore, it saves computing time in contrast to earlier work that computed such a convex combination sequentially.

The paper treats a general self-supervised learning setup, using the optimization problem itself as label data encoded in the loss function. The efficiency of the method is explored on various experiments for MaxCut, the Qadratic Assignment Problem, Maximum Coverage, Densest k-subgraph. The accuracy-runtime-tradeoff is compared with various other standard solvers for this kind of combinatorial optimization problem.

Critical strengths
  1. The experimental setup seems reasonable, the charts indicate that the approach achieves a favourable time-accuracy tradeoff compared to other standard solvers.

  2. The derivation of the gradient on page 5 seems reasonable, though, as described below, I struggle to see its meaning.

Critical weaknesses
  1. I struggled to understand the paper until I read the previous work by Karalias et al. The setup is not clearly described and there are various flawed details. I give some examples:
  • page 3, line 121: 'We associate C with its combinatorial polytope' -- what do you mean by a combinatorial polytope? In this 'association' not all elements of C are necessarily vertices of P.
  • page 3, line 126: I guess the maximization problem should range over P?
  • page 4, line 178: why should the linear maximization oracle (LMO) return a vertex? The solution could be a whole face of the polytope, the details are not specified.
  • page 4, line 181: I don't understand what is meant with 'the query directions ... vary continuously with the neural network output' -- how do they even differ from the neural network output?

Additionally, the comparison with the work Karalias et al. (2025), Nerem et al. (2025), Rafiey et al. (2026) is not clear on the technical level -- as far as I see, they are actually quite similar.

  1. It is unclear why the constructed loss function actually has a meaning for the considered problem: in the described setup, the neural network encodes directions q_1,...,q_m used to select vertices of the convex hull of the feasible set. It is unclear how these directions are drawn, shouldn't the network yield a deterministic output for a given instance? Furthermore, the computation of the coefficients for the convex combination seems rather arbitrary: the weighted sum x_{\theta} of the directions has actually no meaning in the space of the polytope, so I don't see why equation (3) would be a 'natural way' to associate a distribution over vertices.
Questions for authors
  1. How can the neural network acutally learn to encode the structure of the minimization problem with the chosen setup?

  2. All the experiments are over {0,1}- or {-1,1}-points. In this case, all points are actually vertices of the convex hull. Did you also compare with other discrete problems where this is not the case?

10 comments
AuthorsOpenReview ↗

Response to Reviewer 1f9C - I

We thank the reviewer for the detailed feedback. We have revised the manuscript to clarify your conerns. We hope these changes address the concerns and make our contributions clearer.

The experimental setup seems reasonable, the charts indicate that the approach achieves a favourable time-accuracy tradeoff compared to other standard solvers.

We thank the reviewer for recognizing the favorable quality-runtime trade-off. We would like to emphasize that our improvements over leading neural methods are substantial across all four combinatorial problems. On MaxCut, we achieve a better mean gap than ANYCSP (0.87% vs. 0.95%) while being over 800$\times$ faster. On QAP, we match FWNCO's solution quality with 43$\times$ lower inference time. On DKS, we achieve the best solution quality among the compared methods (0.8940.894 normalized objective) while being over 100$\times$ faster than L-ADMM, an ADMM-based optimization method. For Maximum Coverage, we achieve the lowest inference time across all eight benchmark settings, while maintaining competitive or better solution quality.

More broadly, our contribution is a unified framework that works across diverse combinatorial optimization problems with different constraints and polytope structures.

The derivation of the gradient on page 5 seems reasonable, though, as described below, I struggle to see its meaning.

We thank the reviewer for this comment. The gradient has a clear interpretation in our training framework. Changes in the query directions qiq_i affect their mean xθ=1m∑iqix_\theta=\frac{1}{m}\sum_i q_i, which in turn changes the probability weights assigned to the generated feasible solutions. Our surrogate objective is

FV(xθ)=∑i=1mαi(xθ)f(vi).F_V(x_\theta)=\sum_{i=1}^{m}\alpha_i(x_\theta)f(v_i).

Under the local stability assumption, VV remains fixed, and our KKT-based computation gives the exact gradient of this objective. The chain rule then gives

\left(\frac{\partial q_i}{\partial\theta}\right)^\top \nabla_{x_\theta}F_V(x_\theta),$$ allowing the objective values of feasible candidates to guide network training without differentiating through the discrete LMO. We have further clarified this interpretation and added the explicit backpropagation and chain-rule expressions in Section 3. > I struggled to understand the paper until I read the previous work by Karalias et al. The setup is not clearly described and there are various flawed details. I give some examples: >> page 3, line 121: 'We associate C with its combinatorial polytope' -- what do you mean by a combinatorial polytope? In this 'association' not all elements of C are necessarily vertices of P. By *combinatorial polytope*, we mean $P=\operatorname{conv}(\mathcal C)$, the convex hull of the finite feasible set. We agree that **not every element of $\mathcal C$ must be a vertex of $P$ in general**. However, every vertex of $P$ belongs to $\mathcal C$, and linear optimization over $P$ always admits an optimal vertex. **Importantly, in all four problems considered in our experiments, every feasible solution is a vertex (corner) of $P$**, since the feasible solutions are binary or sign-valued, including permutation matrices. More generally, our framework only requires the LMO to return feasible solutions. We have updated Section 2 to clarify these distinctions and explicitly state this property of our experimental settings. >> page 3, line 126: I guess the maximization problem should range over P? Linear maximization over $\mathcal C$ and its convex hull $P=\operatorname{conv}(\mathcal C)$ are exactly equivalent. Indeed, any $x\in P$ can be written as a convex combination $x=\sum_i\lambda_i v_i$, where $v_i\in\mathcal C$, $\lambda_i\geq 0$, and $\sum_i\lambda_i=1$. By linearity, $$\langle q,x\rangle =\sum_i\lambda_i\langle q,v_i\rangle \leq \max_{v\in\mathcal C}\langle q,v\rangle.$$ Since $\mathcal C\subseteq P$, the reverse inequality also holds. Therefore, $$\boxed{\max_{v\in\mathcal C}\langle q,v\rangle =\max_{x\in P}\langle q,x\rangle.}$$ We use $\mathcal C$ in the LMO definition to emphasize that the oracle returns a feasible discrete solution. We have clarified this equivalence in the revised manuscript. >> page 4, line 178: why should the linear maximization oracle (LMO) return a vertex? The solution could be a whole face of the polytope, the details are not specified. We agree that the set of maximizers of a linear objective over $P$ can form an entire face. However, a linear objective over a polytope always attains its optimum at a vertex, so an exact LMO can select such a vertex using a fixed tie-breaking rule. Please check our response to your previous concern for details. In our experiments, all LMOs return discrete feasible solutions that are vertices of $P$, including sign vectors, top-$k$ selections, and permutation matrices.
AuthorsOpenReview ↗

Response to Reviewer 1f9C - II

page 4, line 181: I don't understand what is meant with 'the query directions ... vary continuously with the neural network output' -- how do they even differ from the neural network output?

As discussed in the draft, the query directions are either direct outputs of the neural network or samples from distributions parameterized by the network. In the deterministic setting, q1,…,qm=NNθ(I)q_1,\ldots,q_m=\mathrm{NN}_\theta(I). In the stochastic setting, the network predicts distribution parameters, and queries are generated through reparameterization as qi=μi+σi⊙ϵiq_i=\mu_i+\sigma_i\odot\epsilon_i.

Our intended point is that the queries vary continuously with the network parameters θ\theta (for fixed sampled noise), while the discrete LMO outputs remain locally constant.

Additionally, the comparison with the work Karalias et al. (2025), Nerem et al. (2025), Rafiey et al. (2026) is not clear on the technical level -- as far as I see, they are actually quite similar.

While these works share the general idea of constructing differentiable objectives from feasible solutions, there is a significant difference in their algorithmic structure.

Karalias et al. (2025) use geometric decomposition procedures, Nerem et al. (2025) rely on successive decompositions over the Birkhoff polytope, and Rafiey et al. (2026) employ an iterative Frank-Wolfe decomposition. All three require sequential steps, where subsequent oracle calls depend on previous results. In our approach, all queries are generated simultaneously, and the LMOs are evaluated independently in parallel. We then obtain the distribution over feasible candidates through a regularized simplex QP and compute the gradient directly from its KKT conditions.

Removing the sequential dependency is a central technical contribution of our work, and it leads to substantial computational improvements while maintaining competitive or better solution quality. We discussed this in the draft in the paragprah with question Can we design parallel decomposition algorithms for self-supervised constrained NCO that make both loss computation and rounding efficient on GPUs?. We clarified further in the updated draft.

It is unclear why the constructed loss function actually has a meaning for the considered problem: in the described setup, the neural network encodes directions q_1,...,q_m used to select vertices of the convex hull of the feasible set. It is unclear how these directions are drawn, shouldn't the network yield a deterministic output for a given instance? Furthermore, the computation of the coefficients for the convex combination seems rather arbitrary: the weighted sum x_{\theta} of the directions has actually no meaning in the space of the polytope, so I don't see why equation (3) would be a 'natural way' to associate a distribution over vertices.

We thank the reviewer for raising these points. Regarding query generation, our framework supports both deterministic and stochastic parameterizations, as described in Section 3. The network can directly output the queries or predict Gaussian parameters from which queries are sampled through reparameterization. The stochastic formulation is intentional, allowing the model to explore different LMO regions and generate diverse feasible solutions.

Regarding the loss construction, the role of xθx_\theta is to provide a differentiable reference point, rather than a feasible solution or an exact decomposition of the polytope. Given the generated candidates, the regularized QP provides a unique probability distribution α∈Δm\alpha\in\Delta_m, balancing proximity to xθx_\theta with regularization. The resulting surrogate FV(xθ)=∑iαif(vi)F_V(x_\theta)=\sum_i\alpha_i f(v_i) is directly based on the original combinatorial objective and provides informative gradients even when the discrete LMO outputs remain locally unchanged. Please see lines 275-288 in the updated draft.

Our construction does not require xθx_\theta to lie in conv⁡(V)\operatorname{conv}(V). Proposition 1 establishes the exact gradient of this candidate-conditioned surrogate almost everywhere under the stated assumptions, and our experimental results demonstrate its effectiveness in training neural solvers across different combinatorial problems. We explain more on this in Remark 2 of the updated draft.

AuthorsOpenReview ↗

Response to Reviewer 1f9C - III

How can the neural network acutally learn to encode the structure of the minimization problem with the chosen setup?

The network learns from the original combinatorial objective through a differentiable surrogate and backpropagation. Given an instance, the network generates queries qiq_i that produce feasible solutions vi=LMO⁡(qi)v_i=\operatorname{LMO}(q_i). Their objective values define the surrogate loss

\qquad x_\theta=\frac{1}{m}\sum_{i=1}^{m}q_i.$$ Under the local stability assumption, the generated candidates remain fixed, and **the KKT-based gradient provides a learning signal through the chain rule**: $$\nabla_\theta L =\frac{1}{m}\sum_{i=1}^{m} \left(\frac{\partial q_i}{\partial\theta}\right)^\top \nabla_{x_\theta}F_V(x_\theta).$$ This allows the network to update its query-generation parameters using the objective values of feasible solutions, without differentiating through the discrete LMO. **The effectiveness of this learning mechanism is supported by our training ablation in Appendix G.5**, which shows a 26--31% improvement in solution quality over the untrained model on DKS. > All the experiments are over {0,1}- or {-1,1}-points. In this case, all points are actually vertices of the convex hull. Did you also compare with other discrete problems where this is not the case? We thank the reviewer for this question. **It is important to distinguish the discrete feasible set $\mathcal C$ from its convex hull $P=\operatorname{conv}(\mathcal C)$.** For example, the hypersimplex contains fractional points, but its vertices are precisely the feasible binary $k$-selection vectors. Similarly, the vertices of the Birkhoff polytope are permutation matrices, while the polytope also contains fractional doubly stochastic matrices. **Our framework does not require every feasible solution to be a vertex.** The QP and KKT-based gradient computation apply to any feasible candidates returned by the LMO.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.