A Parallel Tabu Search for the Large-scale Quadratic Assignment Problem

Omar Abdelkafi (1, 2) , Bilel Derbel (1) , Arnaud Liefooghe (2)

1 BONUS - Optimisation de grande taille et calcul large échelle
2 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189

Parallelization is an important paradigm for solving massive optimization problems. Understanding how to fully benefit form the aggregated computing power and what makes a parallel strategy successful is a difficult issue. In this study, we propose a simple parallel iterative tabu search (PITS) and study its effectiveness with respect to different experimental settings. Using the quadratic assignment problem (QAP) as a case study, we first consider different small-and medium-size instances from the literature and then tackle a large-size instance that was rarely considered due the its inherent solving difficulty. In particular, we show that a balance between the number of function evaluations each parallel process is allowed to perform before resuming the search is a critical issue to obtain an improved quality.

Mots clés: Big Optimization; Quadratic assignment problem; Iterative tabu search

Domaines: Intelligence artificielle [cs.AI]; Calcul parallèle, distribué et partagé [cs.DC]; Recherche opérationnelle [math.OC]

Omar Abdelkafi, Bilel Derbel, Arnaud Liefooghe. A Parallel Tabu Search for the Large-scale Quadratic Assignment Problem. IEEE CEC 2019 - IEEE Congress on Evolutionary Computation, Jun 2019, Wellington, New Zealand. ⟨hal-02179193⟩