PLMA: A New Framework for Solving Quadratic Assignment Problems

arXiv:2604.20109 introduces PLMA, a permutation learning framework for the quadratic assignment problem (QAP), a fundamental NP-hard task. PLMA features an efficient warm-started MCMC finetuning procedure that enhances deployment-time performance by using short Markov chains to anchor adaptation to promising regions. For rapid exploration over permutation space, it employs an additive energy-based model (EBM) enabling O(1)-time 2-swap Metropolis-Hastings sampling. The neural network parameterizing the EBM incorporates a scalable cross-graph attention mechanism to model interactions between facilities. This work addresses the challenge of achieving consistently competitive performance across structurally diverse real-world QAP instances, bridging the gap between traditional heuristics and learning-based solvers.