Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

The Linear Assignment Problem is a fundamental combinatorial optimization task where classical exact solvers ensure optimality but suffer from an $\mathcal{O}(N^{3})$ bottleneck, while recent neural approximations struggle with scalability and exactness. We propose a learning-augmented framework that accelerates exact solvers by predicting dual variables to warm-start the search, backed by a fallback mechanism to preserve worst-case guarantees. Central to our approach is RowDualNet, a lightweight, row-independent architecture that avoids the $\mathcal{O}(N^{2})$ memory bottleneck of graph models, enabling scalable neural warm-starting up to $N=16{,}384$. Feasibility is guaranteed by construction via the Min-Trick mechanism, completely eliminating the need for costly iterative projections. Empirically, our method drastically reduces the search effort of the Jonker-Volgenant (LAPJV) algorithm, yielding robust zero-shot generalization with strict optimality and end-to-end speedups of over 2x on complex synthetic data, 1.25x on real-world tracking, and 1.5x on transportation networks.

Many important real-world tasks—such as routing traffic, scheduling logistics, or tracking moving objects in videos—rely on solving a massive matching puzzle known as the Linear Assignment Problem. While traditional mathematical algorithms guarantee perfect matches, they become very slow as the number of items grows into the thousands. Conversely, modern AI systems can guess matches quickly, but they often make errors or run out of computer memory on large puzzles. To bridge this gap, we designed an AI model called RowDualNet that acts as a smart advisor to these traditional algorithms. Instead of trying to guess the final matches itself, our AI rapidly analyzes the puzzle and gives the traditional algorithm a highly accurate head start. We also included a built-in safety net: if the AI makes a poor prediction, the system safely ignores it. Because the traditional algorithm no longer starts from scratch, it finds the perfect answer significantly faster. Our method more than doubles the speed of finding flawless solutions and successfully generalizes to real-world applications like transportation networks and multi-object tracking in videos. Ultimately, this approach merges the rapid speed of AI with the absolute certainty of pure mathematics.