Tiny recursive neural models improve combinatorial optimization speed and quality
Compute Time Scaling with Recursive Models for Combinatorial Optimization
Machine Learning
Summary
Combinatorial optimization problems like the Traveling Salesman Problem and Maximum Independent Set are hard to solve quickly and well. The authors propose a tiny recursive neural network model that repeatedly modifies its understanding of the problem, while using only a small part of the input at a time. This method balances the need for computation on tough problems with avoiding overfitting, leading to better solutions faster. They also introduce a way for the model to train itself using its own improved solutions instead of relying on perfect examples.
What this means in practice
- •For logistics planners: Generate faster, higher-quality routes for large-scale vehicle routing and delivery scheduling problems using efficient neural optimization.$Commercial implications: Enables commercial route planning software to provide more accurate, faster solutions for logistics companies handling complex delivery networks.
- •For network operators: Optimize network node selections and resource allocations in large communication or data networks with reduced computation time.
Authors
Zhengxi Zhang, Paul Swoboda
Abstract
We propose Tiny Recursive Models for Combinatorial Optimization (\ours{}), a general neural method for combinatorial optimization that scales both depth (how often we recursively invoke our network) and width (how much we sample in parallel). Both are fundamental for combinatorial optimization: hard instances demand a large amount of compute, while a small network is essential to avoid overfitting and capture the algorithmic essence of optimization. In particular, our method consists of a graph-aware tiny recursive model that iterates on a latent state with adaptive halting and needs only a lightweight problem-specific decoder. Compared with previous heatmap-based general neural solvers, it achieves a better balance between solution quality and inference speed on both the Traveling Salesman Problem~(TSP) and the Maximum Independent Set~(MIS) problem, and remains competitive with hybrid methods that combine neural components with heuristics specific to each problem. With the same backbone architecture for both tasks, \ours{} outperforms every diffusion-based solver on TSP from 500 to 10,000 cities at a lower inference cost, and on the standard Erdős--Rényi-[700-800] MIS benchmark it surpasses all neural solvers except those that only work well on MIS. We then explore self-relabeling for self-supervised training. We periodically replace the current set of training labels with the model's own better solutions, as an alternative training signal. Self-relabeling can, while forgoing supervision from near-optimal solutions, still result in on-par quality.