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:341-357, 2001.

[AnBr2:00]

K.M. ANSTREICHER and N.W. BRIXIUS. Solving quadratic assignment problems using convex quadratic programming relaxations, Optimization Methods and Software 16:49-68, 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):563-588, 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):917-934, 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. 107-120, 2003.

[BaTe:94]

R. BATTITI and G. TECCHIOLLI. The reactive tabu search. ORSA Journal on Computing, 6(2):126-140, 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):35-49, 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 Case-Studies. PhD Thesis, ETH Zurich, Hartung-Gorre Verlag Konstanz, ISBN 3-89649-299-3, 1997.

[BrClMaPe:96]

A. BRUENGGER, J. CLAUSEN, A. MARZETTA and M. PERREGAARD. Joining forces in solving large-scale 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 three-dimensional assignment problems. In M. Dell'Amico, F. Maffioli, and S. Martello, editors, Annotated Bibliographies in Combinatorial Optimization . 1997. Wiley, Chichester, pp. 373-392.

[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. 241-238.

[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:B121-B132, 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):169-174, 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, 37-5:760-768, 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 branch-and-bound 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):11-127, 1997.

[Connolly:90]

D. T. CONNOLLY. An improved annealing scheme for the QAP. European Journal of Operational Research, 46:93-100, 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 IEEE-ICEC'97 Conference in Indianapolis, April 13-16, 1997.

[DKSo:07]

E. DE KLERK and R. SOTIROV. Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Optimization On-line /2007/06/1684.

[Drez:03]

Z. DREZNER. A New Genetic Algorithm for the Quadratic Assignment Problem, INFORMS Journal of Computing, 15, 320-330, 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.

[Drez:15]

Z. DREZNER. The quadratic assignment problem. In: F. S. da Gama, G. Laporte, and S. Nickel (eds.), Location Science, Springer, 345-363, 2015.

[DrHaTa:03]

Z. DREZNER, P. HAHN and E. TAILLARD. A study of quadratic Assignment Problem Instances that are Difficult for Meta-heuristic Methods. Accepted for publication to a special issue of Annals of Operations Research, devoted to the State-of-the-Art 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, 417-436, 2006.

[DrHaTa:03]

Z. DREZNER, A. MISEVICIUS, and G. PALUBECKIS. Exact Algorithms for the Solution of the Grey Pattern Quadratic Assignment Problem. Mathematical Methods of Operations Research, 82, 85-105, 2015.

[Elshafei:77]

A.N. ELSHAFEI. Hospital layout as a quadratic assignment problem. Operations Research Quarterly, 28:167-179, 1977.

[EsWu:90]

B. ESCHERMANN and H.J. WUNDERLICH. Optimized synthesis of self-testable finite state machines. In 20th International Symposium on Fault-Tolerant Computing (FFTCS 20), Newcastle upon Tyne, 26-28th 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 173-187. 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:305-31, 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:727-739, 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:912-942, 1998.

[HaGrHa:96]

P. HAHN, T. GRANT, and N. HALL. A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method. European Journal of Operational Research, 108:629-640, 1998.

[HHJGSR:99]

P.M. HAHN, W.L. HIGHTOWER, T.A. JOHNSON, M. GUIGNARD-SPIELBERG, and C. ROUCAIROL. Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem. Yugoslavian Journal of Operational Research, 11(1):41-60, 2001.

[HHJGSR:01]

P.M. HAHN, W.L. HIGHTOWER, T.A. JOHNSON, M. GUIGNARD-SPIELBERG, and C. ROUCAIROL. A level-2 reformulation-linearization techinque bound for the Quadratic Assignment Problem. Working Paper 01-04, 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):487-496, 2001.

[Iriyama:97]

H. IRIYAMA. Investigation of searching methods using meta-strategies for quadratic assignment problem and its improvements. Bachelor Thesis, University of Tokyo, Tokyo, Japan, 1997.

[Johnson:92]

T.A. JOHNSON. New linear programming-based solution procedures for the quadratic assignment problem. PhD thesis, Clemson University, Clemson, USA, 1992.

[JueKA:01]

M. JÜNGER and V. KAIBEL. The QAP-polytope and the star transformation, Discrete Applied Mathematics 111(3):283-306, 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. 97-297, 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:351-403, 1999.

[KaRe:95a]

S.E. KARISCH and F. RENDL. Lower bounds for the quadratic assignment problem via triangle decompositions. Mathematical Programming, 71(2):137-152, 1995.

[KrPr:78]

J. KRARUP and P.M. PRUZAN. Computer-aided layout design. Mathematical Programming Study, 9:75-94, 1978.

[Lawler:63]

E. LAWLER. The quadratic assignment problem. Management Science, 9:586-599, 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:163-184, 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 237-261. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1994.

[LoAbBoHaQu:06]

E.M. LOIOLA, N.M.M. DE ABREU, P.O. BOAVENTURA-NETTO, P.M. HAHN, AND T. QUERIDO, A survey for the quadratic assingment problem", Invited Review, European Journal of Operational Research, vol. 176, pp 657-690, 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 tree-search procedures for the quadratic assignment problem. Research Report CSR 97-1, 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, 121-135.

[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:95-111, 2005.

[Mise:04]

A. MISEVICIUS. An improved hybrid genetic algorithm: new results for the quadratic assignment problem, Knowledge-Based Systems, 17:65-73, 2004

[Mise:03]

A. MISEVICIUS. A modified simulated annealing algorithm for the quadratic assignment problem. Informatica, 14:497-514, 2003.

[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:150-173, 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):311-318, 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 1-42. 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: 781-791, 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 meta-heuristic approach, Proceedings of the 18th Annual International Symposium on High Performance Computing Systems and Applications (HPCS), pp. 9-16, M.R. Eskicioglu (Ed.), Department of Computer Science, Winnipeg, Manitoba, Canada, May 16-19, 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:172-187, 1975.

[Skorin:90]

J. SKORIN-KAPOV. Tabu search applied to the quadratic assingnment problem. ORSA Journal on Computing, 2(1):33-45, 1990.

[Steinberg:61]

L. STEINBERG. The backboard wiring problem: a placement algorithm. SIAM Review, 3:37-50, 1961.

[Stu:99]

Th. STÜTZLE. Iterated local search for the quadratic assignment problem. Research Report AIDA-99-3, 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:443-455, 1991.

[Taillard:94]

E.D. TAILLARD. Comparison of iterative searches for the quadratic assingnment problem. Location Science,3:87-105, 1995.

[Taillard:98]

E.D. TAILLARD. FANT: Fast ant system. Technical Report IDSIA-46-98, 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 J-M. 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. MAX-MIN ant system for quadratic assignment problems. Research Report AIDA-97-04, 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:107-119, 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 DIKU-TR-96/32, Department of Computer Science, University of Copenhagen, 1996.

GO BACK TO MAIN PAGE OF QAPLIB

May 2018. Peter Hahn, hahn@seas.upenn.edu