An improved annealing scheme for the QAP

Recently there has been some interest in the use of Simulated Annealing to obtain ‘good’ solutions to a number of combinatorial problems. This paper reports on the use of this method applied to the Quadratic Assignment Problem (i.e. the assignment of inter-communicating objects to locations to minimize the total cost of communication between them). The result is a much-improved annealing scheme for this problem which performs well on a range of examples, finding improved solutions for several of the largest problems available in the literature and requiring only modest amounts of computational effort.