The Quadratic Assignment Problem: An Experimental Evaluation of Solution Strategies

Abstract

Since procedures for producing optimal solutions to a quadratic assignment problem are computationally infeasible for any but small problems, heuristic techniques for producing approximate solutions must be employed for the solution of real practical problems. This paper presents the results of experimentation that demonstrates that a solution procedure which couples a constructive initial placement technique with simple and inexpensive improvement procedures produces good solutions with very reasonable computation requirements. The results indicate that such an approach would make the solution of large-scale quadratic assignment problems feasible.