PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe

Akbar Rafiey, Yifei Xu, Nikolaos Karalias

arXiv:2609.25728v1cs.LGcs.AI

TL;DR

Self-supervised combinatorial optimization must handle hard discrete constraints during continuous neural-network training. The paper decomposes arbitrary network outputs into sparse distributions over feasible solutions and reports strong empirical performance across several combinatorial problems.

  • Problem

    Self-supervised combinatorial optimization needs to handle hard discrete constraints during gradient-based training, while existing convex-extension approaches often require feasible network outputs and problem-specific constructions.

    Source: §1 · pp. 1–2

  • Method

    A Frank–Wolfe–style decomposition maps arbitrary continuous network predictions to sparse convex combinations of feasible solutions, using a linear maximization oracle.

    Source: §1 · p. 2

  • Results

    The framework shows strong empirical performance across Maximum Coverage, TSP, and QAP, and compared favorably with neural baselines on several combinatorial problems.

    Source: §1 · p. 3, §6 · p. 11

  • Takeaways & Limitations

    The TSP case showcases an end-to-end pipeline that infuses learned modules into Christofides’s algorithm.

    Source: §5.3 · p. 9, §6 · p. 11

    The a.e. stability assumption requires oracle decisions and tie-breaking not to switch pathologically under arbitrarily small input perturbations.

    Source: §4.1 · p. 7

Abstract

from arXiv · show

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 Caratheodory results. This decomposition induces an a.e.-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.

1 Introduction

Self-supervised combinatorial optimization can exploit patterns in structured instances without labeled solutions, but integrating hard constraints into gradient-based learning remains challenging. This work uses Frank–Wolfe decomposition to train from arbitrary network outputs and reports strong performance across several combinatorial problems.

1 Introduction

  • A Frank–Wolfe decomposition turns arbitrary continuous network outputs into sparse convex combinations of feasible solutions, whose expected discrete objective defines the self-supervised loss.The discrepancy between the output and its decomposition can also be included as an auxiliary regularizer; the authors report that it improves optimization stability and solution quality.Source: §1 · p. 2
  • The decomposition uses exactly T linear maximization oracle calls for T iterations, while a GLS iteration may require many oracle calls.The passage gives approximately O(n^2L) calls per iteration and O(n^3L) overall for a standard ellipsoid-based implementation.Source: §1 · p. 2
  • Unlike prior geometric-extension methods, the framework does not require network outputs to lie inside the feasible polytope during training.It uses Frank–Wolfe decomposition rather than projection to construct a sparse convex combination of feasible vertices.Source: §1 · p. 2
  • Given an efficient exact or approximate linear maximization oracle, the same decomposition applies across polytopes by changing only the oracle implementation.Each iteration requires one oracle call, avoiding problem-specific projections and specialized decomposition algorithms.Source: §1 · pp. 2–3
  • At inference, selecting the best solution in the decomposition support yields a feasible solution whose objective is no worse than the support’s expectation.The loss is a.e. differentiable, allowing gradients to propagate through the decomposition layer.Source: §1 · p. 3, Figure 1 · p. 3
  • The framework shows strong empirical performance across Maximum Coverage, TSP, and QAP.It uses a common framework across these different constraint families.Source: §1 · p. 3

2 Related Work

Prior work connects combinatorial optimization to convex geometry and self-supervised learning, but rounding, constraint enforcement, and integration with learning remain challenges. The paper situates its approach among these lines of work and draws on sparse convex approximation and Frank–Wolfe methods.

Extensions and optimization

  • Classical LP and SDP relaxations can yield strong guarantees, but typically rely on problem-specific, non-differentiable rounding procedures that are difficult to integrate into data-driven learning.Source: §2 · p. 3

Neural CO

  • Self-supervised combinatorial optimization uses expected discrete objectives as differentiable losses, but must still address constraint enforcement.Prior approaches include projection, penalty terms, annealing, and physics-inspired formulations; this work instead builds feasibility into a distribution over feasible solutions.Source: §2 · pp. 3–4
  • Related geometric-relaxation methods generally require network outputs inside the feasible polytope, whereas this approach accepts arbitrary continuous outputs and decomposes them across constraint families.Source: §2 · p. 4

Approximate Carathéodory and Frank-Wolfe

  • Carathéodory’s theorem gives an exact representation using at most d + 1 vertices, while approximate variants provide dimension-independent bounds for sparse approximations.Frank–Wolfe-type algorithms offer a mechanism for obtaining these sparse convex combinations.Source: §2 · p. 4

3 Problem Formulation and Learning Setup

The setup represents combinatorial optimization as optimizing an objective over a finite feasible set and uses its convex hull to connect discrete solutions with continuous outputs. In self-supervised learning, networks need no optimal-solution labels, and a geometry-based procedure supplies a differentiable training objective and feasible inference solutions.

3 Problem Formulation and Learning Setup

  • A combinatorial optimization instance has discrete variables, a finite feasible set, and an objective to maximize or minimize over that set.Source: §3 · p. 4
  • The formulation covers Boolean vectors, discrete assignments, permutations, and non-Boolean domains.Examples include budgeted Maximum Coverage, TSP tours, QAP, and k-submodular maximization.Source: §3 · p. 4
  • The feasible polytope P is the convex hull of feasible solutions; for k-subsets, its vertices are indicator vectors and the polytope is the hypersimplex.Source: §3 · p. 4
  • Many important combinatorial polytopes have efficient linear optimization oracles despite potentially having exponentially large facet descriptions.Source: §3 · p. 4

3.1 Self-Supervised Learning for CO

  • In self-supervised learning, a neural network maps instance features to a representation that need not lie in the feasible polytope.Source: §3.1 · p. 5
  • Learning uses an a.e. differentiable extension of the combinatorial objective, constructed using polytope geometry so it can be optimized on fractional solutions.Source: §3.1 · p. 5
  • Training uses instances without ground-truth optimal solutions; at inference, a geometry-based procedure converts continuous outputs into feasible discrete solutions.The objective can also be optimized directly on test instances, allowing additional test-time computation to improve solution quality.Source: §3.1 · p. 5

4 Proposed Method

The method accepts unconstrained network predictions, decomposes them into sparse mixtures of feasible vertices with Frank–Wolfe, and uses the resulting coefficients in self-supervised training. It extends across matroid and matching polytopes through efficient or approximate linear maximization oracles.

4 Proposed Method

  • The pipeline maps an arbitrary network output to a sparse convex combination of feasible vertices in the polytope.The support budget T controls the number of vertices in the mixture.Source: §4 · p. 5, §4.1 · p. 6

4.1 From NN Output to Polytope: Frank-Wolfe Decomposition

  • Frank–Wolfe selects a polytope vertex aligned with the residual and takes a line-search step toward it, keeping each iterate feasible without projection.The linear maximization oracle supplies the vertex; the step is a convex combination of feasible points.Source: §4.1 · pp. 6–7
  • The decomposition coefficients are almost everywhere differentiable functions of the target input, supporting gradient-based training through the induced objective.Under the stable-oracle assumption, the selected vertices are locally constant almost everywhere, so gradients propagate through the coefficients.Source: §4 · p. 5, §4.1 · p. 7
  • A δ-relative Frank–Wolfe-gap oracle preserves the convex-combination conclusion, and its coefficient map remains almost everywhere differentiable.The approximate-oracle result extends the decomposition guarantee beyond exact linear maximization.Source: §4.1 · p. 7

4.2 Examples with Efficient (Approximate) LMO

  • Matroid base polytopes use greedy maximum-weight base oracles, while Birkhoff and perfect-matching polytopes use matching oracles; greedy approximations can suffice empirically.The framework applies across matroids without modification and supports direct optimization over matching polytopes without projections or penalties.Source: §4.2 · p. 7

5 Applications and Experiments

The experiments apply the same decomposition across Maximum Coverage, QAP, and TSP, reporting competitive or stronger performance; the TSP study embeds learning in a Christofides-style pipeline.

5.1 Maximum Coverage

  • For Maximum Coverage, the method is faster than GeoNCO, often outperforms learning baselines, and stays on their Pareto front while remaining competitive with non-learning methods on quality-efficiency tradeoffs.Evaluation uses maximum coverage over decomposed subsets without test-time optimization.Source: §5.1 · p. 8

5.2 Quadratic Assignment Problem

  • On QAPLIB sizes 12–64, the method achieves the best overall performance among learning and classical baselines, is the fastest neural method, and scales beyond 64 with similar average gaps.SM and RRWM run faster but incur a substantial loss in solution quality.Source: Table 2 · p. 9, §5.2 · p. 9
  • Under QAPLIB’s strong heterogeneity and distribution shift, unconstrained outputs far from the Birkhoff polytope can yield low-quality permutations; a lightweight Sinkhorn projection improves generalization.The projection is included for practical reasons, not theoretical necessity.Source: §5.2 · p. 9

5.3 TSP via Spanning Trees and Learned Matchings

  • For TSP, the method learns distributions over spanning trees and matching polytopes, then applies matching and shortcutting within a differentiable Christofides-style pipeline.The spanning-tree decomposition uses Kruskal’s algorithm as its linear maximization oracle.Source: §5.3 · pp. 9–10
  • Across TSP benchmark scales, the method outperforms unsupervised neural baselines and, on larger instances, DIFUSCO, but remains behind the strongest supervised methods.It can be trained in under an hour on a single outdated GPU, while DIFUSCO and COExpander rely on up to about 1.5M labeled instances and extensive training time on good hardware.Source: Table 3 · p. 10, §5.3 · p. 10

6 Conclusion

The paper concludes that its generic decomposition supports self-supervised combinatorial optimization under constraints and reports strong empirical performance against neural baselines on several problems.

6 Conclusion

  • The framework accepts neural outputs outside the feasible polytope and decomposes them into sparse distributions over feasible solutions for self-supervised learning.The paper presents this as a general framework for constrained combinatorial optimization.Source: §6 · p. 11
  • The paper demonstrates an end-to-end example of learned modules within an algorithm by applying its approach to TSP using Christofides’s algorithm.Source: §6 · p. 11
  • The paper leaves the effect of model architecture on performance unstudied and identifies it as future work.Source: §6 · p. 11

A Proofs for Theorem 4.3 and Corollary 4.4

The appendix proof addresses convex-combination structure and almost-everywhere differentiability under a stable oracle decision assumption, alongside experimental setup and baseline details.

A Proofs for Theorem 4.3 and Corollary 4.4

B Details and Further Experiments for Maximum Coverage

B.1 Experiment Setup

  • Maximum Coverage experiments train on synthetic random graphs and test on same-distribution samples plus three Italian railway crew-assignment instances.The setup uses a three-layer residual GNN, entropy regularization annealed to zero by epoch 30, and 80 training epochs; inference runs 50 decomposition iterations without randomized or local improvement.Source: §B.1 · p. 16

B.2 Baselines

  • The Maximum Coverage baselines include exact Gurobi, classical random and greedy methods, UCOM2, and neural methods including CardNN, EGN, GeoNCO, and actor-critic reinforcement learning.Source: §B.2 · pp. 16–17

B.3 Ablation study on projection

The ablation finds that projection is unnecessary for feasibility and that removing it preserves solution quality while slightly improving coverage and inference time.

B.3 Ablation study on projection

  • The framework does not require projection because feasibility is already guaranteed by the Frank–Wolfe decomposition.The ablation uses the same projection method as [24].Source: §B.3 · p. 17
  • Removing projection preserves solution quality and slightly improves coverage on rand500 and rand1000, with slightly lower wall-clock inference time.FW decomposition still produces feasible candidates, while unconstrained scores retain a richer exploration space.Source: §B.3 · p. 17, Table 4 · p. 17
  • The stated explanation is that hard, piecewise projection can compress the effective search region and reduce gradient-signal diversity.The authors attribute steadier optimization and marginally improved performance to allowing unconstrained continuous scores while decomposition supplies feasible candidates.Source: §B.3 · p. 17

B.4 Ablation on Hard Instances for Greedy

On GREEDYTRAP instances, the method outperforms greedy and approaches OPT; a separate iteration-budget study finds T = 50 a practical quality–runtime balance. The section also points readers to the full QAP results in Table 7.

B.4 Ablation on Hard Instances for Greedy

  • GREEDYTRAP constructs k sets that cover disjoint element partitions, while k trap sets win greedy's early choices with slightly more than 1/k of each part.The 500- and 1000-set variants use 1000 and 2000 elements, respectively; greedy is pushed near its 0.63212 lower bound.Source: §B.4 · p. 17
  • Our method consistently outperforms greedy and achieves coverage closer to OPT on GREEDYTRAP instances.Table 5 reports coverage ratios averaged across 64 test instances.Source: Table 5 · p. 17, §B.4 · p. 18

B.5 Effect of the Frank–Wolfe Iteration Budget

  • 99.391–99.652% of reference quality is reached at T = 50; moving to T = 200 adds only 0.348–0.609 percentage points while runtime rises approximately 3.7–3.8×.The reported quality is normalized by weighted coverage at T = 200; runtime grows linearly with iteration budget.Source: §B.5 · p. 18, Table 6 · p. 18
  • The authors select T = 50 as a practical balance between solution quality and computational cost.The study reports four configurations.Source: §B.5 · p. 18

C Details and Further Experiments on QAP

C.1 Experiment Setup

The experiments span QAPLIB and Euclidean TSP settings, with setup choices tailored to each task. The related-work discussion contrasts the framework with iterative QAP methods and heatmap-based TSP pipelines, while the baseline sections describe the comparison landscape.

C.1 Experiment Setup

  • Synthetic QAP training uses 5120 instances at n = 32 and p = 0.3; QAPLIB tests cover varied classes, with results reported for n = 12–64 and larger instances listed separately.Table 7 reports per-class and aggregate QAPLIB results; Table 8 covers n > 64.Source: §C.1 · pp. 18, 20, Table 7 · p. 19, Table 8 · p. 20
  • QAP outputs are not theoretically required to be projected, but a 20-iteration Sinkhorn layer calibrates them near the Birkhoff polytope for robustness under QAPLIB distribution shift.Inference selects the minimum-cost permutation from the decomposition; greedy maximum-weight assignment instantiates the LMO.Source: §C.1 · pp. 19–20

C.2 Related Work (QAP / Matching).

  • Earlier QAP methods use iterative construction or improvement, whereas this framework produces assignment logits once and deterministically outputs a permutation, with lightweight Sinkhorn normalization for outlier-friendly behavior.The cited discussion characterizes the earlier methods as less efficient for large instances and reliant on complex architectures or inference procedures.Source: §C.2 · pp. 20–21

C.3 Baselines

  • The QAPLIB comparison includes classical and neural baselines, but SAWT and RGM timings are cited rather than reproduced and are indicative because of hardware differences.The authors also flag uncertainty about the evaluation protocol behind multiple reported WIL results, since the stated size range contains only WIL50.Source: §C.3 · p. 21

C.4 Effect of the Frank–Wolfe Iteration Budget

  • 99.837% relative quality at T = 3000 costs 4.410 seconds; T = 10000 adds 0.163 percentage points but raises runtime to 15.798 seconds, approximately 3.6× higher.Table 9 normalizes solution quality by the weighted solution at T = 10000.Source: Table 9 · p. 21, §C.4 · p. 21

D.1 Experiment Setup

  • TSP-50 and TSP-100 tests use 1280 instances each, while TSP-500 uses 128 and TSP-1000 uses 32; decomposition uses T = 64 in training and testing.Edge features include subtour-LP values computed with QSopt, also used by Concorde.Source: §D.1 · p. 22

D.2 Related Work: Neural Methods for TSP

  • The TSP discussion contrasts sequential LC decoding and heatmap-based GP/AE recovery with an end-to-end pipeline that differentiates through a selected FW branch and directly optimizes feasible tours.The discussion frames the design as reducing reliance on hand-crafted post-processing and avoiding a separate heatmap recovery/search step.Source: §D.2 · pp. 22–23

D.3 Baselines

  • TSP baselines span exact solvers, LKH3, an RL-trained LC method, and neural GP/AE approaches under RL-style and supervised regimes.The comparison aims to cover paradigms and supervision regimes under a fixed compute budget, noting timeouts or training-cost omissions.Source: §D.3 · p. 23

D.4 Detailed Results

The TSP experiments report cross-size generalization and show that learned matching improves tour objective values over greedy matching, at the cost of inference time.

D.4 Detailed Results

  • The TSP runtime breakdown identifies the Subtour-Elimination LP and FW decomposition as the dominant pipeline stages.In the learned-matching version, matching also takes up a large portion of overall runtime.Source: §D.4 · p. 23
  • Performance transfers largely stably across TSP instance sizes, with modest degradation when models trained on smaller instances are tested on larger ones.Models trained on larger instances transfer to smaller ones with only minor differences on TSP-100.Source: §D.4 · p. 23, Table 12 · p. 24
  • The learned scoring function is described as capturing size-agnostic geometric regularities of Euclidean TSP, supporting transfer across instance scales without retraining at each target size.Some results are omitted because methods could not finish within the cutoff time or training costs were prohibitive.Source: §D.4 · p. 24

D.5 Discussion on Learned Matching

  • The learned matching pipeline uses a two-layer MLP with Fourier positional encodings and an FW matching-decomposition budget of Tmatch = 8.The TSP spanning-tree network follows the setup in Section D.1.Source: §D.5 · p. 25
  • Learned matching improves objective values over greedy matching, but increases inference time and can dominate the added runtime on large instances.The runtime breakdown identifies matching as a large part of total runtime on large instances.Source: Table 10 · p. 24, §D.5 · p. 25

D.6 Ablation Study and Discussion on Projection

For TSP, removing projection slightly improves performance on TSP-500 and TSP-1000; the paper also reports robustness on a broader set of Euclidean instances.

D.6 Ablation Study and Discussion on Projection

  • Removing projection yields slightly better performance on both TSP-500 and TSP-1000.The projection ablation compares results with and without projection.Source: §D.6 · p. 25, Table 13 · p. 25
  • The TSP-1000-trained model remains robust on 2D Euclidean TSPLIB instances ranging from 51 to 1002 nodes.The authors link this result to Euclidean TSP's low-dimensional geometric embedding and metric distances, which they say make extremely hard out-of-distribution instances comparatively rare.Source: §D.6 · p. 25, Table 14 · p. 25
  • The authors conclude that explicit projection can be counterproductive for problems like Euclidean TSP, where the no-projection design is viable and can perform better.Source: §D.6 · p. 25

D.7 Ablation Study: LP + Noise

The paper compares learned TSP weights with random LP perturbations, sets a one-shot evaluation protocol, reports training memory below 8 GiB, and describes polytope settings handled through efficient linear maximization oracles.

D.7 Ablation Study: LP + Noise

  • Even under a favorable best-of-10 comparison, random perturbations of the LP solution do not match the learned method, especially on larger TSP instances.The baseline adds Gaussian noise with σ = 0.2 before the same decomposition and rounding pipeline.Source: §D.7 · pp. 25–26, Table 15 · p. 26

E Further Discussion on Inference Settings

  • The evaluation protocol treats a sparse feasible set produced from one neural output as one-shot, while excluding extra inference computation that enlarges the search pool.This protocol aims to assess intrinsic constructive capability without extensive post-hoc search.Source: E Further Discussion on Inference… · pp. 26–27

F GPU Memory Usage

  • FWNCO's peak allocated training memory is below 8 GiB for every evaluated configuration.The measurements are allocated CUDA memory, not total device-memory consumption.Source: F GPU Memory Usage · p. 27, Table 16 · p. 27

G Polytopes with Efficient (Approximate) LMO

  • The framework applies uniformly across the listed matroidal constraints using an efficient LMO, without constraint-specific projections or decomposition procedures.The cited constraints include cardinality, partition, and spanning-tree constraints.Source: G Polytopes with Efficient… · pp. 27–28
  • For the Birkhoff polytope, linear maximization reduces to maximum-weight perfect matching and can be solved by the Hungarian algorithm in O(n^3).The approach also covers matching and perfect-matching polytopes; the paper notes that greedy approximate LMOs suffice empirically.Source: G Polytopes with Efficient… · p. 28

Related papers

Loading 2609.25728v1…