QAPLIB  A Quadratic Assignment Problem Library
R.E. BURKARD, E. ÇELA, S.E. KARISCH and F. RENDL
References
 [AnBr1:00]

K.M. ANSTREICHER and N.W. BRIXIUS,
A new bound for the quadratic assignment problem based on convex quadratic
programming,
Mathematical Programming 80:341357, 2001.
 [AnBr2:00]

K.M. ANSTREICHER and N.W. BRIXIUS.
Solving quadratic assignment problems using convex quadratic
programming relaxations,
Optimization Methods and Software 16:4968, 2001.
 [AnBrGoLi:01]

K.M. ANSTREICHER, N.W. BRIXIUS, J.P. GOUX, and J.LINDEROTH.
Solving large quadratic assignment problems on computational grids,
Mathematical Programming 91(3):563588, 2002.
 [Amin:98]

S. AMIN. Simulated Jumping. Annals of Operations Research, 1998.
To appear.
 [AhOrTi:98]

R. AHUJA, J.B. ORLIN and A. TIVARI.
A greedy genetic algorithm for the quadratic assignment problem.
Comput. Oper. Res., 27(10):917934, 2000.
To appear.
 [BaChCoLau:03]

J. BALAKRISHNAN, C.H. CHENG, D.G. CONWAY AND C.M. LAU.
A hybrid genetic algorithm for the dynamic plant layout problem,
International Journal of Production Economics, vol. 86:2, pp. 107120, 2003.
 [BaTe:94]

R. BATTITI and G. TECCHIOLLI. The reactive tabu search.
ORSA Journal on Computing, 6(2):126140, 1994.
 [BlElFaWi:03]

A. BLANCHARD, S. ELLOUMI, A. FAYE and N. WICKER. Un algorithme de
génération de coupes pour le problème de
l'affectation quadratique.
INFOR, 41(1):3549, 2003.
 [Bouras:96]

A. BOURAS,
Problème d'affectation quadratique de petit rang; modèles, compléxite, et applications,
PhD Thesis, L'Université Joseph Fourier, Grenoble, France.
 [Brixius:00]

N.W. BRIXIUS.
Solving Large Scale Quadratic Assignment Problems. PhD
Thesis, University of Iowa, USA, 2000.
 [BrAn:01]

N.W. BRIXIUS and K.M. ANSTREICHER.
The Steinberg wiring problem.
Working Paper, The University of Iowa, October 2001.
 [Bruengger:97]

A. BRUENGGER.
Solving Hard Combinatorial Optimization Problems in Parallel:
Three CaseStudies. PhD Thesis, ETH Zurich, HartungGorre Verlag
Konstanz, ISBN 3896492993, 1997.
 [BrClMaPe:96]

A. BRUENGGER, J. CLAUSEN, A. MARZETTA and M. PERREGAARD.
Joining forces in solving largescale quadratic assignment problems in
parallel. DIKU Technical Report, University of Copenhagen, 1996.
 [BrMa:97]

A. BRUENGGER and A. MARZETTA.
Private communication, 1997.
 [Burkard:91]

R.E. BURKARD. Locations with spatial interactions: the quadratic assignment
problem. In P.B. Mirchandani and R.L. Francis, editors, Discrete
Location Theory. Wiley, Berlin, 1991.
 [BuCe:96]

R.E. BURKARD and E. ÇELA.
Quadratic and threedimensional assignment problems.
In M. Dell'Amico, F. Maffioli, and S. Martello, editors,
Annotated Bibliographies in Combinatorial Optimization . 1997.
Wiley, Chichester, pp. 373392.
 [BCPP:98]

R.E. BURKARD, E. ÇELA, P.M. PARDALOS and L. PITSOULIS.
The quadratic assignment problem.
In P.P. Pardalos and M.G.C. Resende, editors,
Handbook of Combinatorial Optimization, 1998.
Kluwer Academic Publishers, Dordrecht, pp. 241238.
 [BuDe:80]

R.E. BURKARD and U. DERIGS.
Assignment and matching problems: Solution methods with fortran
programs, volume 184 of Lecture Notes in Economics and Mathematical
Systems.
Springer, Berlin, 1980.
 [BuOf:77]

R.E. BURKARD and J. OFFERMANN.
Entwurf von Schreibmaschinentastaturen mittels quadratischer
Zuordnungsprobleme.
Zeitschrift für Operations Research, 21:B121B132, 1977.
 [BuRe:84]

R.E. BURKARD and F. RENDL.
A thermodynamically motivated simulation procedure for combinatorial
optimization problems.
European Journal of Operations Research, 17(2):169174, 1984.
 [Cela:95]

E. ÇELA.
The quadratic assignment problem: special cases and relatives.
PhD thesis, Graz University of Technology, Graz, Austria, 1995.
 [Cela:98]

E. ÇELA.
The Quadratic Assignment Problem: Theory and Algorithms.
Kluwer Academic Publishers, Dordrecht, 1998.
 [ChBe:89]

N. CHRISTOFIDES and E. BENAVENT.
An exact algorithm for the quadratic assignment problem.
Operations Research, 375:760768, 1989.
 [CEKPT:96]

J. CLAUSEN, T. ESPERSEN, S.E. KARISCH, M. PERREGAARD, N. SENSEN and
S. TSCHÖKE.
Benchmark testing for quadratic assignment problems on a portable parallel
branchandbound library. Work in progress, 1996.
 [ClPe:94]

J. CLAUSEN and M. PERREGAARD.
Solving large quadratic assignment problems in parallel.
Computational Optimization and Applications, 8(2):11127, 1997.
 [Connolly:90]

D. T. CONNOLLY.
An improved annealing scheme for the QAP.
European Journal of Operational Research, 46:93100, 1990.
 [CuMaMiTa:97]

V.D. CUNG, T. MAUTOR, P. MICHELON and A. TAVARES.
A scatter search based approach for the quadratic assignment problem.
Proceedings of the IEEEICEC'97 Conference in Indianapolis,
April 1316, 1997.
 [DKSo:07]

E. DE KLERK and R. SOTIROV.
Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Optimization Online /2007/06/1684.
 [Drez:03]

Z. DREZNER.
A New Genetic Algorithm for the Quadratic Assignment Problem, INFORMS Journal of Computing, 15, 320330, 2003.
 [Drez:02]

Z. DREZNER.
Robust heuristic algorithms for the quadratic assignment problem.
College of Business and Economics, California State University  Fullerton,
CA, USA, January 2002.
 [DrHaTa:03]

Z. DREZNER, P. HAHN and E. TAILLARD.
A study of quadratic Assignment Problem Instances that are Difficult for
Metaheuristic Methods.
Accepted for publication to a special issue of Annals of Operations Research,
devoted to the StateoftheArt in Integer Programming, Editors M. Guignard
Spielberg and K. Spielberg, 2004.
 [Drez:06]

Z. DREZNER.
"Finding a Cluster of Points and the Grey Pattern Quadratic Assignment Problem," OR Spectrum, 28, 417436.
 [Elshafei:77]

A.N. ELSHAFEI.
Hospital layout as a quadratic assignment problem.
Operations Research Quarterly, 28:167179, 1977.
 [EsWu:90]

B. ESCHERMANN and H.J. WUNDERLICH.
Optimized synthesis of selftestable finite state machines.
In 20th International Symposium on FaultTolerant Computing
(FFTCS 20), Newcastle upon Tyne, 2628th June, 1990.
 [FlFe:94]

C. FLEURENT and J.A. FERLAND.
Genetic hybrids for the quadratic assignment problem.
In P. Pardalos and H. Wolkowicz, editors, Quadratic assignment
and related problems, volume 16, pages 173187. DIMACS Series
in Discrete Mathematics and Theoretical Computer Science, 1994.
 [Gilmore:62]

P.C. GILMORE.
Optimal and suboptimal algorithms for the quadratic assignment
problem.
SIAM Journal on Applied Mathematics, 10:30531, 1962.
 [Giovannetti:97]

M. GIOVANNETTI.
Methaheuristic and exact algorithms for the quadratic assignment
problem.
University of Bologna, Cesena Site, 1997.
 [HaReWo:92]

S.W. HADLEY, F. RENDL, and H. WOLKOWICZ.
A new lower bound via projection for the quadratic assignment
problem.
Mathematics of Operations Research, 17:727739, 1992.
 [Hahn:68]

P.M. HAHN.
Minimization of Cost in Assignment of Codes to Data Transmission.
Ph.D. Dissertation, University of Pennsylvania, Philadelphia, UMI, Ann Arbor Michigan, Order No. 6905628, 1968.
 [HaGr:95]

P.M. HAHN and T. GRANT.
Lower bounds for the quadratic assignment problem based upon a dual
formulation. Operations Research, 46:912942, 1998.
 [HaGrHa:96]

P. HAHN, T. GRANT, and N. HALL.
A branchandbound algorithm for the quadratic assignment problem based
on the Hungarian method. European Journal of Operational
Research, 108:629640, 1998.
 [HHJGSR:99]

P.M. HAHN, W.L. HIGHTOWER, T.A. JOHNSON, M. GUIGNARDSPIELBERG, and C. ROUCAIROL.
Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem.
Yugoslavian Journal of Operational Research, 11(1):4160, 2001.
 [HHJGSR:01]

P.M. HAHN, W.L. HIGHTOWER, T.A. JOHNSON, M. GUIGNARDSPIELBERG, and C. ROUCAIROL.
A level2 reformulationlinearization techinque bound for the Quadratic Assignment Problem.
Working Paper 0104, Systems Engineering Department, University of Pennsylvania, 2001.
 [HaKr:01]

P. HAHN and J. KRARUP.
A hospital facility problem finally solved. The Journal of Intelligent Manufacturing, 12(5/6):487496, 2001.
 [Iriyama:97]

H. IRIYAMA.
Investigation of searching methods using metastrategies
for quadratic assignment problem and its improvements.
Bachelor Thesis, University of Tokyo, Tokyo, Japan, 1997.
 [Johnson:92]

T.A. JOHNSON.
New linear programmingbased solution procedures for the
quadratic assignment problem.
PhD thesis, Clemson University, Clemson, USA, 1992.
 [JueKA:01]

M. JÜNGER and V. KAIBEL.
The QAPpolytope and the star transformation,
Discrete Applied Mathematics 111(3):283306, 2001.
 [Kaibel:97]

V. KAIBEL.
Polyhedral combinatorics of the quadratic assignment problem.
PhD thesis, University of Cologne, Cologne, Germany, 1997.
 [Kaibel:97a]

V. KAIBEL.
Polyhedral combinatorics of QAPs with less objects than locations.
Technical Report Nr. 97297, Angewandte Mathematik und Informatik, Universitaet
zu Koeln, Cologne, Germany, 1997.
 [Karisch:95]

S.E. KARISCH.
Nonlinear approaches for the quadratic assignment and graph
partition problems.
PhD thesis, Graz University of Technology, Graz, Austria, 1995.
 [KaCeClEs:98]

S.E. KARISCH, E. CELA, J. CLAUSEN, and T. ESPERSEN.
A dual framework for lower
bounds of the quadratic assignment problem based on linearization.
Computing 63:351403, 1999.
 [KaRe:95a]

S.E. KARISCH and F. RENDL.
Lower bounds for the quadratic assignment problem via triangle
decompositions.
Mathematical Programming, 71(2):137152, 1995.
 [KrPr:78]

J. KRARUP and P.M. PRUZAN.
Computeraided layout design.
Mathematical Programming Study, 9:7594, 1978.
 [Lawler:63]

E. LAWLER.
The quadratic assignment problem.
Management Science, 9:586599, 1963.
 [Li:92]

Y. LI.
Heuristic and exact algorithms for the quadratic assignment
problem.
PhD thesis, The Pennsylvania State University, USA, 1992.
 [LiPa:92]

Y. LI and P.M. PARDALOS.
Generating quadratic assignment test problems with known optimal
permutations.
Computational Optimization and Applications, 1:163184, 1992.
 [LiPaRe:94]

Y. LI, P.M. PARDALOS, and M.G.C. RESENDE.
A greedy randomized adaptive search procedure for the quadratic
assignment problem.
In P. Pardalos and H. Wolkowicz, editors, Quadratic assignment
and related problems, volume 16, pages 237261. DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, 1994.
 [LoAbBoHaQu:06]

E.M. LOIOLA, N.M.M. DE ABREU, P.O. BOAVENTURANETTO, P.M. HAHN, AND T. QUERIDO,
A survey for the quadratic assingment problem", Invited Review, European
Journal of Operational Research, vol. 176, pp 657690, 2006.
 [Malucelli:93]

F. MALUCELLI.
Quadratic assignment problems: solution methods and
applications.
PhD thesis, University of Pisa, Pisa, Italy, 1993.
 [Maniezzo:97]

V. MANIEZZO.
Exact and approximate nondeterministic treesearch procedures
for the quadratic assignment problem.
Research Report CSR 971, Scienze dell'Informazione, Cesena site,
University of Bologna, 1997.
 [Mautor:92]

T. MAUTOR.
Contribution à la résolution des problèmes
d'implanation: algorithmes séquentiels et parallèles pour
l'affectation quadratique.
PhD thesis, Université Pierre et Marie Curie, Paris, France,
1992.
 [Mills:02]

P. MILLS.
Extensions to Guided Local
Search, PhD Thesis, Department of
Computer Science, University of Essex, 2002.
 [Mills:03]

P. MILLS, E.P.E. TSANG and J. FORD.
Applying an Extended Guided Local
Search on the Quadratic
Assignment Problem, Annals of Operations Research, Kluwer Academic
Publishers, Vol.118, 2003, 121135.
 [Mise:08]

A. MISEVICIUS.
An implementation of the iterated tabu search algorithm for the quadratic assignment problem.
Working Paper, Kaunas University of Technology,
Kaunas, Lithuania, 2008.
 [Mise:05]

A. MISEVICIUS.
A tabu search algorithm for the quadratic assignment problem.
Computational Optimization and Applications,
30:95111, 2005.
 [Mise:04]

A. MISEVICIUS.
An improved hybrid genetic algorithm: new results for the quadratic assignment problem,
KnowledgeBased Systems, 17:6573, 2004
 [Mise:03]

A. MISEVICIUS.
A modified simulated annealing algorithm for the quadratic assignment problem.
Informatica, 14:497514, 2003.
 [Mitt:10]

J. PENG, H. D. MITTELMANN, and X. LI.
A New Relaxation Framework for Quadratic Assignment Problems based on Matrix Splitting, Math. Prog. Comp. 2, 5977, 2010.
 [NuVoRu:68]

C.E. NUGENT, T.E. VOLLMAN, and J. RUML.
An experimental comparison of techniques for the assignment of
facilities to locations.
Operations Research, 16:150173, 1968.
 [Ny:99]

M. NYSTRÖM.
Solving certain large instances of the quadratic assignment problem: Steinberg's examples.
Working paper, California Institute of Technology, 1999.
 [OsRu:96]

T. OSTROWSKI and V.T. RUOPPILA.
Genetic annealing search for index assignment in vector quantization.
Technical Report, Pattern Recognition Letters, 18(4):311318, 1997.
 [PaReWo:94]

P.M. PARDALOS, F. RENDL, and H. WOLKOWICZ.
The quadratic assignment problem: a survey of recent developments.
In P. Pardalos and H. Wolkowicz, editors, Quadratic assignment
and related problems, volume 16, pages 142. DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, 1994.
 [PaWo:94]

P.M. PARDALOS and H. WOLKOWICZ, editors.
Quadratic assignment and related problems, volume 16 of
DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, 1994.
 [ReRaDr:94]

M.G.C. RESENDE, K.G. RAMAKRISHNAN, and Z. DREZNER.
Computing lower bounds for the quadratic assignment problem with an
interior point algorithm for linear programming.
Operations Research, 43: 781791, 1995.
 [Rijal:95]

M. RIJAL.
Scheduling, design and assignment problems with quadratic
costs.
PhD thesis, New York University, New York, USA, 1995.
 [Rodriguez:04]

J.M. RODRIGUEZ.
An integrated system for the design of agile plant layouts, Unpublished Doctoral Dissertation, Department of Mechanical Engineering, University of New Brunswick, Fredericton, NB, Canada. (2004)
 [RoMcBoBh:04]

J.M. RODRIGUEZ, F.C. MacPHEE, D.J. BONHAM and V.C. BHAVSAR.
Solving the quadratic assignment and dynamic plant layout problems using a new hybrid metaheuristic approach, Proceedings of the 18th Annual International Symposium on High Performance Computing Systems and Applications (HPCS), pp. 916, M.R. Eskicioglu (Ed.), Department of Computer Science, Winnipeg, Manitoba, Canada, May 1619, 2004
 [Roucairol:87]

C. ROUCAIROL.
Du sequentiel au parallele: la recherche arborescente et son
application a la programmation quadratique en variables 0 et 1, 1987.
Thèse d'Etat, Université Pierre et Marie Curie, Paris,
France.
 [ScVe:75]

M. SCRIABIN and R.C. VERGIN.
Comparison of computer algorithms and visual based methods for plant
layout.
Management Science, 22:172187, 1975.
 [Skorin:90]

J. SKORINKAPOV.
Tabu search applied to the quadratic assingnment problem.
ORSA Journal on Computing, 2(1):3345, 1990.
 [Steinberg:61]

L. STEINBERG.
The backboard wiring problem: a placement algorithm.
SIAM Review, 3:3750, 1961.
 [Stu:99]

Th. STÜTZLE.
Iterated local search for the quadratic assignment problem.
Research Report AIDA993, Department of Computer Science,
Darmstadt University of Technology, Germany.
 [Taillard:91]

E.D. TAILLARD.
Robust tabu search for the quadratic assingnment problem.
Parallel Computing, 17:443455, 1991.
 [Taillard:94]

E.D. TAILLARD.
Comparison of iterative searches for the quadratic assingnment
problem.
Location Science,3:87105, 1995.
 [Taillard:98]

E.D. TAILLARD.
FANT: Fast ant system.
Technical Report IDSIA4698, Lugano, 1998.
 [TaGa:97]

E.D. TAILLARD and L.M. GAMBARDELLA.
Adaptive memories for the quadratic assingnment problem.
Research report, IDSIA Lugano, Switzerland, 1997.
 [TaHaGe:97]

E.G. TALBI, Z. HAFIDI, and JM. GEIB.
Parallel adaptive tabu search for large optimization problems.
Research report, LIFL, University of Lille, March 1997.
 [ThBo:94]

U.W. THONEMANN and A. BÖLTE.
An improved simulated annealing algorithm for the quadratic
assignment problem.
Working paper, School of Business, Department of Production and
Operations Research, University of Paderborn, Germany, 1994.
 [Stuetzle:97]

T. STÜTZLE.
MAXMIN ant system for quadratic assignment problems.
Research Report AIDA9704, Department of Computer Schience, Darmstadt
University of Technology, Germany, 1997.
 [WiWa:87]

M.R. WILHELM and T.L. WARD.
Solving quadratic assignment problems by simulated annealing.
IIE Transaction, 19/1:107119, 1987.
 [Zhao:96]

Q. ZHAO.
Semidefinite programming for assignment and partitioning problems.
PhD thesis, University of Waterloo, Waterloo, Canada, 1996.
 [ZhKaReWo:96]

Q. ZHAO, S.E. KARISCH, F. RENDL, and H. WOLKOWICZ.
Semidefinite programming relaxations for the quadratic assignment
problem.
Technical Report DIKUTR96/32, Department of Computer Science, University of
Copenhagen, 1996.
GO BACK TO MAIN PAGE OF QAPLIB