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.
[Amin: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.
[BaTe:94]
R. BATTITI and G. TECCHIOLLI. The reactive tabu search. ORSA Journal on Computing, 6(2):126-140, 1994.
[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.
[BrAn:01]
N.W. BRIXIUS and K.M. ANSTREICHER. The Steinberg wiring problem. Working Paper, The University of Iowa, October 2001.
[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.
[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.
[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.
[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), 2001.
[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.
[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>/em> 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.
[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.
[Mise:01]
A. MISEVICIUS. An efficient simulated annealing algorithm for the quadratic assignment problem. Working paper, Kaunas University of Technology, Kaunas, Lithuania, 2001.
[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.
[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
February 2002. Eranda Çela, cela@opt.math.tu-graz.ac.at