An Effective Structural Iterative Refinement Technique for Solving the Quadratic Assignment Problem

摘要

The quadratic assignment problem deals with the arrangement of facilities in plants for minimizing the communication cost among the facilities. This problem is one of the focal problems both in academia and industry, absorbing the attention of researchers for more than five decades. Having a variety of applications, this problem has still no effective exact solution strategy, as the number of possible? feasible solutions, even for medium-sized problems, is extremely large. This makes effective heuristics as the only viable solution strategy for this problem. In this paper, a technique is presented which aims at achieving local minimization through refining layouts structurally. For this purpose, the technique uses an efficient linear assignment technique, and enhances layouts based on the feedback provided. The results of extensive computational experiments on different benchmark instances indicate that the procedure is both robust and efficient.