Neural Combinatorial Optimization (NCO) promises a revolution in logistics and manufacturing by replacing slow, hand-crafted heuristics with fast, learned solvers. However, these models face a notorious "generalization wall": a model trained to solve the Traveling Salesman Problem (TSP) for 50 cities often fails catastrophically when asked to solve for 5,000.
This failure isn't just a lack of data; it is a fundamental mismatch between the structural patterns of small-scale synthetic benchmarks and the complexity of large-scale, real-world instances. Recent research has focused on bridging this gap through architectural priors, problem decomposition, and hybrid search strategies.
The Attention Dispersion Problem
The primary engine of modern NCO is the Transformer. While powerful, its self-attention mechanism suffers from "attention dispersion" as problem size increases. In a 50-node problem, a node might attend strongly to its 5 nearest neighbors. In a 5,000-node problem, the softmax function flattens the attention weights across hundreds of nodes, diluting the signal and causing the model to make "blurry" decisions.
To combat this, Yang Wang and colleagues introduced Distance-aware Attention Reshaping (DAR). DAR adjusts attention scores using Euclidean distance as a bias, forcing the model to maintain focus on local neighborhoods even as the total number of nodes explodes. Similarly, Yubin Xiao proposed the Entropy-based Scaling Factor (ESF), which dynamically rescales attention weights based on the problem scale to prevent the vanishing gradient and signal dilution that occurs during inference on large graphs.
Locality as a Generalization Prior
A key insight in recent work is that while global optimal structures change with scale, the local logic of a good route—such as "visit nearby clusters before moving on"—remains relatively invariant.
Han Fang and Paul Weng developed INViT, which uses a "nested view" to process problems. By focusing on invariant coordinate layers, the model learns features that don't depend on the absolute size of the map. This is echoed in the work of Chengrui Gao, whose ELG framework combines a global policy with a "local policy" that uses scale-invariant features like polar coordinates. By prioritizing the topology of a node's immediate neighborhood, these models can generalize from 100 nodes to 7,000 without retraining.
Divide and Conquer via Neural Delegation
When a problem is too large for a single neural pass, the most effective strategy is often to break it into manageable pieces. This "divide and conquer" approach allows models trained on small data to tackle massive industrial instances.
Sirui Li introduced a learning-to-delegate framework where a Transformer identifies promising sub-regions of a large Vehicle Routing Problem (VRP) and "delegates" them to specialized solvers. This achieves massive speedups by focusing computational effort only where it is needed. For Mixed-Integer Linear Programming (MILP), Huigen Ye and Hua Xu developed Light-MILPopt, which uses a dual-reduction strategy to shrink variables and constraints, allowing a model trained on small instances to solve problems with millions of variables.
Hybridizing Intuition with Search
Purely neural solvers often struggle with feasibility—ensuring that a delivery truck doesn't exceed its capacity or miss a time window. To solve this, researchers are increasingly using neural networks as "intuition engines" inside traditional search metaheuristics.
- Heatmap-guided Search: Zhang-Hua Fu and Kai-Bin Qiu use a Graph Convolutional Residual Network to produce a "heat map" of likely edges, which then guides a Monte Carlo Tree Search to solve TSPs with 10,000 nodes.
- Neural Neighborhood Search: Jonas K. Falkner and colleagues integrated neural construction heuristics into Large Neighborhood Search (LNS). The neural network suggests which parts of a solution to "destroy" and "re-create," while the LNS framework ensures the final result is feasible and high-quality.
- LLM-Driven Optimization: Most recently, Huigen Ye explored using Large Language Models to automatically design LNS strategies, discovering search patterns that outperform commercial solvers like Gurobi on industrial-scale datasets.
The Path to Foundation Models for Optimization
The ultimate goal of this research direction is a "foundation model" for optimization—a single network that can solve any routing or scheduling problem regardless of its specific constraints or scale. Yaochu Jin and Xueming Yan have proposed a unified framework for converting diverse problems into a shared graph representation. By combining this universality with scale-agnostic architectures like INViT or Meta-SAGE, the field is moving toward solvers that are as flexible as human experts but as fast as silicon.