Gromov–Wasserstein Meets Combinatorial Optimization: A Scalable Solver for the Capacitated Quadratic Assignment Problem

The Capacitated Quadratic Assignment Problem (CQAP) arises in logistics and network design, requiring the allocation of tasks to agents under quadratic interaction costs and capacity constraints. Classical exact solvers become computationally infeasible for large-scale instances, while heuristic methods such as Genetic Algorithms suffer from scalability limitations and sensitivity to local optima, leaving a gap for principled scalable approximations. In this paper, we address CQAP using the Gromov–Wasserstein (GW) framework, derived from Optimal Transport (OT) theory. In particular, we propose a multi-initialization GW strategy (GW_MultiInit) that mitigates the local optima problem inherent to non-convex GW optimization and scales efficiently to large problem sizes. Computational experiments on synthetic CQAP instances show that GW_MultiInit consistently achieves solutions close to the exact optimum for small- and medium-scale problems, and outperforms heuristic baselines such as the genetic algorithm at large scale in both runtime and solution quality across the benchmarks tested. To validate generalizability, we further evaluate GW_MultiInit On 17 QAPLIB benchmark instances adapted to the CQAP setting, GW_MultiInit achieves the best approximate result on 15 out of 17 instances with an average optimality gap of 0.34%, demonstrating strong generalizability beyond synthetic data. Additional comparisons with Entropic GW and Fused GW highlight practical trade-offs between accuracy, speed, and parameter sensitivity, offering guidelines for real-world deployment. Our results suggest that GW-based methods, and GW_MultiInit in particular, offer a promising and scalable approach for CQAP and related large-scale assignment problems within the problem scales examined.