Approaching the Quadratic Assignment Problem with Kernels of Mallows Models under the Hamming Distance

Abstract

The Quadratic Assignment Problem (QAP) is a specially challenging permutation-based np-hard combinatorial optimization problem, since instances of size $n>40$ are seldom solved using exact methods. In this sense, many approximate methods have been published to tackle this problem, including Estimation of Distribution Algorithms (EDAs).

In particular, EDAs have been used to solve permutation problems by introducing distance based exponential models, such as the Mallows Models. In this paper we approximate the QAP with a Hamming distance based kernels of Mallows Models. Based on the benchmark instances, we have observed that our approach is competitive, reaching the best-known solution in $71\%$ of the tested instances, especially on large instances ($n>125$), where it is able to outperform state of the art results in 43 out of 288 instances.