Geoscience Reference
In-Depth Information
There are nŠ possible permutations. The optimal solution is the best such permuta-
tion. Note that adding a constant to all c
ij
does not change the solution. The objective
function is increased by a constant (the common weight increase multiplied by the
sum of the distances). Therefore, if there are negative weights, a constant can be
added to all weights so that all weights are positive if this is required for a solution
procedure.
The original formulation of the QAP by Koopmans and Beckmann (
1957
)is
based on defining n
2
binary variables so that x
ij
D
1 if facility i is located at site j
and x
ij
D
0 otherwise. The problem is then:
8
<
9
=
n
n
n
n
X
X
X
X
minimize
f
D
c
ij
d
rs
x
ir
x
js
(13.2)
:
;
iD1
jD1
rD1
sD1
subject to
X
n
x
ij
D
1;
j
D
1;:::;n;
iD1
X
n
x
ij
D
1;
i
D
1;:::;n;
jD1
x
ij
2f
0;1
g
;
i;j
D
1;:::;n;
hence the name “Quadratic Assignment Problem”. The constraints are identical to
those of the linear assignment problem (Burkard and Cela
1999
) but the objective
function is quadratic rather than linear.
The QAP was proven to be NP-hard by Sahni and Gonzalez (
1976
). Even
obtaining an "-approximation for a given ">0cannot be done in polynomial time
unless P
D
NP.
Reviews of the quadratic assignment problem include Burkard (
1990
,
2013
),
Cela (
1998
), Rendl (
2002
), Taillard (
1995
), Drezner et al. (
2005
), Drezner (
2008a
),
Drezner and Misevicius (
2013
), and Loiola et al. (
2007
).
The web site QAPLIB (
http://www.seas.upenn.edu/qaplib
)
includes comprehen-
sive and up to date information on the quadratic assignment problem such as
research papers and solution results of test instances. There are sets of problems
for which the optimal solution is known by design. Two of them are reported in Li
and Pardalos (
1992
) and Drezner et al. (
2005
).
13.2
Applications
There are many applications that can be formulated and solved as quadratic
assignment problems. Examples of such applications are listed here.
