Neural Combinatorial Optimization and the Optimality Gap

This direction is split into other directions: optimality gap. Its last version stays readable and citable here.

Version 1 of 177 papers79 conceptsfrozen 2026-10-04

Combinatorial optimization (CO) problems—such as the Traveling Salesman Problem (TSP), Vehicle Routing (VRP), and Boolean Satisfiability (SAT)—are the backbone of logistics, hardware design, and scheduling. Traditionally, these NP-hard problems are solved using either exact solvers (which guarantee the best answer but scale poorly) or handcrafted heuristics (which are fast but require years of human engineering).

Neural Combinatorial Optimization (NCO) seeks to replace these handcrafted rules with learned heuristics. By training Graph Neural Networks (GNNs) and Reinforcement Learning (RL) agents, researchers aim to "learn" the underlying structure of optimization problems, producing solvers that are nearly as fast as simple heuristics but significantly more accurate. However, a persistent "optimality gap" remains: neural models often struggle to match the precision of mature, classical algorithms.

The Mechanism: Learning to Construct and Improve

Most NCO approaches fall into two categories: constructive and improvement heuristics.

In constructive models, an agent builds a solution step-by-step. For example, Herke van Hoof, Wouter Kool, and Max Welling demonstrated in Attention Solves Your TSP, Approximately that a Transformer-style attention mechanism can learn to pick the next city in a tour by attending to the embeddings of all other cities. This allows the model to capture global relationships that simple greedy algorithms miss.

Improvement heuristics, by contrast, start with a complete (but suboptimal) solution and iteratively refine it. André Hottung and Kevin Tierney introduced Neural Large Neighborhood Search (NLNS), which uses a neural network to "repair" broken solutions. This hybrid approach Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem leverages the iterative nature of classical optimization while using neural intuition to guide the search.

The Scaling Advantage

The primary appeal of NCO is its ability to generalize. A model trained on small instances (e.g., 50 nodes) can often be applied to much larger ones. Zhang-Hua Fu and Kai-Bin Qiu showed that by combining supervised "heat maps" with Monte Carlo Tree Search, a model trained on tiny graphs could Generalize to Arbitrarily Large TSP Instances of up to 10,000 nodes.

More recently, frameworks like L2R (Changliang Zhou et al.) and H-TSP (Xuanhao Pan et al.) have pushed this further, using hierarchical RL to solve problems with up to one million nodes. These models offer a massive speedup—sometimes 100x faster than traditional search—making them ideal for real-time applications where a "good enough" solution is needed instantly.

The Reality Check: Why the Gap Persists

Despite these successes, NCO faces a "reality check." In Neural Combinatorial Optimization: a New Player in the Field, Andoni I. Garmendia and colleagues noted that while neural solvers are fast, they rarely outperform mature metaheuristics (like LKH or Gurobi) in raw solution quality.

This performance gap is not just a matter of training time; it may be fundamental. David Gamarnik argues in Barriers for the performance of graph neural networks that GNNs are essentially "local algorithms." Because they pass messages between neighboring nodes, they struggle with the Overlap Gap Property—a mathematical barrier in random structures where local information is insufficient to find the global optimum.

Furthermore, neural models often lack the formal guarantees of classical solvers. As Huaiyuan Liu points out, many neural solvers lack a strict mathematical approximation ratio, making it difficult to know exactly how far a solution is from the absolute optimum.

Bridging the Gap: Hybrid Solvers

The current frontier of the field is hybridization: using neural networks to "warm-start" or guide classical algorithms.

  • Deep Policy Dynamic Programming (DPDP): This framework uses a GNN to prune the search space of a classical dynamic programming algorithm, achieving near-optimal results on constrained problems.
  • EARLI: Ido Greenberg and Shie Mannor developed EARLI, which uses RL to provide a high-quality initial population for a Genetic Algorithm, reaching in one second the quality that traditional methods take ten seconds to find.
  • Neural Algorithmic Reasoning (NAR): Dobrik Georgiev and Pietro Lio suggest pre-training GNNs to mimic classical polynomial-time algorithms (like Minimum Spanning Tree) before tackling NP-hard tasks, which improves the model's ability to reason about graph structure.

By combining the "intuition" of deep learning with the "rigor" of classical search, researchers are slowly narrowing the optimality gap, moving toward a future where neural solvers can handle the complexity of the real world with the precision of mathematics.

Papers in this version

Showing 60 of 77 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_neural_combinatorial_optimization_and_th_38ed9d5e,
  title = {Neural Combinatorial Optimization and the Optimality Gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/neural-combinatorial-optimization-and-the-optimality-gap/rdr_38ed9d5ec682490087b151750ecb209a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_neural_combinatorial_optimization_and_th_38ed9d5e_v1,
  title = {Neural Combinatorial Optimization and the Optimality Gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/neural-combinatorial-optimization-and-the-optimality-gap/rdr_38ed9d5ec682490087b151750ecb209a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}