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.
[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.
[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.
[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, 59-77, 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: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
Sept 2013. Peter Hahn, hahn@seas.upenn.edu