EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Iman Seyedi, Antonio Candelieri, Enza Messina, Francesco Archetti

Mathematics · 03.06.2026 · 14 (11) · 1972

DOI: 10.3390/math14111972 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics, online erschienen am 03.06.2026. Verfasst von Iman Seyedi und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 72 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Italian University and Research Ministry.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Italian University and Research Ministry

Zitieren

APA

Seyedi, I., Candelieri, A., Messina, E., & Archetti, F. (2026). Gromov–Wasserstein Meets Combinatorial Optimization: A Scalable Solver for the Capacitated Quadratic Assignment Problem. Mathematics, 14(11), 1972. https://doi.org/10.3390/math14111972

Vancouver

Seyedi I, Candelieri A, Messina E, Archetti F. Gromov–Wasserstein Meets Combinatorial Optimization: A Scalable Solver for the Capacitated Quadratic Assignment Problem. Mathematics. 2026;14(11):1972. doi:10.3390/math14111972

BibTeX
@article{Seyedi2026,
  author = {Seyedi, Iman and Candelieri, Antonio and Messina, Enza and Archetti, Francesco},
  title = {Gromov–Wasserstein Meets Combinatorial Optimization: A Scalable Solver for the Capacitated Quadratic Assignment Problem},
  journal = {Mathematics},
  year = {2026},
  volume = {14},
  number = {11},
  pages = {1972},
  doi = {10.3390/math14111972}
}
Kostenlos starten →