Approaching the quadratic assignment problem with kernels of mallows models under the hamming distance
Lists
Only you see this
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.
BibTeX
@inproceedings{arza2019approaching,
author = {Etor Arza and Josu Ceberio and Aritz Pérez and Ekhine Irurozki},
title = {{Approaching the quadratic assignment problem with kernels of mallows models under the hamming distance}},
booktitle = {GECCO (Companion)},
year = {2019},
doi = {10.1145/3319619.3321976},
}