Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SAWT, a learn-to-improve RL policy for Koopmans-Beckmann QAP that encodes facilities and locations separately and injects the solution-aware flow-distance matrix into attention, trained with REINFORCE and swap actions.
Problem
Learning-based solving of the Quadratic Assignment Problem is limited by O(n^4) association graphs, restricting scalability; prior ML work is small-scale or learn-to-construct, while OR meta-heuristics are slow.
Approach
Encodes facility and location nodes separately (Transformer with flow-matrix-mixed attention for facilities, GCN over distances for locations) and multiplies attention scores by a solution-aware matrix M = F ⊙ D_σ whose sum equals the QAP cost, so the policy iteratively applies swap operations without association graphs.
Key results
- On self-generated QAP100 with 10k search steps, SAWT reaches mean 1617.23 (gap 0.52%) vs. Tabu-search 5k best-known solution, and solves QAP100 where Gurobi runs out of memory.
- On QAPLIB (Policy-50 generalization), SAWT achieves the lowest average mean gap of 26.8% across categories versus RGM 35.8% and NGM 62.4%.
- SAWT inference is reported as up to 5350x faster than Tabu-search with 5k steps on QAP100 (per the paper's timing comparison).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SAWT {10k} instead of TS {5k} | QAP solver · QAP20 | Mean: 54.93 -> 54.63 | Helped |
| Use SAWT {10k} instead of TS {5k} | QAP solver · QAP50 | Mean: 380.13 -> 379.96 | Helped |
| Use SAWT {10k} instead of TS {5k} | QAP solver · QAP100 | Mean: 1608.82 -> 1617.23 | Hurt |
| Add Single-AM to the QAP encoder (ablation) | SAWT · QAP20 | Gap: 12.67% -> -0.54% | Helped |
| Add the SAWT-encoder (ablation) | SAWT · QAP20 | Gap: 3.76% -> -0.54% | Helped |
| Train and evaluate with random initial solutions rather than fixed initial solutions (ablation) | SAWT · QAP20 | Mean: 54.63 -> 54.62 | Helped |
| Train and evaluate with random initial solutions rather than fixed initial solutions (ablation) | SAWT · QAP50 | Mean: 379.97 -> 379.35 | Helped |
| Train and evaluate with random initial solutions rather than fixed initial solutions (ablation) | SAWT · QAP100 | Mean: 1617.08 -> 1614.42 | Helped |
| Evaluate with random initial solutions after training with fixed initial solutions (ablation) | SAWT · QAP20 | Mean: 54.63 -> 54.69 | Hurt |
| Evaluate with random initial solutions after training with fixed initial solutions (ablation) | SAWT · QAP50 | Mean: 379.97 -> 380.83 | Hurt |
| Evaluate with random initial solutions after training with fixed initial solutions (ablation) | SAWT · QAP100 | Mean: 1617.08 -> 1622.06 | Hurt |
| Apply the QAP50-pretrained policy to QAPLIB | SAWT · QAPLIB average (12-64) | Mean gap: 35.8 -> 26.8 | Helped |
Surprising findings
- Heuristic and L2I baselines adapted from VRP/TSP solvers perform poorly on QAP, with best L2I gaps several times larger than SAWT's.
- On QAPLIB, SAWT has very large gaps on chr (about 110%) and ste categories, attributed to flow-matrix sparsity distribution shift.
Limitations
- Large gaps on QAPLIB categories with sparse flow matrices (chr, ste, esc), indicating distribution sensitivity.
- Trained only on self-generated dense instances (density p=0.7), limiting generalization.
- Winning rate against TS 5k is only moderate for larger sizes (10.15% at QAP100).
Experimental setup
Datasets: self-generated Koopmans-Beckmann QAP instances QAPLIB
Benchmarks: self-generated QAP10/20/50/100 QAPLIB
Metrics: mean objective gap to best-known solution inference time standard deviation winning rate
Baselines: Gurobi Tabu search SM RRWM IPFP MatNet* Costa Sui Wu Dact NeuOpt RGM
Builds on: MatNet REINFORCE NGM RGM
Closest papers by meaning
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.85)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.85)
- Deep Distributed Optimization for Large-Scale Quadratic Programming (ICLR 2025 · similarity 0.85)
- Differentiation Through Black-Box Quadratic Programming Solvers (NeurIPS 2025 · similarity 0.84)
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing (NeurIPS 2025 · similarity 0.83)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.