Deterministic interchange algorithms for the quadratic assignment problem

The quadratic assignment problem (QAP) is a combinatorial optimization problem in which the total cost of an assignment of objects (facilities) to sites (locations) is to be minimized. Unlike the linear assignment problem, the QAP explicitly considers the costs associated with the flow or interaction between the facilities. Several authors (e.g., Steinberg (1961)) have advanced practical applications of the QAP in commercial or industrial settings. Several mathematical formulations of the problem are presented, and the problem is situated among the classical Operations Research problems. Likewise, the problem is situated with the topics of Locational Analysis, with specific attention to Facilities Layout. Results from Computer Complexity are introduced which indicate that the QAP is a very difficult problem, and its exact solution is likely to be computationally infeasible for large sized problems. Considerable research attention has been devoted to the QAP. This research is summarized, chronological surveys of the exact and heuristic algorithms are included, and related statistical results are discussed. Several characteristics of the QAP solution space are examined, both theoretically and computationally. One class of solution algorithms, those based on deterministic interchange improvements, is singled out for specific treatment. Several algorithms of this type are compared statistically on their ability to yield good assignments, and on the computational effort required. The concept of algorithm \u27utility\u27 is introduced, which unifies the ability of the algorithm to achieve near optimal solutions and the computational effort required. It is shown that repetitive applications of the simpler algorithms is a better investment in computational effort (higher utility) than a single application of the intricate algorithms. A new interactive heuristic technique called QAPDWELL is proposed and evaluated against several benchmark problems. The algorithm is shown to perform well as an improvement technique, and exhibits several desirable features (e.g., flexibility and portability)