Label-Free Learning for Combinatorial Optimization

This direction is merged into another direction: label generation bottleneck. Its last version stays readable and citable here.

Version 1 of 117 papers21 conceptsfrozen 2026-10-04

The central challenge of using machine learning for combinatorial optimization (CO) is a recursive one: to train a model to solve an NP-hard problem, you typically need a dataset of optimal solutions. However, generating these "ground-truth" labels requires the very solvers we are trying to replace—solvers that are notoriously slow and often fail to scale to the large-scale instances where neural networks would be most useful.

A growing body of research is moving past this "label bottleneck" by developing frameworks that learn to optimize directly from the problem's mathematical structure. Instead of mimicking a teacher, these models explore the solution space and use the objective function itself as a training signal.

The Objective Function as a Teacher

In traditional supervised learning, a model is penalized for deviating from a known optimal path. In label-free learning, the model is instead penalized for the "cost" of the solution it proposes.

As noted by Yun Peng 0002 and Yün Peng in their survey Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art, reinforcement learning (RL) provides a natural mechanism for this. By treating the reduction in path length or cost as a reward, models can discover effective heuristics without ever seeing a single pre-solved example. This approach allows researchers like Yubin Xiao to develop Non-Autoregressive Solvers for TSP that are significantly faster than iterative solvers while remaining competitive in quality.

Differentiable Surrogates for Discrete Spaces

The primary technical hurdle in label-free learning is that combinatorial problems are discrete (e.g., an edge is either in a tour or it isn't), which makes them non-differentiable. You cannot "backpropagate" through a discrete choice.

To solve this, researchers are developing differentiable surrogate loss functions that act as continuous proxies for discrete constraints. For example, in Unsupervised Learning for Solving the Travelling Salesman Problem, Yimeng Min and Carla P. Gomes use a surrogate loss that encourages the model to produce "edge heat maps" that satisfy the properties of a Hamiltonian cycle.

Similarly, Feng Wu and colleagues introduced DiffILO, which reformulates Integer Linear Programs (ILPs) into continuous, unconstrained optimization problems. By smoothing the problem landscape, the model can learn to navigate toward feasible, high-quality solutions using standard gradient descent, bypassing the need for expensive training labels from traditional solvers.

Learning Constraints without Labels

Solving a problem like the Traveling Salesperson Problem (TSP) is not just about minimizing distance; it is about doing so while obeying strict constraints. In a label-free setting, the model must learn these rules of "physics" on its own.

Pascal Van Hentenryck and Seonho Park addressed this through Primal-Dual Learning (PDL). Their framework mimics the trajectory of classical optimization algorithms by training neural networks to satisfy constraints and optimize the objective simultaneously. This self-supervised approach achieves near-optimal solutions with negligible violations, offering massive speedups over traditional solvers because the "solving" happens in a single forward pass of the network.

For even more complex tasks, such as the Constrained Most Probable Explanation (CMPE) task in graphical models, Shivvrat Arya and Vibhav Gogate derived "consistent" loss functions from first principles. This allows the network to focus exclusively on the primal variable space, eliminating the need for auxiliary networks to estimate Lagrange multipliers.

Why It Works: Scaling Beyond the Teacher

The intuition behind the success of label-free learning is that a model's potential is no longer capped by the performance of the solver used to generate its training data.

As Benjamin Hudson and Amanda Prorok point out in their work on GNN-Guided Local Search, removing the reliance on optimal labels is the key to scaling. When a model learns from the objective function, it can be trained on problem sizes that are too large for any exact algorithm to solve. This enables a transition from "learning to imitate" to "learning to optimize," allowing neural solvers to generalize to massive, real-world datasets that were previously inaccessible.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_label_free_learning_for_combinatorial_op_8147d78a,
  title = {Label-Free Learning for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/label-free-learning-for-combinatorial-optimization/rdr_8147d78a7a954a81a765db3902fa9d77},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_label_free_learning_for_combinatorial_op_8147d78a_v1,
  title = {Label-Free Learning for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/label-free-learning-for-combinatorial-optimization/rdr_8147d78a7a954a81a765db3902fa9d77/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}