A Local Search Based on Variant Variable Depth Search for the Quadratic Assignment Problem
Takeshi Okano, Kengo Katayama, Kazuho Kanahara, Noritaka Nishihara · 2018
The quadratic assignment problem (QAP) has practical applications in the electronics domain, such as component placing on circuit boards, minimizing the number of transistors on integrated circuits, optimal placing of letters on touchscreen devices, etc. Since QAP is NP-hard and large problems are not practically solvable to optimality, heuristic methods such as local search are regarded as an efficient algorithm to obtain nearoptimal solutions within a reasonable time. In this paper, we present a new sophisticated local search algorithm, called variant k-opt local search (vKLS), based on a variant of the variable depth search for QAP. Computational results show that vKLS is capable of finding better solutions on average than the standard VDS and typical 2-opt local search algorithms.