Geoscience Reference
In-Depth Information
Fig. 13.1 Optimal
configuration of 20 black
points in an 8 8 square
replicated 9 times
Fig. 13.2 Grey patterns of
64 points in a 16 16 square
13.8
Conclusions
The Quadratic Assignment Problem (QAP) is considered to be one of the most
difficult combinatorial optimization problems. The problem was presented and
applications were described. The related layout problem and two extensions were
briefly presented. Exact and heuristic solution methods were listed and best known
results for some test problems reported. We concluded with a depiction of two grey
pattern problems which are a special case of the QAP.
Current exact algorithms can solve mostly problems of up to 30-40 facilities
while heuristic algorithms require long run times to obtain reasonably good
solutions. Research in developing more effective exact and heuristic algorithms will
be very helpful and should be pursued.
References
Adams W, Guignard M, Hahn P, Hightower W (2007) A level-2 reformulation-linearization
technique bound for the quadratic assignment problem. Eur J Oper Res 180:983-996
Ahuja R, Orlin J, Tiwari A (2000) A descent genetic algorithm for the quadratic assignment
problem. Comput Oper Res 27:917-934
Amin S (1999) Simulated jumping. Ann Oper Res 84:23-38
Anstreicher K, Brixius N, Gaux JP, Linderoth J (2002) Solving large quadratic assignment
problems on computational grids. Math Program 91:563-588
Anstreicher KM, Brixius NW (2001) A new bound for the quadratic assignment problem based on
convex quadratic programming. Math Program 89:341-357
Armour GC, Buffa ES (1963) A heuristic algorithm and simulation approach to relative location
of facilities. Manag Sci 9:294-309
Battiti R, Tecchiolli G (1994) The reactive tabu search. ORSA J Comput 6:126-140
Search WWH ::




Custom Search