Sequential and Parallel Path-Relinking Algorithms for the Quadratic Assignment Problem

Abstract

The quadratic assignment problem, a classical combinatorial optimization problem, has garnered much attention due to its many applications and solution complexity. This research represents the first use of parallelization for path relinking within the QAP setting. We used a simple form of path relinking to focus on the parallel implementation's elements and to determine their impact when used with a method of this type. Our computational results demonstrate highly attractive outcomes despite the procedure's simplicity and show in particular the value of a well-designed parallelization process in this context.