Solving Quadratic Assignment Problems by ‘Simulated Annealing’

Abstract

Recently, an interesting analogy between problems in combinatorial optimization and statistical mechanics has been developed and has proven useful in solving certain traditional optimization problems such as computer design, partitioning, component placement, wiring, and traveling salesman problems. The analogy has resulted in a methodology, termed “simulated annealing,” which, in the process of iterating to an optimum, uses Monte Carlo sampling to occasionally accept solutions to discrete optimization problems which increase rather than decrease the objective function value. This process is counter to the normal ‘steepest-descent’ algorithmic approach. However, it is argued in the analogy that by taking such controlled uphill steps, the optimizing algorithm need not get “stuck” on inferior solutions. This paper presents an application of the simulated annealing method to solve the quadratic assignment problem (QAP). Performance is tested on a set of “standard” problems, as well as some newly generated larger problems (n = 50 and n = 100). The results are compared to those from other traditional heuristics, e.g., CRAFT, biased sampling, and a revised Hillier procedure. It is shown that under certain conditions simulated annealing can yield higher quality (lower cost) solutions at comparable CPU times. However, the simulated annealing algorithm is sensitive to a number of parameters, some of whose effects are investigated and reported herein through the analysis of an experimental design.