用神经网络预热求解器，让大型指派问题更快更准
Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
- 用轻量神经网络预测对偶变量，快速启动精确求解
- 在16384规模下仍保持高效，比传统方法快1.5倍以上
- 无需迭代修正，保证最优解，适合大规模实时场景
线性指派问题（LAP）是基础组合优化任务，经典精确求解器虽能保证最优但存在$/mathcal{O}(N^{3})$瓶颈，而现有神经近似方法难以兼顾可扩展性与精确性。本文提出学习增强框架，通过预测对偶变量来热启动精确求解器，并配备回退机制以维持最坏情况保证。核心为RowDualNet，一种行独立的轻量架构，避免图模型的$/mathcal{O}(N^{2})$内存瓶颈，支持高达$N=16{,}384$的可扩展神经热启动。通过最小化技巧（Min-Trick）机制确保可行性，完全消除昂贵的迭代投影。实验表明，该方法显著降低Jonker-Volgenant（LAPJV）算法的搜索开销，在复杂合成数据上实现超2倍端到端加速，真实追踪任务提速1.25倍，运输网络提速1.5倍，且具备严格最优性和零样本泛化能力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。