The Quadratic Assignment Problem - Location Science - page 335

Resende et al. ( 1995 ). A quadratic programming based lower bound was proposed
by Anstreicher and Brixius ( 2001 ) who reported in a follow-up paper (Anstreicher
et al. 2002 ) the optimal solution of the Nug30 (Nugent et al. 1968 ) instance. The
process was run in parallel on hundreds of computers that would take about 7
years on a single computer. The “Reformulation-Linearization Technique” (RLT)
was developed by Sherali and Adams ( 1990 , 1998 ) and utilized by Hahn and Grant
( 1998 ) as a Level-1 LRT. Later it was extended to Level-2 LRT by Adams et al.
( 2007 ), and Level-3 by Hahn et al. ( 2012 ). Other lower bounds include the Level-2
RLT interior point bound by Ramakrishnan et al. ( 2002 ), the SDP bound by Roupin
( 2004 ), the lift-and-project SDP bound by Burer and Vandenbussche ( 2006 ), and the
bundle method bound by Rendl and Sotirov ( 2007 ).
Most of the problems solved optimally are based on no more than 30 facilities.
Nyström ( 1999 ) reported the optimal solution of the n D 36 (Steinberg 1961 )
problem. Drezner et al. ( 2005 ) proposed problems whose optimal solution is known
and problems with up to 72 facilities are optimally solved. The special structure of
grey pattern problems enables more efficient solution algorithms. The n D 64 grey
pattern problem of uniformly placing m D 13 black points in a 64 points square
(termed Tai64c) was optimally solved by Drezner ( 2006 ) in about 2 h of computer
time. Drezner ( 2006 ) also optimally solved n D 256 problems with 3 m 8
black points. The Tai64c problem was also solved later by Fischetti et al. ( 2012 )in
about 5 h, and by Nyberg and Westerlund ( 2012 ) in about 50 h. Drezner et al. ( 2014 )
developed a more efficient branch-and-bound approach which optimally solved the
Tai64c problem in about 15 s of computer time.

13.6 Heuristic Solution Algorithms

Optimal algorithms can solve relatively small problems. Consequently, considerable
effort has been devoted to constructing heuristic algorithms.
The first heuristic approaches based on a descent type heuristic of checking
some or all exchanges between facilities were proposed by Gilmore ( 1962 ), CRAFT
(Buffa et al. 1962 ) and Hillier and Connors ( 1966 ). Nugent et al. ( 1968 ) suggested
a biased sampling of exchanges rather than checking all of them. All exchanges
between pairs of facilities define a “neighborhood” of solutions which serves as a
basis for more recent metaheuristic algorithms.
In order to calculate all the values of the objective function in the neighborhood,
n.n 1/=2 possible pair exchanges need to be evaluated. Evaluating each value
directly by ( 13.1 ) requires O.n 2 / time leading to a total of O.n 4 / time. Burkard and
Rendl ( 1984 ) suggested a short cut that we present for symmetric problems with
zero diagonal (i.e., the cost between a facility and itself, and the distance between
the same two locations is zero). Note, however, that this can be easily generalized
to non symmetric problems. Let f rs be the change in the cost f , calculated by