Numerical investigations on quadratic assignment problems

This paper contains a comparative study of the numerical behavior of different algorithms for solving quadratic assignment problems. After the formulation of the problem, branch and bound algorithms are briefly discussed. Then, starting procedures are described and compared by means of numerical results. Modifications of branch and bound procedures for obtaining good suboptimal solutions are treated in the next section. Subsequently, numerical results with the Gaschütz-Ahrens algorithm are reported. In the last section, exchange algorithms are discussed, and it is pointed out how they can be combined efficiently with the Gaschütz-Ahrens procedure and the perturbation method. All suboptimal solutions found in the literature could be improved by these combined methods. In the appendix, test examples and the best known solutions are listed.