Unsupervised Learning for Combinatorial Optimization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2404 papers459 conceptsfrozen 2026-10-04

In traditional deep learning, we teach models by showing them the "right" answer. To train a model to recognize cats, we show it thousands of labeled cat photos. To train a model to solve a math problem, we usually show it thousands of solved examples.

In Combinatorial Optimization (CO)—the field of finding the best arrangement among a finite set of possibilities, like the Traveling Salesperson Problem (TSP) or the Maximum Independent Set (MIS)—this supervised approach hits a wall. These problems are NP-hard, meaning that finding the "right" answer (the ground truth) for large-scale instances is exactly what we are trying to avoid doing because it is computationally exhausting.

This creates a circular dependency: to train a neural solver that is faster than traditional algorithms, we first need to run those slow algorithms for thousands of hours to generate training data. Researchers like Oriol Vinyals noted this early on with Pointer Networks, where the performance of the neural network was inherently capped by the quality of the teacher.

The emerging research direction is to break this cycle by moving toward unsupervised and self-supervised learning, where models learn to solve problems by looking at the problem's own structure rather than a pre-computed solution.

Minimizing the Objective Directly

The most intuitive way to skip the "teacher" is to let the problem's objective function be the loss function. If we want to minimize the distance of a route, we don't need to know the optimal route; we just need a differentiable way for the neural network to calculate the distance of the route it thinks is best and then use gradient descent to make that distance smaller.

Carla P Gomes and Yimeng Min demonstrate this in Unsupervised Learning for Quadratic Assignment. Their framework, PLUME, trains a network to minimize the Quadratic Assignment Problem (QAP) objective directly. By doing so, the model provides a "warm-start" for traditional search heuristics, significantly speeding up the time to find high-quality solutions without ever seeing a single labeled example.

Similarly, in Differentiable Quadratic Optimization For the Maximum Independent Set Problem, Ismail Alkhouri and Cunxi Yu use a "dataless" approach. They reformulate the discrete MIS problem into a continuous quadratic objective that can be solved using GPU-parallelized gradient descent, allowing the model to scale to massive graphs where ground truth is impossible to obtain.

Primal-Dual Learning and Constraints

A major hurdle in unsupervised CO is handling constraints. If a model simply minimizes a cost function, it might "cheat" by providing an illegal solution (e.g., a TSP route that visits the same city twice).

Pascal Van Hentenryck and Seonho Park addressed this through Self-Supervised Primal-Dual Learning for Constrained Optimization. Their framework, PDL, mimics the Augmented Lagrangian Method. It uses two networks: one to predict the solution and another to predict the "penalty" for violating constraints. This adversarial-like setup forces the solver to find solutions that are both optimal and feasible, all without pre-solved training data.

Self-Improvement and Iterative Refinement

If we don't have a teacher, the model can become its own teacher. This is the core intuition behind Self-Improved Learning (SIL). In Self-Improved Learning for Scalable Neural Combinatorial Optimization, Fu Luo and Xi Lin describe a mechanism where the model generates its own training labels through local reconstruction. By iteratively refining its own guesses, the model can scale to problems with 100,000 nodes—far beyond the 1,000-node limit of most supervised solvers.

Generative models are also being adapted for this purpose. Yu Wang and Junchi Yan introduced StruDiCO, a diffusion-based solver. Instead of denoising images, it "denoises" a random initial state into a structured combinatorial solution. Because it uses a gradient-free refinement strategy at the inference stage, it can boost its own performance without needing a dataset of optimal solutions.

Learning from Preferences

When absolute ground truth is unavailable, relative quality can still provide a signal. If a model generates two different solutions, we might not know if either is optimal, but we can easily tell which one is better.

Alexander Mielke and colleagues explored this in Preference-Based Gradient Estimation for ML-Based Approximate Combinatorial Optimization. By using a Preference-Based Gradient Estimation (PBGE) scheme, they allow Graph Neural Networks to learn from the relative quality of solutions. This allows the model to match supervised performance by simply understanding the "direction" of improvement.

Why It Works: The Geometry of the Problem

The reason these unsupervised methods work is that combinatorial problems are not random; they have rigorous mathematical structures. Whether it is the connectivity constraints in the Maximum Minimal Cut Problem or the message-passing logic in RUN-CSP by Jan Toenshoff and Martin Grohe, the rules of the game provide the gradient.

By embedding these rules directly into the loss function or the architecture (like the Deep Attentive Belief Propagation by Yanchen Deng), we allow neural networks to explore the solution space and discover the underlying patterns of optimality on their own. This shifts the role of the researcher from "data provider" to "architect of the objective."

Papers in this version

Showing 60 of 404 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 377 papers
  2. Version 1 · 2026-10-04 · 404 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_label_generation_bottleneck_f384bfbc,
  title = {label generation bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/label-generation-bottleneck/rdr_f384bfbca6134fc1819fe278c4c04ce9},
  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_unsupervised_learning_for_combinatorial__f384bfbc_v1,
  title = {Unsupervised Learning for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unsupervised-learning-for-combinatorial-optimization/rdr_f384bfbca6134fc1819fe278c4c04ce9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}