On the use of the Doubly Stochastic Matrix models for the Quadratic Assignment Problem (MAEB 2025)

Permutation problems have captured the attention of the combinatorial optimization community for decades due to the challenge they pose. Although their solutions are naturally encoded as permutations, in each problem, the information to be used to optimize them can vary substantially. In this article, we consider the Quadratic Assignment Problem (QAP) as a case study and propose using Doubly Stochastic Matrices (DSMs) under the framework of Estimation of Distribution Algorithms. To that end, we design efficient learning and sampling schemes that enable an effective iterative update of the probability model. Conducted experiments on commonly adopted benchmarks for the QAP prove doubly stochastic matrices to be preferred to four other models for permutations, both in terms of effectiveness and computational efficiency.