QAP-SCP: Learning Structural Compatibility Priors for Quadratic Assignment

The quadratic assignment problem (QAP) remains challenging under limited search budgets because solution quality depends strongly on which search basins are reached. Rather than replacing combinatorial search, we propose QAP-SCP, a learning framework that predicts where search should begin. Given a QAP instance, QAP-SCP constructs a compatibility-aware structural representation that captures interaction profiles, relative structural roles, and assignment-specific compatibility, and maps them to an additive assignment score matrix. The scorer is trained with staged search-aware supervision: exact local refinement provides both a refined assignment target and exchange-geometry signals, while a compatibility module is introduced as a zero-initialized correction to a learned structural prior. At inference, deterministic and perturbed decoding convert the learned score matrix into a diverse multi-start proposal portfolio, which is filtered using the exact QAP objective and passed to a replaceable search backend. This design preserves exact objective evaluation and backend search dynamics while using learning only to guide initialization. Experiments on QAPLIB, Taixxeyy, and synthetic QAP distributions show that QAP-SCP achieves competitive standalone construction quality and substantially reduces long-tail failures on basin-sensitive instances, while maintaining low final gaps on standard QAP benchmarks. Ablations further show the contributions of compatibility-aware representations, exchange-geometry supervision, and learned proposal diversification.