Title: Accelerating Scalable Linear Assignment Problem Optimization Through Neural Dual Warm-Starts

Abstract: The Linear Assignment Problem represents a core challenge in combinatorial optimization. While traditional exact solvers guarantee optimal solutions, they are hindered by an $\mathcal{O}(N^{3})$ computational bottleneck. Conversely, emerging neural approximation methods often fail to balance scalability with precision. To address these limitations, we introduce a learning-augmented framework designed to speed up exact solvers by leveraging predicted dual variables for warm-starting the search process. This approach includes a fallback mechanism to maintain worst-case performance guarantees. The cornerstone of our method is RowDualNet, a lightweight architecture that operates independently by row. This design circumvents the $\mathcal{O}(N^{2})$ memory constraints typical of graph-based models, allowing for scalable neural warm-starting with problem sizes up to $N=16{,}384$. We ensure feasibility through construction using the Min-Trick mechanism, which removes the necessity for expensive iterative projections. Our empirical results demonstrate a significant reduction in the search workload for the Jonker-Volgenant (LAPJV) algorithm. The method achieves robust zero-shot generalization while maintaining strict optimality, delivering end-to-end speedups of more than 2x on complex synthetic datasets, 1.25x on real-world tracking applications, and 1.5x on transportation network scenarios.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC