The quadratic assignment problem: A survey and recent developments 论文

摘要

. Quadratic Assignment Problems model many applications in diverse areas such as operations research, parallel and distributed computing, and combinatorial data analysis. In this paper we survey some of the most important techniques, applications, and methods regarding the quadratic assignment problem. We focus our attention on recent developments. 1. Introduction Given a set N = f1; 2; : : : ; ng and n \\Theta n matrices F = (f ij ) and D = (d kl ), the quadratic assignment problem (QAP) can be stated as follows: min p2\\Pi N n X i=1 n X j=1 f ij d p(i)p(j) + n X i=1 c ip(i) ; where \\Pi N is the set of all permutations of N . One of the major applications of the QAP is in location theory where the matrix F = (f ij ) is the flow matrix, i.e. f ij is the flow of materials from facility i to facility j, and D = (d kl ) is the distance matrix, i.e. d kl represents the distance from location k to location l [62, 67, 137]. The cost of simultaneously assigning facility i to locat...