Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) consists of assigning n facilities to n locations to minimize the total weighted cost of interactions between facilities. The QAP arises in many diverse settings, is known to be NP-hard, and can be solved to optimality only for fairly small instances (typically, n ≤ 30). Neighborhood search algorithms are the most popular heuristic algorithms for solving larger instances of the QAP. The most extensively applied neighborhood structure for the QAP is the 2-exchange neighborhood. This neighborhood is obtained by swapping the locations of two facilities; its size is therefore O(n²). Previous efforts to explore larger neighborhoods (such as 3-exchange or 4-exchange neighborhoods) were not very successful, as it took too long to evaluate the larger set of neighbors. In this paper, we propose very large-scale neighborhood (VLSN) search algorithms when the size of the neighborhood is very large, and we propose a novel search procedure to enumerate good neighbors heuristically. Our search procedure relies on the concept of an improvement graph that allows us to evaluate neighbors much faster than existing methods. In this paper, we present extensive computational results of our algorithms when applied to standard benchmark instances.