The Quadratic Assignment Problem

1. E. H. L. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, Wiley, Chichester, 1989.

   MATH  Google Scholar 

2. E. Aarts and J. K. Lenstra, eds., Local Search in Combinatorial Optimization, Wiley, Chichester, 1997.

   MATH  Google Scholar 

3. W. P. Adams and T. A. Johnson, Improved linear programming-based lower bounds for the quadratic assignment problem, in Quadratic Assignment and Related Problems, P. M. Pardalos and H. Wolkowicz, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science 16, 1994, 43–75, AMS, Providence, RI.

   Google Scholar 

4. W. P. Adams and H. D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science 32, 1986, 1274–1290.

   Article  MATH  MathSciNet  Google Scholar 

5. W. P. Adams and H. D. Sherali, Linearization strategies for a class of zero-one mixed integer programming problems, Operations Research 38, 1990, 217–226.

   Article  MATH  MathSciNet  Google Scholar 

6. R. K. Ahuja, J. B. Orlin, and A. Tivari, A greedy genetic algorithm for the quadratic assignment problem, Working paper 3826–95, Sloan School of Management, MIT, 1995.

   Google Scholar 

7. S. Arora, A. Frieze, and H. Kaplan, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Proceedings of the 37-th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1996, 21–30.

   Google Scholar 

8. A. A. Assad, and W. Xu, On lower bounds for a class of quadratic 0–1 programs, Operations Research Letters 4, 1985, 175–180.

   Article  MATH  MathSciNet  Google Scholar 

9. E. Balas and J. B. Mazzola, Quadratic 0–1 programming by a new linearization, presented at the Joint ORSA/TIMS National Meeting, 1980, Washington D.C.

   Google Scholar 

10. E. Balas and J. B. Mazzola, Nonlinear programming: I. Linearization techniques, Mathematical Programming 30, 1984, 1–21.

    Article  MATH  MathSciNet  Google Scholar 

11. E. Balas and J. B. Mazzola, Nonlinear programming: II. Dominance relations and algorithms, Mathematical Programming 30, 1984, 2245.

    Google Scholar 

12. A. I. Barvinok, Computational complexity of orbits in representations of symmetric groups, Advances in Soviet Mathematics 9, 1992, 161–182.

    MathSciNet  Google Scholar 

13. R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA Journal on Computing 6, 1994, 126–140.

    MATH  Google Scholar 

14. M. S. Bazaraa and O. Kirca, Branch and bound based heuristics for solving the quadratic assignment problem, Naval Research Logistics Quarterly 30, 1983, 287–304.

    Article  MATH  MathSciNet  Google Scholar 

15. M. S. Bazaraa and H. D. Sherali, Benders’ partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Research Logistics Quarterly 27, 1980, 29–41.

    Article  MATH  MathSciNet  Google Scholar 

16. M. S. Bazaraa and H. D. Sherali, On the use of exact and heuristic cutting plane methods for the quadratic assignment problem, Journal of Operations Research Society 33, 1982, 991–1003.

    MATH  MathSciNet  Google Scholar 

17. G. Birkhoff, Tres observaciones sobre el algebra lineal, Univ. Nac. Tucumán Rev., Ser. A, 1946, 147–151

    Google Scholar 

18. B. Bollobâs, Extremal Graph Theory, Academic Press, London, 1978.

    MATH  Google Scholar 

19. A. Bruengger, J. Clausen, A. Marzetta, and M. Perregaard, Joining forces in solving large-scale quadratic assignment problems in parallel, in Proceedings of the 11-th IEEE International Parallel Processing Symposium (IPPS), 1997, 418–427.

    Google Scholar 

20. E. S. Buffa, G. C. Armour, and T. E. Vollmann, Allocating facilities with CRAFT, Harvard Business Review42, 1962, 136–158.

    Google Scholar 

21. R. E. Burkard, Die Störungsmethode zur Lösung quadratischer Zuordnungsprobleme, Operations Research Verfahren 16, 1973, 84–108.

    Google Scholar 

22. R. E. Burkard, Quadratische Bottleneckprobleme, Operations Research Verfahren18, 1974, 26–41.

    MathSciNet  Google Scholar 

23. R. E. Burkard, Locations with spatial interactions: the quadratic assignment problem, inDiscrete Location Theory, P. B. Mirchandani and R. L. Francis, eds., Wiley, 1991.

    Google Scholar 

24. R. E. Burkard and T. Bönniger, A heuristic for quadratic boolean programs with applications to quadratic assignment problems, European Journal of Operational Research13, 1983, 374–386.

    Article  MATH  Google Scholar 

25. R. E. Burkard and E. Çela, Heuristics for biquadratic assignment problems and their computational comparison, European Journal of Operational Research 83, 1995, 283–300.

    Article  MATH  Google Scholar 

26. R. E. Burkard, E. Çela, V. M. Demidenko, N. N. Metelski, and G. J. Woeginger, Perspectives of Easy and Hard Cases of the Quadratic Assignment Problems, SFB Report 104, Institute of Mathematics, Technical University Graz, Austria, 1997.

    Google Scholar 

27. R. E. Burkard, E. Çela, and B. Klinz, On the biquadratic assignment problem, in Quadratic Assignment and Related Problems, P. M. Pardalos and H. Wolkowicz, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science 16, 1994, 117–146, AMS, Providence, RI.

    Google Scholar 

28. R. E. Burkard, E. Çela, G. Rote, and G. J. Woeginger, The quadratic assignment problem with an Anti-Monge and a Toeplitz matrix: Easy and hard cases, SFB Report 34, Institute of Mathematics, Technical University Graz, Austria, 1995. To appear in Mathematical Programming.

    Google Scholar 

29. R. E. Burkard and U. Derigs, Assignment and matching problems: Solution methods with Fortran programs, Lecture Notes in Economics and Mathematical Systems184, Springer-Verlag, Berlin, 1980.

    Google Scholar 

30. R. E. Burkard and U. Fincke, On random quadratic bottleneck assignment problems, Mathematical Programming 23, 1982, 227–232.

    Article  MATH  MathSciNet  Google Scholar 

31. R. E. Burkard and U. Fincke, The asymptotic probabilistic behavior of the quadratic sum assignment problem, Zeitschrift für Operations Research27, 1983, 73–81.

    Article  MATH  MathSciNet  Google Scholar 

32. R. E. Burkard and U. Fincke, Probabilistic asymptotic properties of some combinatorial optimization problems, Discrete Applied Mathematics12, 1985, 21–29.

    Article  MATH  MathSciNet  Google Scholar 

33. R. E. Burkard, W. Hahn and U. Zimmermann, An algebraic approach to assignment problems, Mathematical Programming 12, 1977, 318–327.

    Article  MATH  MathSciNet  Google Scholar 

34. R. E. Burkard, S. E. Karisch, and F. Rendl, QAPLIB-a quadratic assignment prob- lem library, Journal of Global Optimization 10, 1997, 391–403. An on-line version is available via World Wide Web at the following URL: http://www.opt.math.tu-graz.ac.at/karisch/gaplib/

    Article  MathSciNet  Google Scholar 

35. R. E. Burkard, B. Klinz, and R. Rudolf, Perspectives of Monge properties in optimization, Discrete Applied Mathematics70, 1996, 95–161.

    Article  MATH  MathSciNet  Google Scholar 

36. R. E. Burkard and J. Offermann, Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme, Zeitschrift für Operations Research 21, 1977, B121–B132, (in German).

    Article  Google Scholar 

37. R. E. Burkard and F. Rendl, A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal Operational Research 17, 1984, 169–174.

    Article  MATH  Google Scholar 

38. R. E. Burkard and U. Zimmermann, Combinatorial optimization in linearly ordered semimodules: a survey, in Modern Applied Mathematics, B. Korte, ed., North Holland, Amsterdam, 1982, 392–436.

    Google Scholar 

39. P. Carraresi and F. Malucelli, A new lower bound for the quadratic assignment problem, Operations Research 40, 1992, Suppl. No. 1, S22–S27.

    Article  MathSciNet  Google Scholar 

40. P. Carraresi and F. Malucelli, A reformulation scheme and new lower bounds for the QAP, in Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 1994, 147–160, AMS, Providence, RI.

    Google Scholar 

41. E. Çela, The Quadratic Assignment Problem: Theory and Algorithms, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.

    Google Scholar 

42. V. Cerny, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications 45, 1985, 41–51.

    Article  MATH  MathSciNet  Google Scholar 

43. J. Chakrapani and J. Skorin-Kapov, Massively parallel tabu search for the quadratic assignment problem, Annals of Operations Research 41, 1993, 327–342.

    Article  MATH  Google Scholar 

44. J. Chakrapani and J. Skorin-Kapov, A constructive method to improve lower bounds for the quadratic assignment problem, in Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 1994, 161–171, AMS, Providence, RI.

    Google Scholar 

45. P. Chretienne, A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints, European Journal of Operational Research 43, 1989, 225–230.

    Article  MATH  MathSciNet  Google Scholar 

46. N. Christofides, Worst case analysis of a new heuristic for the traveling salesman problem, Technical Report 338, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.

    Google Scholar 

47. N. Christofides and E. Benavent, An exact algorithm for the quadratic assignment problem, Operations Research 37, 1989, 760–768.

    Article  MATH  MathSciNet  Google Scholar 

48. N. Christofides and M. Gerrard, A graph theoretic analysis of bounds for the quadratic assignment problem, in Studies on Graphs and Discrete Programming, P. Hansen, ed., North Holland, 1981, pp. 61–68.

    Chapter  Google Scholar 

49. J. Clausen, S. E. Karisch, M. Perregaard, and F. Rendl, On the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel, Computational Optimization and Applications 10, 1998, 127–147.

    Article  MATH  MathSciNet  Google Scholar 

50. J. Clausen and M. Perregaard, Solving large quadratic assignment problems in parallel, Computational Optimization and Applications 8, 1997, 111–127.

    Article  MATH  MathSciNet  Google Scholar 

51. A. Colorni, M. Dorigo, and V. Maniezzo, The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics -Part B 26, 1996, 29–41.

    Article  Google Scholar 

52. A. Colorni and V. Maniezzo, The ant system applied to the quadratic assignment problem, to appear in IEEE Transactions on Knowledge and Data Engineering, 1998.

    Google Scholar 

53. D. T. Connolly, An improved annealing scheme for the QAP, European Journal of Operational Research 46, 1990, 93–100.

    Article  MATH  MathSciNet  Google Scholar 

54. K. Conrad, Das Quadratische Zuweisungsproblem and zwei seiner Spezialfälle, Mohr-Siebeck, Tübingen, 1971.

    Google Scholar 

55. D. Cyganski, R. F. Vaz, and V. G. Virball, Quadratic assignment problems with the Palubeckis’ algorithm are degenerate, IEEE Transactions on Circuits and Systems-I 41, 1994, 481–484.

    Article  MathSciNet  Google Scholar 

56. L. Davis, Genetic Algorithms and Simulated Annealing, Pitman, London, 1987.

    MATH  Google Scholar 

57. V. G. Deineko and G. J. Woeginger, A solvable case of the quadratic assignment problem, SFB Report 88, Institute of Mathematics, Technical University Graz, Austria, 1996.

    Google Scholar 

58. J. W. Dickey and J. W. Hopkins, Campus building arrangement using TOPAZ, Transportation Research 6, 1972, 59–68.

    Article  Google Scholar 

59. M. Dorigo, Optimization, Learning, and Natural algorithms, Ph.D. Thesis, Dipartimento die Elettronica e Informazione, Politecnico di Milano, Milano, Italy, 1992, (in Italian).

    Google Scholar 

60. M. E. Dyer, A. M. Frieze, and C. J. H. McDiarmid, On linear programs with random costs, Mathematical Programming 35, 1986, 3–16.

    Article  MATH  MathSciNet  Google Scholar 

61. C. S. Edwards, The derivation of a greedy approximator for the Koopmans-Beckmann quadratic assignment problem, Proceedings of the 77-th Combinatorial Programming Conference (CP77), 1977, 55–86.

    Google Scholar 

62. C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Mathematical Programming Study 13, 1980, 35–52.

    MATH  Google Scholar 

63. A. N. Elshafei, Hospital layout as a quadratic assignment problem, Operations Research Quarterly 28, 1977, 167–179.

    Article  Google Scholar 

64. T. Espersen, S. E. Karisch, E. Cela, and J. Clausen, QAPPACK- a JAVA package for solving quadratic assignment problems, working paper, Department of Mathematical Modelling, Technical University of Denmark, Denmark, and Institute of Mathematics, Technical University Graz, Austria.

    Google Scholar 

65. T. A. Feo, M. G. C. Resende, and S. H. Smith, A greedy randomized adaptive search procedure for the maximum independent set, Technical report, AT&T Bell Laboratories, Murray Hill, NJ, 1989. To appear in Operations Research.

    Google Scholar 

66. T. A. Feo and M. G. C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization 6, 1995, 109–133.

    Article  MATH  MathSciNet  Google Scholar 

67. G. Finke, R. E. Burkard, and F. Rendl, Quadratic assignment problems, Annals of Discrete Mathematics 31, 1987, 61–82.

    MathSciNet  Google Scholar 

68. C. Fleurent and J. Ferland, Genetic hybrids for the quadratic assignment problem, in Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 1994, 173–187, AMS, Providence, RI.

    Google Scholar 

69. J. B. G. Frenk, M. van Houweninge, and A. H. G. Rinnooy Kan, Asymptotic properties of the quadratic assignment problem, Mathematics of Operations Research 10, 1985, 100–116.

    Article  MATH  MathSciNet  Google Scholar 

70. A. M. Frieze and J. Yadegar, On the quadratic assignment problem, Discrete Applied Mathematics 5, 1983, 89–98.

    Article  MATH  MathSciNet  Google Scholar 

71. A. M. Frieze, J. Yadegar, S. El-Horbaty, and D. Parkinson, Algorithms for assignment problems on an array processor, Parallel Computing 11, 1989, 151–162.

    Article  MATH  MathSciNet  Google Scholar 

72. L. M. Gambardella, E. D. Taillard, and M. Dorigo, Ant colonies for the QAP, Technical Report IDSIA-4–97, 1997, Istituto dalle Molle Di Studi sull’ Intelligenza Artificiale, Lugano, Switzerland.

    Google Scholar 

73. M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman and Company, New York, 1979.

    MATH  Google Scholar 

74. J. W. Gavett and N. V. Plyter, The optimal assignment of facilities to locations by branch and bound, Operations Research 14, 1966, 210–232.

    Article  Google Scholar 

75. A. M. Geoffrion, Lagrangean relaxation and its uses in integer programming, Mathematical Programming Study 2, 1974, 82–114.

    MathSciNet  Google Scholar 

76. A. M. Geoffrion and G. W. Graves, Scheduling parallel production lines with changeover costs: Practical applications of a quadratic assignment/LP approach. Operations Research 24, 1976, 595–610.

    Article  MATH  Google Scholar 

77. P. C. Gilmore, Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics 10, 1962, 305–313.

    Article  MATH  MathSciNet  Google Scholar 

78. F. Glover, Improved linear integer programming formulations of nonlinear integer problems, Management Science 22, 1975, 455–460.

    Article  MathSciNet  Google Scholar 

79. F. Glover, Tabu search-Part I, ORSA Journal on Computing 1, 1989, 190–206.

    MATH  MathSciNet  Google Scholar 

80. F. Glover, Tabu search-Part II, ORSA Journal on Computing 2, 1989, 4–32.

    MathSciNet  Google Scholar 

81. F. Glover, M. Laguna, E. Taillard, and D. de Werra, eds., Tabu search, Annals of Operations Research 41, 1993.

    Google Scholar 

82. M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42, 1995, 1115–1145.

    Article  MATH  MathSciNet  Google Scholar 

83. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Wokingham, England, 1989.

    MATH  Google Scholar 

84. A. Graham, Kronecker Products and Matrix Calculus with Applications, Halsted Press, Toronto, 1981.

    MATH  Google Scholar 

85. H. Greenberg, A quadratic assignment problem without column constraints, Naval Research Logistic Quarterly 16, 1969, 417–422.

    MATH  Google Scholar 

86. S. W. Hadley, Continuous Optimization Approaches for the Quadratic Assignment Problem, PhD thesis, University of Waterloo, Ontario, Canada, 1989.

    Google Scholar 

87. S. W. Hadley, F. Rendl, and H. Wolkowicz, Bounds for the quadratic assignment problem using continuous optimization techniques, Proceedings of the 1-st Integer Programming and Combinatorial Optimization Conference (IPCO), University of Waterloo Press, 1990, 237–248.

    Google Scholar 

88. S. W. Hadley, F. Rendl, and H. Wolkowicz, A new lower bound via projection for the quadratic assignment problem, Mathematics of Operations Research 17, 1992, 727–739.

    Article  MATH  MathSciNet  Google Scholar 

89. S. W. Hadley, F. Rendl, and H. Wolkowicz, Nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality, Linear Algebra and its Applications 58, 1992, 109–124.

    MathSciNet  Google Scholar 

90. P. Hahn and T. Grant, Lower bounds for the quadratic assignment problem based upon a dual formulation, to appear in Operations Research.

    Google Scholar 

91. P. Hahn, T. Grant, and N. Hall, Solution of the quadratic assignment problem using the Hungarian method, to appear in European Journal of Operational Research.

    Google Scholar 

92. G. G. Hardy, J. E. Littlewood, and G. Pblya, Inequalities, Cambridge University Press, London and New York, 1952.

    MATH  Google Scholar 

93. D. R. Hefiiey, Assigning runners to a relay team, in Optimal Strategies in Sports, S. P. Ladany and R. E. Machol, eds., North-Holland, Amsterdam, 1977, 169–171.

    Google Scholar 

94. C. H. Heider, A computationally simplified pair exchange algorithm for the quadratic assignment problem, Paper No. 101, Center for Naval Analysis, Arlington, Virginia, 1972.

    Google Scholar 

95. J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

    Google Scholar 

96. B. Jansen. A note on lower bounds for the QAP, Technical report, Mathematics and Computer Science, Delft University of Technology, The Netherlands, December 1993.

    Google Scholar 

97. D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, How easy is local search, Journal of Computer and System Sciences 37, 1988, 79–100.

    Article  MATH  MathSciNet  Google Scholar 

98. T. A. Johnson, New linear programming-based solution procedures for the quadratic assignment problem, Ph.D. Thesis, Clemson University, SC, 1992.

    Google Scholar 

99. M. Jünger, Polyhedral Combinatorics and the Acyclic Subdigraph Problem, Heldermann Verlag, Berlin, Germany, 1985.

    Google Scholar 

100. M. Jünger and V. Kaibel, A basic study of the QAP polytope, Technical Report 96. 215, Institut für Informatik, Universität zu Köln, Germany, 1996.

     Google Scholar 

101. M. Jünger and V. Kaibel, On the SQAP polytope, Technical Report 96. 241, Institut für Informatik, Universität zu Köln, Germany, 1996.

     Google Scholar 

102. V. Kaibel, Polyhedral Combinatorics of the Quadratic Assignment Problem, Ph.D. Thesis, Universität zu Köln, Germany, 1997.

     Google Scholar 

103. S. E. Karisch, Nonlinear Approaches for Quadratic Assignment and Graph Partition Problems, Ph.D. Thesis, Technical University Graz, Austria, 1995.

     Google Scholar 

104. S. E. Karisch, E. Çela, J. Clausen, and T. Espersen, A dual framework for lower bounds of the quadratic assignment problem based on linearization, SFB Report 120, Institute of Mathematics, Technical University Graz, Austria, 1997.

     Google Scholar 

105. S. E. Karisch and F. Rendl, Lower bounds for the quadratic assignment problem via triangle decompositions, Mathematical Programming 71, 1995, 137–151.

     MATH  MathSciNet  Google Scholar 

106. S. E. Karisch, F. Rendl, and H. Wolkowicz, Trust regions and relaxations for the quadratic assignment problem, in Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 1994, 199–220, AMS, Providence, RI.

     Google Scholar 

107. R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum, New York, 1972, 85–103.

     Google Scholar 

108. L. Kaufmann and Fe Broeckx, An algorithm for the quadratic assignment problem using Benders’ decomposition, European Journal of Operational Research 2, 1978, 204–211.

     Article  Google Scholar 

109. B. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Systems Journal 49, 1972, 291–307.

     Google Scholar 

110. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science 220, 1983, 671–680.

     Article  MATH  MathSciNet  Google Scholar 

111. J. G. Klincewicz, Avoiding local optima in the p-hub location problem using tabu search and GRASP, Annals of Operations 40, 1992, 283–302.

     Article  MATH  MathSciNet  Google Scholar 

112. J. G. Klincewicz and A. Rajan, Using GRASP to solve the component grouping problem, Technical report, AT&T Bell Laboratories, Holmdel, NJ, 1992.

     Google Scholar 

113. T. C. Koopmans and M. J. Beckmann, Assignment problems and the location of economic activities, Econometrica 25, 1957, 53–76.

     Article  MATH  MathSciNet  Google Scholar 

114. J. Krarup and P. M. Pruzan, Computer-aided layout design, Mathematical Programming Study 9, 1978, 75–94.

     MathSciNet  Google Scholar 

115. P. J. M. van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications, D. Reidel Publishing Company, Dordrecht, 1988.

     Google Scholar 

116. A. M. Land, A problem of assignment with interrelated costs, Operations Research Quarterly 14, 1963, 185–198.

     Article  Google Scholar 

117. G. Laporte and H. Mercure, Balancing hydraulic turbine runners: A quadratic assignment problem, European Journal of Operational Research 35, 1988, 378–382.

     Article  Google Scholar 

118. E. L. Lawler, The quadratic assignment problem, Management Science 9, 1963, 586–599.

     Article  MATH  MathSciNet  Google Scholar 

119. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., The Traveling Salesman Problem, Wiley, Chichester, 1985.

     MATH  Google Scholar 

120. T. Lengauer, Combinatorial Algorithms for Intergrated Circuit Layout, Wiley, Chichester, 1990.

     Google Scholar 

121. W. Leontief, Input-Output Economics, Oxford University Press, New York, 1966.

     Google Scholar 

122. Y. Li and P. M. Pardalos, Generating quadratic assignment test problems with known optimal permutations, Computational Optimization and Applications 1, 1992, 163–184.

     Article  MATH  MathSciNet  Google Scholar 

123. Y. Li, P. M. Pardalos, K. G. Ramakrishnan, and M. G. C. Resende, Lower bounds for the quadratic assignment problem, Annals of Operations Research 50, 1994, 387–410.

     Article  MATH  MathSciNet  Google Scholar 

124. Y. Li, P. M. Pardalos, and M. G. C. Resende, A greedy randomized adaptive search procedure for the quadratic assignment problem, in Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16 1994, 237–261, AMS, Providence, RI.

     Google Scholar 

125. L. Lovâsz and A. Schrijver, Cones of matrices and set functions and 0–1 optimization, SIAM Journal on Optimization 1, 1991, 166–190.

     Article  MATH  MathSciNet  Google Scholar 

126. E. J. McCormick, Human Factors Engineering, McGraw-Hill, New York, 1970.

     Google Scholar 

127. T. Magnanti, R. Ahuja, and J. Orlin. Network flows: theory, algorithms, and applications, Prentice Hall, Englewood-Cliffs, New Jersey, 1993.

     Google Scholar 

128. F. Malucelli, Quadratic Assignment Problems: Solution Methods and Applications, Ph.D. Thesis, Dipartimento di Informatica, Universitâ di Pisa, Italy, 1993.

     Google Scholar 

129. F. Malucelli and D. Pretolani, Lower bounds for the quadratic semi-assignment problem, Technical Report 955, Centre des Recherches sur les Transports, Université de Montréal, Canada, 1993.

     Google Scholar 

130. A. Marzetta, Dynamic programming for the quadratic assignment problem, presented at the 2-nd Aussois Workshop on Combinatorial Optimization, 1998, Aussois, France.

     Google Scholar 

131. T. Mautor and C. Roucairol, A new exact algorithm for the solution of quadratic assignment problems, Discrete Applied Mathematics 55, 1992, 281–293.

     Article  MathSciNet  Google Scholar 

132. T. Mavridou, P. M. Pardalos, L. S. Pitsoulis, and M. G. C. Resende, A GRASP for the biquadratic assignment problem, European Journal of Operations Research 105, 1998, 613–621.

     Article  MATH  Google Scholar 

133. N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, Equations of state calculations by fast computing machines, Journal of Chemical Physics 21, 1953, 1087–1092.

     Article  Google Scholar 

134. I. Z. Milis and V. F. Magirou, A Lagrangean relaxation algorithm for sparse quadratic assignment problems, Operations ResearchLetters 17, 1995, 69–76.

     MATH  MathSciNet  Google Scholar 

135. P. B. Mirchandani and T. Obata, Locational decisions with interactions between facilities: the quadratic assignment problem a review, Working Paper Ps-79–1, Rensselaer Polytechnic Institute, Troy, New York, May 1979.

     Google Scholar 

136. L. Mirsky, The spread of a matrix, Mathematika 3, 1956, 127–130.

     Article  MATH  MathSciNet  Google Scholar 

137. J. Mosevich, Balancing hydraulic turbine runners — a discrete combinatorial optimization problem, European Journal of Operational Research 26, 1986, 202–204.

     Article  MATH  Google Scholar 

138. K. A. Murthy, P. Pardalos, and Y. Li, A local search algorithm for the quadratic assignment problem, Informatica 3, 1992, 524–538.

     MATH  MathSciNet  Google Scholar 

139. K. G. Murty, An algorithm for ranking all the assignments in order of increasing cost, Operations Research 16, 1968, 682–287.

     Article  MATH  Google Scholar 

140. H. Müller-Merbach, Optimale Reihenfolgen, Springer-Verlag, Berlin, Heidelberg, New York, 1970, pp. 158–171.

     Google Scholar 

141. C. E. Nugent, T. E. Vollmann, and J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Journal of Operations Research 16, 1969, 150–173.

     Article  Google Scholar 

142. M. W. Padberg and M. P. Rijal, Location, Scheduling, Design and Integer Programming, Kluwer Academic Publishers, Boston, 1996.

     Book  MATH  Google Scholar 

143. M. W. Padberg and G. Rinaldi, Optimization of a 532-city symmetric traveling salesman problem by a branch and cut algorithm, Operations Research Letters 6, 1987, 1–7.

     Article  MATH  MathSciNet  Google Scholar 

144. G. S. Palubeckis, Generation of quadratic assignment test problems with known optimal solutions, U.S.S.R. Comput. Maths. Math. Phys. 28, 1988, 97–98, (in Russian).

     Article  MathSciNet  Google Scholar 

145. C. H. Papadimitriou and D. Wolfe, The complexity of facets resolved, Proceedings of the 25-th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 1985, 74–78.

     Google Scholar 

146. P. Pardalos and J. Crouse, A parallel algorithm for the quadratic assignment problem, Proceedings of the Supercomputing Conference 1989, ACM Press, 1989, 351–360.

     Google Scholar 

147. P. Pardalos, F. Rendl, and H. Wolkowicz, The quadratic assignment problem: A survey and recent developments, in Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 1994, 1–42, AMS, Providence, RI.

     Google Scholar 

148. P. M. Pardalos, L. S. Pitsoulis, and M. G. C. Resende, A parallel GRASP implementation for solving the quadratic assignment problem, in Parallel Algorithms for Irregular Problems: State of the Art, A. Ferreira and José D.P. Rolim, eds., Kluwer Academic Publishers, 1995, 115–133.

     Google Scholar 

149. P. M. Pardalos, L. S. Pitsoulis, and M. G. C. Resende, Fortran subroutines for approximate solution of sparse quadratic assignment problems using GRASP, ACM Transcations on Mathematical Software 23, 1997, 196–208.

     Article  MATH  MathSciNet  Google Scholar 

150. P. M. Pardalos, K. G. Ramakrishnan, M. G. C. Resende, and Y. Li, Implementation of a variable reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem, SIAM Journal on Optimization7, 1997, 280–294.

     Article  MATH  MathSciNet  Google Scholar 

151. P. M. Pardalos and J. Xue, The maximum clique problem, Research Report 93–1, Department of Industrial and System Engineering, University of Florida, Fl, 1993.

     Google Scholar 

152. M. Queyranne, Performance ratio of heuristics for triangle inequality quadratic assignment problems, Operations Research Letters 4, 1986, 231–234.

     Article  MATH  MathSciNet  Google Scholar 

153. G. Reinelt, The Linear Ordering Problem: Algorithms and Applications, Heldermann Verlag, Berlin, Germany, 1985.

     Google Scholar 

154. F. Rendl, Ranking scalar products to improve bounds for the quadratic assignment problem, European Journal of Operations Research 20, 1985, 363–372.

     Article  MATH  MathSciNet  Google Scholar 

155. F. Rendl and H. Wolkowicz, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Mathematical Programming 53, 1992, 63–78.

     Article  MATH  MathSciNet  Google Scholar 

156. M. G. C. Resende, P. M. Pardalos, and Y. Li, Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP, ACM Transcations on Mathematical Software 22, 1996, 104–118.

     Article  MATH  Google Scholar 

157. M. G. C. Resende, L. S. Pitsoulis, and P. M. Pardalos, Approximate solution of weighted max-sat problems using GRASP, in The Satisfiability Problem, P. M. Pardalos, M. G. C. Resende and D. Z. Du, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35, 1997, 393–405, AMS, Providence, RI.

     Google Scholar 

158. M. G. C. Resende, K. G. Ramakrishnan, and Z. Drezner, Computing lower bounds for the quadratic assignment problem with an inte-rior point algorithm for linear programming, Operations Research 43, 1995, 781–791.

     MATH  MathSciNet  Google Scholar 

159. W. T. Rhee, A note on asymptotic properties of the quadratic assignment problem, Operations Research Letters 7, 1988, 197–200.

     Article  MATH  MathSciNet  Google Scholar 

160. W. T. Rhee, Stochastic analysis of the quadratic assignment problem, Mathematics of Operations Research 16, 1991, 223–239.

     Article  MATH  MathSciNet  Google Scholar 

161. M. P. Rijal, Scheduling, Design and Assignment Problems with Quadratic Costs, Ph.D. Thesis, New York University, NY, 1995.

     Google Scholar 

162. C. Roucairol, A reduction method for quadratic assignment problems, Operations Research Verfahren 32, 1979, 183–187.

     MATH  Google Scholar 

163. C. Roucairol, A parallel branch and bound algorithm for the quadratic assignment problem, Discrete Applied Mathematics 18, 1987, 221–225.

     Article  MathSciNet  Google Scholar 

164. S. Sahni and T. Gonzalez, P-complete approximation problems, Journal of the Association of Computing Machinery 23, 1976, 555–565.

     Article  MATH  MathSciNet  Google Scholar 

165. A. Schäffer and M. Yannakakis, Simple local search problems that are hard to solve, SIAM Journal on Computing 20, 1991, 56–87.

     Article  MATH  MathSciNet  Google Scholar 

166. J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem, ORSA Journal on Computing 2, 1990, 33–45.

     MATH  Google Scholar 

167. J. Skorin-Kapov, Extensions of tabu search adaptation to the quadratic assignment problem, to appear in Computers and Operations Research.

     Google Scholar 

168. L. Steinberg, The backboard wiring problem: A placement algorithm, SIAM Review 3, 1961, 37–50.

     Article  MATH  MathSciNet  Google Scholar 

169. H. S. Stone, Multiprocessor scheduling with the aid of network flow algorithms, IEEE Transactions on Software Engineering 3, 1977, 8593.

     Article  Google Scholar 

170. W. Szpankowski, Combinatorial optimization problems for which almost every algorithm is asymptotically optimall, Optimization 33, 1995, 359–367.

     Article  MATH  MathSciNet  Google Scholar 

171. E. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Computing 17, 1991, 443–455.

     Article  MathSciNet  Google Scholar 

172. D. M. Tate and A. E. Smith, A genetic approach to the quadratic assignment problem, Computers and Operations Research 22, 1995, 73–83.

     Article  MATH  Google Scholar 

173. I. Ugi, J. Bauer, J. Friedrich, J. Gasteiger, C. Jochum, and W. Schubert, Neue Anwendungsgebiete für Computer in der Chemie, Angewandte Chemie 91, 1979, 99–111.

     Article  Google Scholar 

174. D. H. West, Algorithm 608: Approximate solution of the quadratic assignment problem, ACM Transactions on Mathematical Software 9, 1983, 461–466.

     Article  Google Scholar 

175. M. R. Wilhelm and T. L. Ward, Solving quadratic assignment problems by simulated annealing, IEEE Transactions 19, 1987, 107–119.

     Article  Google Scholar 

176. Q. Zhao, Semidefinite Programming for Assignment and Partitioning Problems, Ph.D. Thesis, University of Waterloo, Ontario, Canada, 1996.

     Google Scholar 

177. Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz, Semidefinite relaxations for the quadratic assignment problem, Technical Report DIKU TR-96–32, Department of Computer Science, University of Copenhagen, Denmark, 1996. To appear in Journal of Combinatorial Optimization.

     Google Scholar 

Download references