Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910275343482880 |
|---|---|
| author | Yavlovich, Ilay Agbaria, Jad Mhamed, Muhamed Weinberger, Nir Yallouz, Jose |
| author_facet | Yavlovich, Ilay Agbaria, Jad Mhamed, Muhamed Weinberger, Nir Yallouz, Jose |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09382 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts Yavlovich, Ilay Agbaria, Jad Mhamed, Muhamed Weinberger, Nir Yallouz, Jose Machine Learning Computer Vision and Pattern Recognition Data Structures and Algorithms Optimization and Control 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. |
| title | Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts |
| topic | Machine Learning Computer Vision and Pattern Recognition Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2605.09382 |