Sinkhorn-Reparameterized Primal-Dual Optimization for Scalable Quadratic Assignment

Finding high-quality solutions to large-scale instances of the quadratic assignment problem (QAP) remains challenging under limited computational budgets. We approach QAP through an equivalent continuous formulation with entrywise integrality constraints over the doubly stochastic domain. Building on this formulation, we propose Sinkhorn-Reparameterized Primal-Dual Optimization (SRPD), which replaces explicit primal projection with a differentiable Sinkhorn parameterization. A finite sequence of Sinkhorn normalizations enables gradient-based primal search in an unconstrained latent space, while entrywise dual updates adapt the objective in response to integrality violations. SRPD then recovers feasible permutations through trajectory harvesting: search trajectories run in parallel on GPUs, and their soft assignments are greedily decoded throughout optimization to retain the best solution. For the finite Sinkhorn map and greedy decoder, we bound the decoding error and returned objective using integrality violations and soft-objective values, and identify sufficient conditions for exact penalization. Experiments on QAPLIB demonstrate competitive solution quality and runtime, with substantial improvements over the projected primal–dual baseline, reducing the average gap from 19.28% to 0.50%. On larger taiXXeYY instances, SRPD achieves substantially lower final gaps than the compared baselines under a common time budget.