A survey for the quadratic assignment problem. (English) Zbl 1103.90058
Summary: The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and distributed computing, and combinatorial data analysis. Combinatorial optimization problems, such as the traveling salesman problem, maximal clique and graph partitioning can be formulated as a QAP. In this paper, we present some of the most important QAP formulations and classify them according to their mathematical sources. We also present a discussion on the theoretical resources used to define lower bounds for exact and heuristic algorithms. We then give a detailed discussion of the progress made in both exact and heuristic solution methods, including those formulated according to metaheuristic strategies. Finally, we analyze the contributions brought about by the study of different approaches.
MSC:
| 90B80 | Discrete location and assignment |
| 90C10 | Integer programming |
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
assignment; integer programming; combinatorial optimization; facilities planning and design; metaheuristics; branch and boundReferences:
| [1] | Abbiw-Jackson, R., Golden, B., Raghavan, S., Wasil, E., in press. A divide-and-conquer local search heuristic for data visualization. Computers and Operations Research.; Abbiw-Jackson, R., Golden, B., Raghavan, S., Wasil, E., in press. A divide-and-conquer local search heuristic for data visualization. Computers and Operations Research. · Zbl 1113.90127 |
| [2] | Abreu, N. M.M.; Querido, T. M.; Boaventura-Netto, P. O., RedInv-SA: A simulated annealing for the quadratic assignment problem, RAIRO Operations Research, 33, 3, 249-273 (1999) · Zbl 1016.90037 |
| [3] | Abreu, N. M.M.; Boaventura-Netto, P. O.; Querido, T. M.; Gouvêa, E. F., Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach, Discrete Applied Mathematics, 124, 1-3, 103-116 (2002) · Zbl 1005.90042 |
| [4] | Acan, A., An external partial permutations memory for ant colony optimization, Lecture Notes in Computer Science, 3448, 1-11 (2005) · Zbl 1119.68430 |
| [5] | Adams, W. P.; Sherali, H. D., A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32, 10, 1274-1290 (1986) · Zbl 0623.90054 |
| [6] | Adams, W. P.; Sherali, H. D., Linearization strategies for a class of zero-one mixed integer programming problems, Operations Research, 38, 2, 217-226 (1990) · Zbl 0724.90046 |
| [7] | Adams, W. P.; Johnson, T. A., Improved linear programming-based lower bounds for the quadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 43-75 · Zbl 0819.90049 |
| [8] | Adams, W.P., Guignard, M., Hahn, P.M., Hightower, W.L., to appear. A level-2 reformulation-linearization technique bound for the quadratic assignment problem. To appear in the European Journal of Operational Research. First available as Working Paper 01-04, Systems Engineering Department, University of Pennsylvania, 2001 (Authors: P.M. Hahn, W.L. Hightower, T.A. Johnson, M. Guignard, and C. Roucairol).; Adams, W.P., Guignard, M., Hahn, P.M., Hightower, W.L., to appear. A level-2 reformulation-linearization technique bound for the quadratic assignment problem. To appear in the European Journal of Operational Research. First available as Working Paper 01-04, Systems Engineering Department, University of Pennsylvania, 2001 (Authors: P.M. Hahn, W.L. Hightower, T.A. Johnson, M. Guignard, and C. Roucairol). · Zbl 1121.90082 |
| [9] | Ahuja, R.; Orlin, J. B.; Tiwari, A., A greedy genetic algorithm for the quadratic assignment problem, Computers and Operations Research, 27, 10, 917-934 (2000) · Zbl 0970.90067 |
| [10] | Anderson, E. J., Theory and methodology: Mechanisms for local search, European Journal of Operational Research, 88, 139-151 (1996) · Zbl 0913.90227 |
| [11] | Angel, E.; Zissimopoulos, V., On the quality of local search for the quadratic assignment problem, Discrete Applied Mathematics, 82, 1-3, 15-25 (1998) · Zbl 0896.90157 |
| [12] | Angel, E.; Zissimopoulos, V., On the classification of NP-complete problems in terms of their correlation coefficient, DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 99, 1-3, 261-277 (2000) · Zbl 0987.90092 |
| [13] | Angel, E.; Zissimopoulos, V., On the landscape ruggedness of the quadratic assignment problem, Theoretical Computer Science, 263, 1-2, 159-172 (2001) · Zbl 0973.68085 |
| [14] | Angel, E.; Zissimopoulos, V., On the hardness of the quadratic assignment problem with metaheuristics, Journal of Heuristics, 8, 4, 399-414 (2002) |
| [15] | Anstreicher, K. M.; Chen, X.; Wolkowicz, H.; Yuan, Y., Strong duality for a trust-region type relaxation of the quadratic assignment problem, Linear Algebra and its Applications, 301, 1-3, 121-136 (1999) · Zbl 0953.90034 |
| [16] | Anstreicher, K. M., Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem, SIAM Journal on Optimization, 11, 1, 254-265 (2001) · Zbl 0990.90099 |
| [17] | Anstreicher, K. M.; Brixius, N. W., A new bound for the quadratic assignment problem based on convex quadratic programming, Mathematical Programming, 89, 3, 341-357 (2001) · Zbl 0986.90042 |
| [18] | Anstreicher, K. M.; Brixius, N. W.; Goux, J. P.; Linderoth, J., Solving large quadratic assignment problems on computational grids, Mathematical Programming, 91, 3, 563-588 (2002) · Zbl 1030.90105 |
| [19] | Anstreicher, K. M., Recent advances in the solution of quadratic assignment problems, Mathematical Programming, 97, 1-2, 27-42 (2003) · Zbl 1035.90067 |
| [20] | Arkin, E. M.; Hassin, R.; Sviridenko, M., Approximating the maximum quadratic assignment problem, Information Processing Letters, 77, 1, 13-16 (2001) · Zbl 0996.90500 |
| [21] | Armour, G. C.; Buffa, E. S., Heuristic algorithm and simulation approach to relative location of facilities, Management Science, 9, 2, 294-309 (1963) |
| [22] | Arora, S.; Frieze, A.; Kaplan, H., A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Mathematical Programming, 92, 1, 1-36 (2002) · Zbl 1154.90602 |
| [23] | Assad, A. A.; Xu, W., On lower bounds for a class of quadratic {0,1} programs, Operations Research Letters, 4, 4, 175-180 (1985) · Zbl 0587.90069 |
| [24] | Balakrishnan, J.; Cheng, C. H.; Conway, D. G.; Lau, C. M., A hybrid genetic algorithm for the dynamic plant layout problem, International Journal of Production Economics, 86, 2, 107-120 (2003) |
| [25] | Balakrishnan, J.; Jacobs, F. R.; Venkataramanan, M. A., Solutions for the constrained dynamic facility layout problem, European Journal of Operational Research, 15, 280-286 (1992) · Zbl 0825.90460 |
| [26] | Balas, E.; Saltzman, M. J., Facets of the three-index assignment polytope, Discrete Applied Mathematics, 23, 201-229 (1989) · Zbl 0723.90065 |
| [27] | Balas, E.; Saltzman, M. J., An algorithm for the three-index assignment problem, Operations Research, 39, 1, 150-161 (1991) · Zbl 0743.90079 |
| [28] | Balas, E.; Qi, L., Linear-time separation algorithms for the three-index assignment polytope, Discrete Applied Mathematics, 43, 1-12 (1993) · Zbl 0781.90069 |
| [29] | Ball, M. O.; Kaku, B. K.; Vakhutinsky, A., Network-based formulations of the quadratic assignment problem, European Journal of Operational Research, 104, 1, 241-249 (1998) · Zbl 0955.90057 |
| [30] | Bandelt, H.-J.; Crama, Y.; Spieksma, F. C.R., Approximation algorithms for multi-dimensional assignment problems with decomposable costs, Discrete Applied Mathematics, 49, 25-50 (1991) · Zbl 0799.90077 |
| [31] | Bartolomei-Suarez, S. M.; Egbelu, P. J., Quadratic assignment problem QAP with adaptable material handling devices, International Journal of Production Research, 38, 4, 855-873 (2000) · Zbl 0944.90522 |
| [32] | Barvinok, A.; Stephen, T., The distribution of values in the quadratic assignment problem, Mathematics of Operations Research, 28, 64-91 (2003) · Zbl 1082.90081 |
| [33] | Battiti, R.; Tecchiolli, G., Simulated annealing and tabu search in the long run: A comparison on QAP tasks, Computer and Mathematics with Applications, 28, 6, 1-8 (1994) · Zbl 0812.68067 |
| [34] | Baykasoglu, A., A meta-heuristic algorithm to solve quadratic assignment formulations of cell formation problems without presetting number of cells, Journal of Intelligent Manufacturing, 15, 6, 753-759 (2004) |
| [35] | Bazaraa, M. S.; Elshafei, A. N., An exact branch-and-bound procedure for the quadratic assignment problem, Naval Research Logistics Quarterly, 26, 109-121 (1979) · Zbl 0405.90051 |
| [36] | Bazaraa, M. S.; Sherali, H. D., New approaches for solving the quadratic assignment problem, Operations Research Verfahren, 32, 29-46 (1979) · Zbl 0408.90063 |
| [37] | Bazaraa, M. S.; Sherali, H. D., Benders’ partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Research Logistics Quarterly, 27, 29-41 (1980) · Zbl 0432.90060 |
| [38] | Bazaraa, M. S.; Sherali, H. D., On the use of exact and heuristic cutting plane methods for the quadratic assignment problem, Journal of the Operational Research Society, 33, 991-1003 (1982) · Zbl 0497.90042 |
| [39] | Bazaraa, M. S.; Kirca, O., A branch-and-bound based heuristic for solving the quadratic assignment problem, Naval Research Logistics Quarterly, 30, 287-304 (1983) · Zbl 0575.90041 |
| [40] | Ben-David, G.; Malah, D., Bounds on the performance of vector-quantizers under channel errors, IEEE Transactions on Information Theory, 51, 6, 2227-2235 (2005) · Zbl 1285.94030 |
| [41] | Benjaafar, S., Modeling and analysis of congestion in the design of facility layouts, Management Science, 48, 5, 679-704 (2002) · Zbl 1232.90138 |
| [42] | Billionnet, A.; Elloumi, S., Best reduction of the quadratic semi-assignment problem, Discrete Applied Mathematics, 109, 3, 197-213 (2001) · Zbl 0987.90065 |
| [43] | Blanchard, A.; Elloumi, S.; Faye, A.; Wicker, N., A cutting algorithm for the quadratic assignment problem, INFOR, 41, 1, 35-49 (2003) · Zbl 07682293 |
| [44] | Bland, J. A.; Dawson, G. P., Tabu search and design optimization, Computer Aided Design, 23, 3, 195-201 (1991) · Zbl 0735.65036 |
| [45] | Bland, J. A.; Dawson, G. P., Large-scale layout of facilities using a heuristic hybrid algorithm, Applied Mathematical Modeling, 18, 9, 500-503 (1994) · Zbl 0811.90055 |
| [46] | Boaventura-Netto, P. O., Combinatorial instruments in the design of a heuristic for the quadratic assignment problems, Pesquisa Operacional, 23, 3, 383-402 (2003) |
| [47] | Bölte, A.; Thonemann, U. W., Optimizing simulated annealing schedules with genetic programming, European Journal of Operational Research, 92, 2, 402-416 (1996) · Zbl 0912.90235 |
| [48] | Bos, J., A quadratic assignment problem solved by simulated annealing, Journal of Environmental Management, 37, 2, 127-145 (1993) |
| [49] | Bousonocalzon, C.; Manning, M. R.W., The Hopfield neural-network applied to the quadratic assignment problem, Neural Computing and Applications, 3, 2, 64-72 (1995) |
| [50] | Bozer, Y. A.; Suk-Chul, R., A branch and bound method for solving the bidirectional circular layout problem, Applied Mathematical Modeling, 20, 5, 342-351 (1996) · Zbl 0865.90106 |
| [51] | Brixius, N. W.; Anstreicher, K. M., Solving quadratic assignment problems using convex quadratic programming relaxations, Optimization Methods and Software, 16, 49-68 (2001) · Zbl 0991.90107 |
| [52] | Brown, D. E.; Huntley, C. L., A parallel heuristic for the quadratic assignment problem, Computers and Operations Research, 18, 275-289 (1991) · Zbl 0723.90044 |
| [53] | Bruijs, P. A., On the quality of heuristic solutions to a 19×19 quadratic assignment problem, European Journal of Operational Research, 17, 21-30 (1984) · Zbl 0538.90069 |
| [54] | Brüngger, A.; Marzetta, A.; Clausen, J.; Perregaard, M., Joining forces in solving large-scale quadratic assignment problems, (Proceedings of the 11th International Parallel Processing Symposium IPPS (1997), IEEE Computer Society Press), 418-427 |
| [55] | Brüngger, A.; Marzetta, A.; Clausen, J.; Perregaard, M., Solving large-scale QAP problems in parallel with the search library ZRAM, Journal of Parallel and Distributed Computing, 50, 1-2, 157-169 (1998) · Zbl 0909.68171 |
| [56] | Brusco, M. J.; Stahl, S., Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices, Journal of Classification, 17, 2, 197-223 (2000) · Zbl 1137.91602 |
| [57] | Buffa, E. S.; Armour, G. C.; Vollmann, T. E., Allocating facilities with CRAFT, Harvard Business Review, 42, 2, 136-158 (1964) |
| [58] | Bui, T. N.; Moon, B. R., A genetic algorithm for a special class of the quadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 99-116 · Zbl 0817.90053 |
| [59] | Bullnheimer, B., An examination-scheduling model to maximize students’ study time, Lecture Notes in Computer Science, 1408, 78-91 (1998) |
| [60] | Burer, S.; Vandenbussche, D., Solving lift-and-project relaxations of binary integer programs, SIAM Journal on Optimization, 16, 726-750 (2006), First available in 2004 on · Zbl 1113.90100 |
| [61] | Burkard, R. E., Numerische Erfahungen mit Summen und Bottleneck Zuordnungsproblemen, (Collatz, L.; Werner, H., Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen (1975), Birkhauser Verlag: Birkhauser Verlag Basel) · Zbl 0311.65045 |
| [62] | Burkard, R. E.; Stratman, R. H., Numerical investigations on quadratic assignment problem, Naval Research Logistics Quarterly, 25, 129-140 (1978) · Zbl 0391.90066 |
| [63] | Burkard, R. E.; Derigs, U., Assignment and matching problems: Solutions methods with Fortran programs, (Lectures Notes in Economics and Mathematical Systems, vol. 184 (1980), Springer-Verlag: Springer-Verlag New York, Secaucus, NJ) · Zbl 0436.90069 |
| [64] | Burkard, R. E.; Fröhlich, K., Some remarks on 3-dimensional assignment problems, Methods of Operations Research, 36, 31-36 (1980) · Zbl 0438.90058 |
| [65] | Burkard, R. E.; Finke, G., On random quadratic bottleneck assignment problems, Mathematical Programming, 23, 227-232 (1982) · Zbl 0479.90063 |
| [66] | Burkard, R. E.; Zimmermann, U., Combinatorial optimization in linearly ordered semimodules: A survey, (Korte, B., Modern Applied Mathematics: Optimization and Operations Research (1982), North Holland: North Holland Amsterdam), 392-436 · Zbl 0483.90086 |
| [67] | Burkard, R. E.; Bonniger, T., A heuristic for quadratic Boolean programs with applications to quadratic assignment problems, European Journal of Operation Research, 13, 374-386 (1983) · Zbl 0509.90058 |
| [68] | Burkard, R. E., Quadratic assignment problems, European Journal of Operational Research, 15, 283-289 (1984) · Zbl 0526.90064 |
| [69] | Burkard, R. E.; Rendl, F., A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research, 17, 2, 169-174 (1984) · Zbl 0541.90070 |
| [70] | Burkard, R. E.; Euler, R.; Grommes, R., On Latin squares and the facial structure of related polytopes, Discrete Mathematics, 62, 155-181 (1986) · Zbl 0614.05015 |
| [71] | Burkard, R. E., Locations with spatial interactions: The quadratic assignment problem, (Mirchandani, P. B.; Francis, R. L., Discrete Location Theory (1991), John Wiley and Sons), 387-437 · Zbl 0726.90041 |
| [72] | Burkard, R. E.; Karisch, S.; Rendl, F., QAPLIB—A quadratic assignment problem library, European Journal of Operational Research, 55, 115-119 (1991) · Zbl 0729.90993 |
| [73] | Burkard, R. E.; Rudolf, R., Computational investigations on 3-dimensional axial assignment problems, Belgian Journal of Operations Research, Statistics and Computer Science, 32, 85-98 (1993) · Zbl 0783.90082 |
| [74] | Burkard, R. E.; Çela, E.; Klinz, B., On the biquadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 117-146 · Zbl 0819.90050 |
| [75] | Burkard, R. E.; Çela, E., Heuristics for biquadratic assignment problems and their computational comparison, European Journal of Operational Research, 83, 2, 283-300 (1995) · Zbl 0904.90138 |
| [76] | Burkard, R. E.; Çela, E., Quadratic and three-dimensional assignment problems: An annotated bibliography, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1996), Wiley: Wiley Chichester), 373-392 |
| [77] | Burkard, R. E.; Çela, E.; Rote, G.; Woeginger, G. J., The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases, Lecture Notes in Computer Science, 1084, 204-218 (1996) · Zbl 1414.90192 |
| [78] | Burkard, R. E.; Rudolf, R.; Woeginger, G. J., Three-dimensional axial assignment problems with decomposable cost coefficients, Discrete Applied Mathematics, 65, 123-139 (1996) · Zbl 0846.90090 |
| [79] | Burkard, R. E.; Karisch, S.; Rendl, F., QAPLIB—A quadratic assignment problem library, Journal of Global Optimization, 10, 391-403 (1997) · Zbl 0884.90116 |
| [80] | Burkard, R. E.; Çela, E.; Pardalos, P. M.; Pitsoulis, L., The quadratic assignment problem, (Pardalos, P. M.; Du, D.-Z., Handbook of Combinatorial Optimization (1998), Kluwer Academic Publishers), 241-338 · Zbl 0944.90071 |
| [81] | Burkard, R. E.; Çela, E.; Rote, G.; Woeginger, G. J., The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases, Mathematical Programming, 82, 1-2, 125-158 (1998) · Zbl 0949.90077 |
| [82] | Burkard, R. E., Selected topics on assignment problems, Discrete Applied Mathematics, 123, 1-3, 257-302 (2002) · Zbl 1036.90056 |
| [83] | Carraresi, P.; Malucelli, F., A new lower bound for the quadratic assignment problem, Operations Research, 40, 1, S22-S27 (1992) · Zbl 0755.90083 |
| [84] | Carraresi, P.; Malucelli, F., A reformulation scheme and new lower bounds for the QAP, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 147-160 · Zbl 0817.90054 |
| [85] | Çela, E., The quadratic assignment problem: Theory and algorithms, (Du, D. Z.; Pardalos, P., Combinatorial Optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht) · Zbl 0909.90226 |
| [86] | Chakrapani, J.; Skorin-Kapov, J., Massively parallel tabu search for the quadratic assignment problem, Annals of Operations Research, 41, 1-4, 327-342 (1993) · Zbl 0775.90288 |
| [87] | Chakrapani, J.; Skorin-Kapov, J., A constructive method to improve lower bounds for the quadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Providence, Rhode Island), 161-171 · Zbl 0817.90055 |
| [88] | Chen, B., Special cases of the quadratic assignment problem, European Journal of Operational Research, 81, 2, 410-419 (1995) · Zbl 0927.90083 |
| [89] | Chiang, W. C.; Chiang, C., Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation, European Journal of Operational Research, 106, 2-3, 457-488 (1998) · Zbl 0991.90127 |
| [90] | Christofides, N.; Mingozzi, A.; Toth, P., Contributions to the quadratic assignment problem, European Journal of Operational Research, 4, 243-247 (1980) · Zbl 0439.90058 |
| [91] | Christofides, N.; Gerrard, M., A graph theoretic analysis of bounds for the quadratic assignment problem, (Hansen, P., Studies on Graphs and Discrete Programming (1981), North-Holland), 61-68 · Zbl 0484.68051 |
| [92] | Christofides, N.; Benavent, E., An exact algorithm for the quadratic assignment problem, Operations Research, 37, 5, 760-768 (1989) · Zbl 0682.90064 |
| [93] | Ciriani, V.; Pisanti, N.; Bernasconi, A., Room allocation: A polynomial subcase of the quadratic assignment problem, Discrete Applied Mathematics, 144, 3, 263-269 (2004) · Zbl 1066.90060 |
| [94] | Clausen, J.; Perregaard, M., Solving large quadratic assignment problems in parallel, Computational Optimization and Applications, 8, 111-127 (1997) · Zbl 0887.90136 |
| [95] | Clausen, J.; Karisch, S. E.; Perregaard, M.; Rendl, F., On the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel, Computational Optimization and Applications, 10, 2, 127-147 (1998) · Zbl 0897.90159 |
| [96] | Colorni, A.; Dorigo, M.; Maffioli, F.; Maniezzo, V.; Righini, G.; Trubian, M., Heuristics from nature for hard combinatorial optimization problems, International Transactions in Operational Research, 3, 1, 1-21 (1996) · Zbl 0863.90120 |
| [97] | Connolly, D. T., An improved annealing scheme for the QAP, European Journal of Operational Research, 46, 93-100 (1990) · Zbl 0715.90079 |
| [98] | Costa, C. S.; Boaventura-Netto, P. O., An algebraic-combinatorial description for the asymmetric quadratic assignment problem, Advances in Modeling and Analysis A, 22, 2, 1-11 (1994) |
| [99] | Crama, Y.; Spieksma, F. C.R., Approximation algorithms for three-dimensional assignment problems with triangle inequalities, European Journal of Operational Research, 60, 273-279 (1992) · Zbl 0761.90071 |
| [100] | Cung, V.-D., Mautor, T., Michelon, P., Tavares, A., 1997. A scatter search based approach for the quadratic assignment problem. In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 165-169.; Cung, V.-D., Mautor, T., Michelon, P., Tavares, A., 1997. A scatter search based approach for the quadratic assignment problem. In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 165-169. |
| [101] | Cyganski, D.; Vaz, R. F.; Virball, V. G., Quadratic assignment problems generated with the Palubetskis algorithm are degenerate, IEEE Transactions on Circuits and Systems I—Fundamental Theory and Applications, 41, 7, 481-484 (1994) |
| [102] | Davis, L., Genetic Algorithms and Simulated Annealing (1987), Morgan Kaufmann Publishers · Zbl 0684.68013 |
| [103] | Day, R. O.; Lamont, G. B., Multiobjective quadratic assignment problem solved by an explicit building block search algorithm—MOMGA-IIa, Lecture Notes in Computer Science, 3448, 91-100 (2005) · Zbl 1119.68436 |
| [104] | Deineko, V. G.; Woeginger, G. J., A solvable case of the quadratic assignment problem, Operations Research Letters, 22, 1, 13-17 (1998) · Zbl 0910.90226 |
| [105] | Deineko, V. G.; Woeginger, G. J., A study of exponential neighborhoods for the traveling salesman problem and for the quadratic assignment problem, Mathematical Programming, Series A, 78, 519-542 (2000) · Zbl 1043.90075 |
| [106] | Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1997), Wiley: Wiley Chichester · Zbl 0899.90138 |
| [107] | Dickey, J. W.; Hopkins, J. W., Campus building arrangement using Topaz, Transportation Research, 6, 59-68 (1972) |
| [108] | Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: Optimization by a colony of cooperating agents, IEEE Transaction on Systems, Man, and Cybernetics—Part B, 26, 2, 29-41 (1996) |
| [109] | Drezner, Z., Lower bounds based on linear programming for the quadratic assignment problem, Computational Optimization and Applications, 4, 2, 159-165 (1995) · Zbl 0832.90091 |
| [110] | Drezner, Z., A new genetic algorithm for the quadratic assignment problem, Informs Journal on Computing, 15, 3, 320-330 (2003) · Zbl 1238.90108 |
| [111] | Drezner, Z.; Marcoulides, G. A., A distance-based selection of parents in genetic algorithms, (Resende, M. G.C.; de Sousa, J. P., Metaheuristics: Computer Decision-Making. Metaheuristics: Computer Decision-Making, Combinatorial Optimization Book Series (2003), Kluwer Academic Publishers), 257-278 |
| [112] | Drezner, Z., Hahn, P., Taillard, E., in press. A study of quadratic assignment problem instances that are difficult for meta-heuristic methods. In: Guignard-Spielberg, M., Spielberg, K. (Eds.), Annals of Operations Research, Special issue devoted to the State-of-the-Art in Integer Programming.; Drezner, Z., Hahn, P., Taillard, E., in press. A study of quadratic assignment problem instances that are difficult for meta-heuristic methods. In: Guignard-Spielberg, M., Spielberg, K. (Eds.), Annals of Operations Research, Special issue devoted to the State-of-the-Art in Integer Programming. · Zbl 1091.90033 |
| [113] | Drezner, Z., Compounded genetic algorithms for the quadratic assignment problem, Operations Research Letters, 33, 5, 475-480 (2005) · Zbl 1195.90090 |
| [114] | Drezner, Z., The extended concentric tabu for the quadratic assignment problem, European Journal of Operational Research, 160, 416-422 (2005) · Zbl 1067.90108 |
| [115] | Duman, E., Ilhan, O., in press. The quadratic assignment problem in the context of the printed circuit board assembly process. Computers and Operations Research.; Duman, E., Ilhan, O., in press. The quadratic assignment problem in the context of the printed circuit board assembly process. Computers and Operations Research. · Zbl 1113.90130 |
| [116] | Dunker, T.; Radons, G.; Westkämper, E., Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem, European Journal of Operational Research, 165, 1, 55-69 (2004) · Zbl 1112.90360 |
| [117] | El-Baz, M. A., A genetic algorithm for facility layout problems of different manufacturing environments, Computers and Industrial Engineering, 47, 2-3, 233-246 (2004) |
| [118] | Edwards, C. S., A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Mathematical Programming Study, 13, 35-52 (1980) · Zbl 0441.90081 |
| [119] | Elshafei, A. N., Hospital layout as a quadratic assignment problem, Operations Research Quarterly, 28, 1, 167-179 (1977) · Zbl 0353.90096 |
| [120] | Emelichev, V. A.; Kovalev, M. N.; Kravtsov, M. K., Polytopes, Graphs and Optimization (1984), Cambridge University Press · Zbl 0523.52002 |
| [121] | Euler, R., Odd cycles and a class of facets of the axial 3-index assignment polytope, Applicationes Mathematicae (Zastosowania Matematyki), 19, 375-386 (1987) · Zbl 0719.90048 |
| [122] | Fedjki, C. A.; Duffuaa, S. O., An extreme point algorithm for a local minimum solution to the quadratic assignment problem, European Journal of Operational Research, 156, 3, 566-578 (2004) · Zbl 1056.90013 |
| [123] | Feo, T. A.; Resende, M. G.C., Greedy randomized adaptive search procedures, Journal of Global Optimization, 6, 109-133 (1995) · Zbl 0822.90110 |
| [124] | Finke, G.; Burkard, R. E.; Rendl, F., Quadratic assignment problems, Annals of Discrete Mathematics, 31, 61-82 (1987) · Zbl 0607.90026 |
| [125] | Fischer, I.; Gruber, G.; Rendl, F.; Sotirov, R., Computational experience with a bundle approach for semidefinite cutting plane relaxations of max-cut and equipartition, Mathematical Programming, 105, 451-469 (2006) · Zbl 1085.90044 |
| [126] | Fleurent, C.; Ferland, J. A., Genetic hybrids for the quadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 173-187 · Zbl 0817.90056 |
| [127] | Fleurent, C.; Glover, F., Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory, INFORMS Journal on Computing, 11, 189-203 (1999) · Zbl 1040.90541 |
| [128] | Forsberg, J. H.; Delaney, R. M.; Zhao, Q.; Harakas, G.; Chandran, R., Analyzing lanthanide-included shifts in the NMR spectra of lanthanide (III) complexes derived from 1,4,7,10-tetrakis \((N,N\)-diethylacetamido)-1,4,7,10-tetraazacyclododecane, Inorganic Chemistry, 34, 3705-3715 (1994) |
| [129] | Francis, R. L.; White, J. A., Facility Layout and Location: An Analytical Approach (1974), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [130] | Freeman, R. J.; Gogerty, D. C.; Graves, G. W.; Brooks, R. B.S., A mathematical model of supply for space operations, Operations Research, 14, 1-15 (1966) |
| [131] | Frenk, J. B.G.; Houweninge, M. V.; Kan, A. H.G. R., Asymptotic properties of the quadratic assignment problem, Mathematics of Operations Research, 10, 1, 100-116 (1985) · Zbl 0576.90061 |
| [132] | Frieze, A. M., A bilinear programming formulation of the 3-dimensional assignment problems, Mathematical Programming, 7, 376-379 (1974) · Zbl 0296.90031 |
| [133] | Frieze, A. M.; Yadegar, J., An algorithm for solving 3-dimensional assignment problems with applications to scheduling a teaching practice, Operations Research, 32, 989-995 (1981) · Zbl 0464.90055 |
| [134] | Frieze, A. M., Complexity of a 3-dimensional assignment problem, European Journal of Operational Research, 13, 161-164 (1983) · Zbl 0507.90057 |
| [135] | Frieze, A. M.; Yadegar, J., On the quadratic assignment problem, Discrete Applied Mathematics, 5, 89-98 (1983) · Zbl 0502.90062 |
| [136] | Gambardella, L. M.; Taillard, D.; Dorigo, M., Ant colonies for the QAP, Journal of the Operational Research Society, 50, 167-176 (1999) · Zbl 1054.90621 |
| [137] | Gavett, J. W.; Plyter, N. V., The optimal assignment of facilities to locations by branch-and-bound, Operations Research, 14, 210-232 (1966) |
| [138] | Geoffrion, A. M.; Graves, G. W., Scheduling parallel production lines with changeover costs: Practical applications of a quadratic assignment/LP approach, Operations Research, 24, 595-610 (1976) · Zbl 0341.90030 |
| [139] | Gilmore, P. C., Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics, 10, 305-313 (1962) · Zbl 0118.15101 |
| [140] | Glover, F., Heuristics for integer programming using surrogate constraints, Decision Science, 8, 156-166 (1977) |
| [141] | Glover, F., Tabu search—Part I, ORSA Journal on Computing, 1, 190-206 (1989) · Zbl 0753.90054 |
| [142] | Glover, F., Tabu search—Part II, ORSA Journal on Computing, 2, 4-32 (1989) · Zbl 0771.90084 |
| [143] | Goldbarg, M. C.; Goldbarg, E. F.G., Transgenética computacional: Uma aplicação ao problema quadrático de alocação, Pesquisa Operacional, 22, 3, 359-386 (2002) |
| [144] | Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Wokingham, England · Zbl 0721.68056 |
| [145] | Gong, D.; Yamazaki, G.; Gen, M.; Xu, W., A genetic algorithm method for one-dimensional machine location problems, International Journal of Production Economics, 60-1, 337-342 (1999) |
| [146] | Gouveia, L.; Voß, S., A classification of formulations for the (time-dependent) traveling salesman problem, European Journal of Operational Research, 83, 1, 69-82 (1995) · Zbl 0903.90170 |
| [147] | Graves, G. W.; Whinston, A. B., An algorithm for the quadratic assignment problem, Management Science, 17, 7, 453-471 (1970) · Zbl 0193.18803 |
| [148] | Gutin, G.; Yeo, A., Polynomial approximation algorithms for TSP and QAP with a factorial domination number, Discrete Applied Mathematics, 119, 1-2, 107-116 (2002) · Zbl 0996.90061 |
| [149] | Hadley, S. W.; Rendl, F.; Wolkowicz, H., Bounds for the quadratic assignment problem using continuous optimization techniques, (Integer Programming and Combinatorial Optimization (1990), University of Waterloo Press), 237-248 |
| [150] | Hadley, S. W.; Rendl, F.; Wolkowicz, H., Nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality, Linear Algebra and its Applications, 58, 109-124 (1992) · Zbl 0767.90070 |
| [151] | Hadley, S. W.; Rendl, F.; Wolkowicz, H., A new lower bound via projection for the quadratic assignment problem, Mathematics of Operations Research, 17, 727-739 (1992) · Zbl 0767.90059 |
| [152] | Hadley, S. W.; Rendl, F.; Wolkowicz, H., Symmetrization of nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality, Linear Algebra and its Applications, 167, 53-64 (1992) · Zbl 0767.90070 |
| [153] | Hadley, S. W., Domination and separation applied to the quadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 189-196 · Zbl 0824.90090 |
| [154] | Haghani, A.; Chen, M.-C., Optimizing gate assignments at airport terminals, Transportation Research A, 32, 6, 437-454 (1998) |
| [155] | Hahn, P.; Grant, T., Lower bounds for the quadratic assignment problem based upon a dual formulation, Operations Research, 46, 912-922 (1998) · Zbl 0979.90100 |
| [156] | Hahn, P.; Grant, T.; Hall, N., A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method, European Journal of Operational Research, 108, 629-640 (1998) · Zbl 0947.90129 |
| [157] | Hahn, P., 2000. Progress in solving the Nugent instances of the quadratic assignment problem. Available from: <http://www-unix.mcs.anl.gov/metaneos/nug30/nug30.pdf>; Hahn, P., 2000. Progress in solving the Nugent instances of the quadratic assignment problem. Available from: <http://www-unix.mcs.anl.gov/metaneos/nug30/nug30.pdf> |
| [158] | Hahn, P. M.; Hightower, W. L.; Johnson, T. A.; Guignard-Spielberg, M.; Roucairol, C., Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem, Yugoslavian Journal of Operational Research, 11, 1, 41-60 (2001) · Zbl 1073.90524 |
| [159] | Hahn, P.M., Hightower, W.L., Johnson, T.A., Guignard-Spielberg, M., Roucairol, C., 2001b. A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Working Paper 01-04, Systems Engineering Department, University of Pennsylvania.; Hahn, P.M., Hightower, W.L., Johnson, T.A., Guignard-Spielberg, M., Roucairol, C., 2001b. A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Working Paper 01-04, Systems Engineering Department, University of Pennsylvania. |
| [160] | Hahn, P. M.; Krarup, J., A hospital facility layout problem finally solved, Journal of Intelligent Manufacturing, 12, 487-496 (2001) |
| [161] | Hahn, P.M., Kim, B.-J., Hightower, W.L., Stützle, T., Kanthak, S., Samra, H., Ding, Z., Guignard, M., 2004. The quadratic three-dimensional assignment problem: Exact and heuristic solution methods. OPIM Working Report No. 04-08-02, The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania, USA.; Hahn, P.M., Kim, B.-J., Hightower, W.L., Stützle, T., Kanthak, S., Samra, H., Ding, Z., Guignard, M., 2004. The quadratic three-dimensional assignment problem: Exact and heuristic solution methods. OPIM Working Report No. 04-08-02, The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania, USA. · Zbl 1149.90364 |
| [162] | Hanan, M.; Kurtzberg, J. M., A review of the placement and quadratic assignment problem, SIAM Review, 14, 324-342 (1972) · Zbl 0241.90048 |
| [163] | Hansen, P.; Lih, K-W., Improved algorithms for partitioning problems in parallel, pipelined, and distributed computing, IEEE Transactions on Computers, 41, 6, 769-771 (1992) |
| [164] | Hasegawa, M.; Ikeguchi, T.; Aihara, K.; Itoh, K., A novel chaotic search for quadratic assignment problems, European Journal of Operational Research, 139, 3, 543-556 (2002) · Zbl 0995.90059 |
| [165] | Heffley, D. R., The quadratic assignment problem: A note, Econometrica, 40, 6, 1155-1163 (1972) |
| [166] | Heffley, D. R., Assigning runners to a relay team, (Ladany, S. P.; Machol, R. E., Optimal Strategies in Sports (1977), North Holland: North Holland Amsterdam), 169-171 |
| [167] | Heffley, D. R., Decomposition of the Koopmans-Beckmann problem, Regional Science and Urban Economics, 10, 4, 571-580 (1980) |
| [168] | Heider, C. H., An \(N\)-step, 2-variable search algorithm for the component placement problem, Naval Research Logistics Quarterly, 20, 699-724 (1973) · Zbl 0275.90028 |
| [169] | Herroeleven, W.; Vangils, A., On the use of flow dominance in complexity measures for facility layout problems, International Journal of Production Research, 23, 97-108 (1985) |
| [170] | Hillier, F. S.; Michael, M. C., Quadratic assignment problem algorithms and the location of indivisible facilities, Management Science, 13, 44-57 (1966) |
| [171] | Ho, Y. C.; Moodie, C. L., A hybrid approach for concurrent layout design of cells and their flow paths in a tree configuration, International Journal of Production Research, 38, 4, 895-928 (2000) · Zbl 0949.90607 |
| [172] | Hubert, L.; Schulz, J., Quadratic assignment as a general data analysis strategy, British Journal of Mathematical Psychology, 29, 190-241 (1976) · Zbl 0356.92027 |
| [173] | Hubert, L., Assignment methods in combinatorial data analysis, (Statistics: Textbooks and Monographs Series, vol. 73 (1987), Marcel Dekker) · Zbl 0628.62003 |
| [174] | Huntley, C. L.; Brown, D. E., Parallel genetic algorithms with local search, Computers and Operations Research, 23, 6, 559-571 (1996) · Zbl 0847.90116 |
| [175] | Ishii, S.; Sato, M., Constrained neural approaches to quadratic assignment problems, Neural Networks, 11, 6, 1073-1082 (1998) |
| [176] | Ishii, S.; Sato, M., Doubly constrained network for combinatorial optimization, Neurocomputing, 43, 1-4, 239-257 (2001) · Zbl 1016.68077 |
| [177] | Jünger, M.; Kaibel, V., On the SQAP-polytope, SIAM Journal on Optimization, 11, 2, 444-463 (2000) · Zbl 1010.90039 |
| [178] | Jünger, M.; Kaibel, V., The QAP-polytope and the star transformation, Discrete Applied Mathematics, 111, 3, 283-306 (2001) · Zbl 0978.90071 |
| [179] | Jünger, M.; Kaibel, V., Box-inequalities for quadratic assignment polytopes, Mathematical Programming, 91, 1, 175-197 (2001) · Zbl 1064.90053 |
| [180] | Kaibel, V., Polyhedral combinatorics of quadratic assignment problems with less objects than locations, Lecture Notes in Computer Science, 1412, 409-422 (1998) · Zbl 0910.90238 |
| [181] | Kaku, B. K.; Thompson, G. L., An exact algorithm for the general quadratic assignment problem, European Journal of Operational Research, 2, 382-390 (1986) · Zbl 0581.90054 |
| [182] | Karisch, S. E.; Rendl, F.; Wolkowicz, H., Trust regions and relaxations for the quadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 199-219 · Zbl 0819.90052 |
| [183] | Karisch, S. E.; Rendl, F., Lower bounds for the quadratic assignment problem via triangle decompositions, Mathematical Programming, 71, 137-152 (1995) · Zbl 0846.90091 |
| [184] | Karisch, S. E.; Çela, E.; Clausen, J.; Espersen, T., A dual framework for lower bounds of the quadratic assignment problem based on linearization, Computing, 63, 351-403 (1999) · Zbl 1138.90458 |
| [185] | Karmarkar, N. K.; Ramakrishnan, K. G., Computational results of an interior point algorithm for large-scale linear programming, Mathematical Programming, 52, 555-586 (1991) · Zbl 0739.90042 |
| [186] | Kaufman, L.; Broeckx, F., An algorithm for the quadratic assignment problem using Bender’s decomposition, European Journal of Operation Research, 2, 204-211 (1978) · Zbl 0378.90065 |
| [187] | Kellerer, H.; Wirsching, G., Bottleneck quadratic assignment problems and the bandwidth problem, Asia-Pacific Journal of Operational Research, 15, 169-177 (1998) · Zbl 0917.90260 |
| [188] | Kelly, J. P.; Laguna, M.; Glover, F., A study of diversification strategies for the quadratic assignment problem, Computers and Operations Research, 21, 8, 885-893 (1994) · Zbl 0814.90060 |
| [189] | Khare, V. K.; Khare, M. K.; Neema, M. L., Estimation of distribution parameters associated with facilities design problems involving forward and backtracking of materials, Computers and Industrial Engineering, 14, 1, 63-75 (1988) |
| [190] | Khare, V. K.; Khare, M. K.; Neema, M. L., Combined computer-aided approach for the facilities design problem and estimation of the distribution parameter in the case of multigoal optimization, Computers and Industrial Engineering, 14, 4, 465-476 (1988) |
| [191] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [192] | Kleeman, M. P.; Day, R. O.; Lamont, G. B., Analysis of a parallel MOEA solving the multi-objective quadratic assignment problem, Lecture Notes in Computer Science, 3103, 402-403 (2004) |
| [193] | Knowles, J. D.; Corne, D. W., Towards landscape analyses to inform the design of a hybrid local search for the multiobjective quadratic assignment problem, (Abraham, A.; Ruiz-del-Solar, J.; Koppen, M., Soft Computing Systems: Design, Management and Applications (2002), IOS Press: IOS Press Amsterdam), 271-279 |
| [194] | Knowles, J.; Corne, D., Instance generators and test suites for the multiobjective quadratic assignment problem, Lecture Notes in Computer Science, 2632, 295-310 (2003) · Zbl 1036.90542 |
| [195] | Kochhar, J. S.; Foster, B. T.; Heragu, S. S., Hope: A genetic algorithm for the unequal area facility layout problem, Computers and Operations Research, 25, 7-8, 583-594 (1998) · Zbl 1042.90579 |
| [196] | Koopmans, T. C.; Beckmann, M. J., Assignment problems and the location of economic activities, Econometrica, 25, 53-76 (1957) · Zbl 0098.12203 |
| [197] | Krackhardt, D., Predicting with networks: Nonparametric multiple regression analysis of dyadic data, Social Networks, 10, 4, 359-381 (1988) |
| [198] | Krarup, J.; Pruzan, P. M., Computer-aided layout design, Mathematical Programming Study, 9, 75-94 (1978) · Zbl 0413.90058 |
| [199] | Kreher, D. L.; Stinson, D. R., Combinatorial algorithms: Generation, enumeration, and search, (DIMACS Discrete Mathematics and its Applications (1998), CRC Press) · Zbl 0972.68526 |
| [200] | Lacksonen, T. A.; Enscore, E. E., Quadratic assignment algorithms for the dynamic layout, International Journal of Production Research, 31, 3, 503-517 (1993) |
| [201] | Land, A. M., A problem of assignment with interrelated costs, Operational Research Quarterly, 14, 185-198 (1963) |
| [202] | Laursen, P. S., Simple approaches to parallel branch-and-bound, Parallel Computing, 19, 143-152 (1993) · Zbl 0809.65060 |
| [203] | Lawler, E. L., The quadratic assignment problem, Management Science, 9, 586-599 (1963) · Zbl 0995.90579 |
| [204] | Li, Y.; Pardalos, P. M., Generating quadratic assignment test problems with known optimal permutations, Computational Optimization and Applications, 1, 163-184 (1992) · Zbl 0773.90083 |
| [205] | Li, Y.; Pardalos, P. M.; Ramakrishnan, K. G.; Resende, M. G.C., Lower bounds for the quadratic assignment problem, Operations Research, 50, 387-410 (1994) · Zbl 0813.90095 |
| [206] | Li, Y.; Pardalos, P. M.; Resende, M. G.C., A greedy randomized adaptive search procedure for the quadratic assignment problem, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 237-261 · Zbl 0817.90057 |
| [207] | Li, W.-J.; Smith, M., An algorithm for quadratic assignment problems, European Journal of Operational Research, 81, 205-216 (1995) · Zbl 0930.90071 |
| [208] | Liang, Y., Combinatorial optimization by Hopfield networks using adjusting neurons, Information Sciences, 94, 1-4, 261-276 (1996) |
| [209] | Lim, M. H.; Yuan, Y.; Omatu, S., Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem, Computational Optimization and Applications, 15, 3, 248-268 (2000) · Zbl 0947.90057 |
| [210] | Lim, M. H.; Yuan, Y.; Omatu, S., Extensive testing of a hybrid genetic algorithm for solving quadratic assignment problems, Computational Optimization and Applications, 23, 1, 47-64 (2002) · Zbl 1036.90057 |
| [211] | Loiola, E. M.; Abreu, N. M.M.; Boaventura-Netto, P. O., Uma revisão comentada das abordagens do problema quadrático de alocação, Pesquisa Operacional, 24, 1, 73-110 (2004), (in Portuguese) |
| [212] | Lopez-Ibanez, M.; Paquete, L.; Stutzle, T., On the design of ACO for the biobjective quadratic assignment problem, Lecture Notes in Computer Science, 3172, 214-225 (2004) |
| [213] | Los, M., Simultaneous optimization of land use and transportation: A synthesis of the quadratic assignment problem and the optimal network problem, Regional Science and Urban Economics, 8, 1, 21-42 (1978) |
| [214] | Lovász, L.; Schrijver, A., Cones of matrices and set-functions, and 0-1 optimization, SIAM Journal on Optimization, 1, 166-190 (1991) · Zbl 0754.90039 |
| [215] | Love, R. F.; Wong, J. Y., Solving quadratic assignment problems with rectangular distances and integer programming, Naval Research Logistics Quarterly, 23, 623-627 (1976) · Zbl 0377.90091 |
| [216] | Love, R. F.; Wong, J. Y., On solving a one-dimensional space allocation problem with integer programming, INFOR, 14, 139-143 (1976) · Zbl 0329.68038 |
| [217] | Magirou, V. F.; Milis, J. Z., An algorithm for the multiprocessor assignment problem, Operations Research Letters, 8, 351-356 (1989) · Zbl 0679.68055 |
| [218] | Magos, D.; Miliotis, P., An algorithm for the planar three-index assignment problem, European Journal of Operational Research, 77, 141-153 (1994) · Zbl 0810.90093 |
| [219] | Magos, D., Tabu search for the planar three-index assignment problem, Journal of Global Optimization, 8, 35-48 (1996) · Zbl 0857.90106 |
| [220] | Malucelli, F., 1993. Quadratic assignment problems: Solution methods and applications. PhD thesis: TE-9/93, University of Pisa, Genova-Udine.; Malucelli, F., 1993. Quadratic assignment problems: Solution methods and applications. PhD thesis: TE-9/93, University of Pisa, Genova-Udine. |
| [221] | Maniezzo, V.; Colorni, A., Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem, European Journal of Operational Research, 81, 1, 188-204 (1995) · Zbl 0912.90240 |
| [222] | Maniezzo, V.; Colorni, A., The ant system applied to the quadratic assignment problem, Knowledge and Data Engineering, 11, 5, 769-778 (1999) |
| [223] | Mans, B.; Mautor, T.; Roucairol, C., A parallel depth first search branch and bound algorithm for the quadratic assignment problem, European Journal of Operational Research, 81, 617-628 (1995) · Zbl 0906.90147 |
| [224] | Marins, M.T.A, Abreu, N.M.M., Jurkiewicz, S., 2004. Automorphism of groups and quadratic assignment problem. Annals of XII Congreso Latino-Iberoamericano de Investigación de Operaciones y Sistemas (CLAIO 2004), La Habana, Cuba.; Marins, M.T.A, Abreu, N.M.M., Jurkiewicz, S., 2004. Automorphism of groups and quadratic assignment problem. Annals of XII Congreso Latino-Iberoamericano de Investigación de Operaciones y Sistemas (CLAIO 2004), La Habana, Cuba. |
| [225] | Martin, W., Fast equi-partitioning of rectangular domains using stripe decomposition, Discrete Applied Mathematics, 82, 1-3, 193-207 (1998) · Zbl 0897.90160 |
| [226] | Mason, A.; Rönnqvist, M., Solution methods for the balancing of jet turbines, Computers and Operations Research, 24, 2, 153-167 (1997) · Zbl 0888.90158 |
| [227] | Mautor, T.; Roucairol, C., A new exact algorithm for the solution of quadratic assignment problems, Discrete Applied Mathematics, 55, 281-293 (1994) · Zbl 0819.90054 |
| [228] | Mautor, T.; Roucairol, C., Difficulties of exact methods for solving the QAP, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 263-274 · Zbl 0817.90058 |
| [229] | Mavridou, T.; Pardalos, P. M., Simulated annealing and genetic algorithms for the facility layout problem: A survey, Computational Optimization and Applications, 7, 111-126 (1997) · Zbl 0883.90078 |
| [230] | Mavridou, T.; Pardalos, P. M.; Pitsoulis, L. S.; Resende, M. G.C., A GRASP for the biquadratic assignment problem, European Journal of Operational Research, 105, 3, 613-621 (1998) · Zbl 0955.90066 |
| [231] | Medova, E., Using QAP bounds for the circulant TSP to design reconfigurable networks, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 275-292 · Zbl 0817.90024 |
| [232] | Merz, P.; Freisleben, B., A genetic local search approach to the quadratic assignment problem, (Back, T., Proceedings of the 7th International Conference on Genetic Algorithms (1997), Morgan Kaufmann), 465-472 |
| [233] | Merz, P.; Freisleben, B., A comparison of mimetic algorithms, tabu search, and ant colonies for the quadratic assignment problem, (Proceedings of the 1999 International Congress of Evolutionary Computation (CEC’99) (1999), IEEE Press), 2063-2070 |
| [234] | Merz, P.; Freisleben, B., Fitness landscape analysis and mimetic algorithms for the quadratic assignment problem, IEEE Transactions on Evolutionary Computation, 4, 4, 337-352 (2000) |
| [235] | Michelon, P.; Maculan, N., Lagrangean decomposition for integer nonlinear programming with linear constraints, Mathematical Programming, 52, 2, 303-313 (1991) · Zbl 0753.90047 |
| [236] | Middendorf, M.; Reischle, F.; Schmeck, H., Multi colony ant algorithms, Journal of Heuristics, 8, 3, 305-320 (2002) · Zbl 1012.68792 |
| [237] | Milis, I. Z.; Magirou, V. F., A Lagrangean-relaxation algorithm for sparse quadratic assignment problems, Operations Research Letters, 17, 2, 69-76 (1995) · Zbl 0836.90128 |
| [238] | Mills, P.; Tsang, E.; Ford, J., Applying an extended guided local search to the quadratic assignment problem, Annals of Operations Research, 118, 1-4, 121-135 (2003) · Zbl 1026.90057 |
| [239] | Miranda, G.; Luna, H. P.L.; Mateus, G. R.; Ferreira, R. P.M., A performance guarantee heuristic for electronic components placement problems including thermal effects, Computers and Operations Research, 32, 2937-2957 (2005) · Zbl 1071.90580 |
| [240] | Mirchandani, P.B., Obata, T., 1979. Algorithms for a class of quadratic assignment problems. Presented at the Joint ORSA/TIMS National Meeting, New Orleans.; Mirchandani, P.B., Obata, T., 1979. Algorithms for a class of quadratic assignment problems. Presented at the Joint ORSA/TIMS National Meeting, New Orleans. |
| [241] | Misevicius, A., A new algorithm for the quadratic assignment problem, Information Technology and Control, 5, 39-44 (1997) |
| [242] | Misevicius, A.; Riskus, A., Multistart threshold accepting: Experiments with the quadratic assignment problem, Information Technology and Control, 12, 31-39 (1999) |
| [243] | Misevicius, A., An intensive search algorithm for the quadratic assignment problem, Informatica, 11, 145-162 (2000) · Zbl 0972.90064 |
| [244] | Misevicius, A., A new improved simulated annealing algorithm for the quadratic assignment problem, Information Technology and Control, 17, 29-38 (2000) |
| [245] | Misevicius, A., Combining simulated annealing and tabu search for the quadratic assignment problem, Information Technology and Control, 20, 37-50 (2001) |
| [246] | Misevicius, A.; Rubliauskas, D.; Smolinskas, J., Reconstruct and improve principle-based algorithm for the quadratic assignment problem, Information Technology and Control, 23, 7-17 (2002) |
| [247] | Misevicius, A., A modification of tabu search and its applications to the quadratic assignment problem, Information Technology and Control, 27, 12-20 (2003) |
| [248] | Misevicius, A., Genetic algorithm hybridized with ruin and recreate procedure: Application to the quadratic assignment problem, Knowledge-Based Systems, 16, 5-6, 261-268 (2003) · Zbl 1095.68743 |
| [249] | Misevicius, A., A modified simulated annealing algorithm for the quadratic assignment problem, Informatica, 14, 4, 497-514 (2003) · Zbl 1176.90665 |
| [250] | Misevicius, A., Ruin and recreate principle-based approach for the quadratic assignment problem, Lecture Notes in Computer Science, 2723, 598-609 (2003) · Zbl 1028.68842 |
| [251] | Misevicius, A., An improved hybrid optimization algorithm for the quadratic assignment problem, Mathematical Modelling and Analysis, 9, 2, 149-168 (2004) · Zbl 1095.90097 |
| [252] | Misevicius, A., An improved hybrid genetic algorithm: New results for the quadratic assignment problem, Knowledge-Based Systems, 17, 2-4, 65-73 (2004) · Zbl 1095.90097 |
| [253] | Misevicius, A., A tabu search algorithm for the quadratic assignment problem, Computational Optimization and Applications, 30, 1, 95-111 (2005) · Zbl 1130.90041 |
| [254] | Mladenovic, N.; Hansen, P., Variable neighborhood search, Computers and Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119 |
| [255] | Moe, R., GRIBB—Branch-and-bound methods on the Internet, Parallel Processing and Applied Mathematics 2003. Parallel Processing and Applied Mathematics 2003, Lecture Notes in Computer Science, 3019, 1020-1027 (2003) |
| [256] | Nishiyama, T.; Tsuchiya, K.; Tsujita, K., A Markov chain Monte Carlo algorithm for the quadratic assignment problem based on replicator equations, Lecture Notes in Computer Science, 2130, 148-155 (2001) · Zbl 1001.68879 |
| [257] | Nissen, V., Solving the quadratic assignment problem with clues from nature, IEEE Transactions on Neural Networks, 5, 1, 66-72 (1994) |
| [258] | Nissen, V.; Paul, H., A modification of threshold accepting and its application to the quadratic assignment problem, OR Spektrum, 17, 2-3, 205-210 (1995) · Zbl 0842.90092 |
| [259] | Nissen, V., Quadratic assignment, (Back, T.; Fogel, D. B.; Michalewicz, Z.; Baeck, T., Handbook of Evolutionary Computation, vol. G9.10 (1997), Institute of Physics Publishing and Oxford University Press), 1-8 · Zbl 0883.68001 |
| [260] | Nugent, C. E.; Vollmann, T. E.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, Operations Research, 16, 150-173 (1968) |
| [261] | Obuchi, Y.; Masui, H.; Ohki, M., Weighted parallel problem solving by optimization networks, Neural Networks, 9, 2, 357-366 (1996) |
| [262] | Oliveira, C. A.S.; Pardalos, M. P.; Resende, M. G.G., GRASP with path relinking for the quadratic assignment problem, (Experimental and Efficient Algorithms, Third International Workshop (WEA 2004), Brazil. Experimental and Efficient Algorithms, Third International Workshop (WEA 2004), Brazil, LNCS 3059 (2004), Springer), 356-368 |
| [263] | Osman, I. H.; Laporte, G., Metaheuristics: A bibliography, Annals of Operations Research, 63, 513-623 (1996) · Zbl 0849.90097 |
| [264] | Ostrowski, T.; Ruoppila, V. T., Genetic annealing search for index assignment in vector quantization, Pattern Recognition Letters, 18, 4, 311-318 (1997) |
| [265] | Padberg, M. W.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, 33, 60-100 (1991) · Zbl 0734.90060 |
| [266] | Padberg, W.; Rijal, P., Location, Scheduling, Design and Integer Programming (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0879.68075 |
| [267] | Palubeckis, G., Generating hard test instances with known optimal solution for the rectilinear quadratic assignment problem, Journal of Global Optimization, 15, 2, 127-156 (1999) · Zbl 0957.90081 |
| [268] | Palubeckis, G., An algorithm for construction of test cases for the quadratic assignment problem, Informatica, 11, 3, 281-296 (2000) · Zbl 0983.90034 |
| [269] | Paquete, L.; Stützle, T., A study of stochastic local search algorithms for biobjective QAP with correlated flow matrices, European Journal of Operational Research, 169, 3, 943-959 (2004) · Zbl 1079.90113 |
| [270] | Pardalos, P.; Crouse, J., A parallel algorithm for the quadratic assignment problem, (Proceedings of the Supercomputing Conference 1989 (1989), ACM Press), 351-360 |
| [271] | Pardalos, P. M.; Murthy, K. A.; Harrison, T. P., A computational comparison of local search heuristics for solving quadratic assignment problems, Informatica, 4, 1-2, 172-187 (1993) · Zbl 0925.68120 |
| [272] | Pardalos, P. M.; Wolkowicz, H., Quadratic assignment and related problems, (Proceedings DIMACS Workshop on Quadratic Assignment Problem. Proceedings DIMACS Workshop on Quadratic Assignment Problem, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island) · Zbl 0797.00027 |
| [273] | Pardalos, P. M.; Rendl, F.; Wolkowicz, H., The quadratic assignment problem: A survey of recent developments, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 1-42 · Zbl 0817.90059 |
| [274] | Pardalos, P. M.; Ramakrishnan, K. G.; Resende, M. G.C.; Li, Y., Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem, SIAM Journal on Optimization, 7, 1, 280-294 (1997) · Zbl 0873.90072 |
| [275] | Peng, T.; Huanchen, W.; Dongme, Z., Simulated annealing for the quadratic assignment problem: A further study, Computers and Industrial Engineering, 31, 3-4, 925-928 (1996) |
| [276] | Phillips, A. T.; Rosen, J. B., A quadratic assignment formulation of the molecular-conformation problem, Journal of Global Optimization, 4, 2, 229-241 (1994) · Zbl 0797.90116 |
| [277] | Pierce, J. F.; Crowston, W. B., Tree-search algorithms for quadratic assignment problems, Naval Research Logistics Quarterly, 18, 136 (1971) · Zbl 0216.54404 |
| [278] | Pierskalla, W. P., The tri-substitution method for the three-multidimensional assignment problem, Canadian Operational Research Society Journal, 5, 2, 71-81 (1967) · Zbl 0149.16304 |
| [279] | Pierskalla, W.F., 1967b. The Multi-Dimensional Assignment Problem. Technical Memorandum No. 93, Operations Research Department, CASE Institute of Technology, September 1967. Available from: <http://www.anderson.ucla.edu/faculty/william.pierskalla/Chronological_Bank/Research_and_Publication_Chro.html#Mathematical>; Pierskalla, W.F., 1967b. The Multi-Dimensional Assignment Problem. Technical Memorandum No. 93, Operations Research Department, CASE Institute of Technology, September 1967. Available from: <http://www.anderson.ucla.edu/faculty/william.pierskalla/Chronological_Bank/Research_and_Publication_Chro.html#Mathematical> |
| [280] | Pierskalla, W. P., The multidimensional assignment problem, Operations Research, 16, 422-431 (1968) · Zbl 0164.50003 |
| [281] | Pitsoulis, L. S.; Pardalos, P. M.; Hearn, D. W., Approximate solutions to the turbine balancing problem, European Journal of Operational Research, 130, 1, 147-155 (2001) · Zbl 1067.90519 |
| [282] | Pollatschek, M. A.; Gershoni, N.; Radday, Y. T., Optimization of the typewriter keyboard by simulation, Angewandte Informatik, 17, 438-439 (1976) |
| [283] | Poore, A., Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking, Computational Optimization and Applications, 3, 27-57 (1994) · Zbl 0818.93070 |
| [284] | Poore, A., Partitioning multiple data sets: Multidimensional assignment and Lagrangean relaxation, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16 (1994), AMS: AMS Rhode Island), 317-341 · Zbl 0797.00027 |
| [285] | Poore, A., 1995. Multidimensional assignment and multitarget tracking. In: DIMACS Series DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 19, pp. 169-196.; Poore, A., 1995. Multidimensional assignment and multitarget tracking. In: DIMACS Series DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 19, pp. 169-196. · Zbl 0818.90064 |
| [286] | Poore, A.; Robertson, A., A new Lagrangean relaxation based algorithm for a class of multidimensional assignment problems, Computational Optimization and Applications, 8, 129-150 (1997) · Zbl 0887.90143 |
| [287] | Povh, J., Rendl, F., 2006. Copositive and semidefinite relaxations of the quadratic assignment problem. Unfinished Technical Report, Department of Mathematics, University of Klagenfurt.; Povh, J., Rendl, F., 2006. Copositive and semidefinite relaxations of the quadratic assignment problem. Unfinished Technical Report, Department of Mathematics, University of Klagenfurt. · Zbl 1167.90597 |
| [288] | QAPLIB, 2004. QAPLIB Home Page <http://www.seas.upenn.edu/qaplib/>; QAPLIB, 2004. QAPLIB Home Page <http://www.seas.upenn.edu/qaplib/> |
| [289] | Qi, L.; Balas, E.; Gwan, G., A new facet class and a polyhedral method for the three-index assignment problem, (Du, D.-Z.; Sun, J., Advances in Optimization and Approximation (1994), Kluwer Academic), 256-274 · Zbl 0830.90105 |
| [290] | Queyranne, M., Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems, Operations Research Letters, 4, 231-234 (1986) · Zbl 0599.90085 |
| [291] | Rabak, C. S.; Sichman, J. S., Using A-Teams to optimize automatic insertion of electronic components, Advanced Engineering Informatics, 17, 2, 95-106 (2003) |
| [292] | Ramachandran, B.; Pekny, J. F., Lower bounds for nonlinear assignment problems using many body interactions, European Journal of Operational Research, 105, 1, 202-215 (1998) · Zbl 0957.90075 |
| [293] | Ramakrishnan, K. G.; Resende, M. G.C.; Ramachandran, B.; Pekny, J. F., Tight QAP bounds via linear programming, (Pardalos, P. M.; Migdalas, A.; Burkard, R. E., Combinatorial and Global Optimization (2002), World Scientific Publishing: World Scientific Publishing Singapore), 297-303 · Zbl 1012.90030 |
| [294] | Randall, M., Near parameter free ant colony optimization, Lecture Notes in Computer Science, 3172, 374-381 (2004) |
| [295] | Rangel, M. C.; Abreu, N. M.M., Ordenações parciais nos conjuntos das soluções dos problemas de alocação linear e quadrático (in Portuguese), Pesquisa Operacional, 23, 2, 265-284 (2003) |
| [296] | Rangel, M. C.; Abreu, N. M.M.; Boaventura-Netto, P. O., GRASP para o PQA: Um limite de aceitação para soluções iniciais (in Portuguese), Pesquisa Operacional, 20, 1, 45-58 (2000) |
| [297] | Rendl, F., Ranking scalar products to improve bounds for the quadratic assignment problem, European Journal of Operational Research, 20, 363-372 (1985) · Zbl 0565.90055 |
| [298] | Rendl, F., Sotirov, R., 2003. Bounds for the quadratic assignment problem using the bundle method. Accepted for publication in Math. Programming B, and will appear in the special issue dedicated to Jos Sturm, First available in 2003 as a Technical Report, Department of Mathematics, University of Klagenfurt.; Rendl, F., Sotirov, R., 2003. Bounds for the quadratic assignment problem using the bundle method. Accepted for publication in Math. Programming B, and will appear in the special issue dedicated to Jos Sturm, First available in 2003 as a Technical Report, Department of Mathematics, University of Klagenfurt. |
| [299] | Rendl, F.; Wolkowicz, H., Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Mathematical Programming, 53, 63-78 (1992) · Zbl 0751.90051 |
| [300] | Resende, M. G.C.; Ramakrishnan, K. G.; Drezner, Z., Computing lower bounds for the quadratic assignment with an interior point algorithm for linear programming, Operations Research, 43, 781-791 (1995) · Zbl 0843.90068 |
| [301] | Resende, M. G.C.; Pardalos, P. M.; Li, Y., Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP, ACM Transactions on Mathematical Software, 22, 1, 104-118 (1996) · Zbl 0884.65052 |
| [302] | Rogger, A.; Fiechter, C. N.; Werra, D., Basic ideas of tabu search with an application to traveling salesman and quadratic assignment, Ricerca Operativa, 62, 5-28 (1992) |
| [303] | Rossin, D. F.; Springer, M. C.; Klein, B. D., New complexity measures for the facility layout problem: An empirical study using traditional and neural network analysis, Computers and Industrial Engineering, 36, 3, 585-602 (1999) |
| [304] | Roucairol, C., A reduction method for quadratic assignment problem, Methods of Operations Research, 32, 185-187 (1979) · Zbl 0414.90070 |
| [305] | Roucairol, C., A parallel branch and bound algorithm for the quadratic assignment problem, Discrete Applied Mathematics, 18, 211-225 (1987) · Zbl 0632.90047 |
| [306] | Roupin, F., From linear to semidefinite programming: An algorithm to obtain semidefinite relaxations for bivalent quadratic problems, Journal of Combinatorial Optimization, 8, 4, 469-493 (2004) · Zbl 1079.90085 |
| [307] | Sahni, S.; Gonzales, T., P-complete approximation problems, Journal of the Association for Computing Machinery, 23, 555-565 (1976) · Zbl 0348.90152 |
| [308] | Samra, H.; Ding, Z.; Hahn, P. M., Symbol mapping diversity design for multiple packet transmissions, IEEE Transactions on Communications, 53, 5, 810-817 (2005) |
| [309] | Sarker, B. R.; Wilhelm, W. E.; Hogg, G. L.; Han, M.-H., Backtracking of jobs in one-dimensional machine location problems, European Journal of Operational Research, 85, 3, 593-609 (1995) · Zbl 0912.90181 |
| [310] | Sarker, B. R.; Wilhelm, W. E.; Hogg, G. L., One-dimensional machine location problems in a multi-product flowline with equidistant locations, European Journal of Operational Research, 105, 3, 401-426 (1998) · Zbl 0955.90067 |
| [311] | Scriabin, M.; Vergin, R. C., Comparison of computer algorithms and visual based methods for plant layout, Management Science, 22, 172-187 (1975) |
| [312] | Sergeev, S. I., Improved lower bounds for the quadratic assignment problem, Automation and Remote Control, 65, 11, 1733-1746 (2004) · Zbl 1074.90023 |
| [313] | Sherali, H. D.; Adams, W. P., Reformulation-linearization techniques for discrete optimization problems, (Pardalos, P. M.; Du, D.-Z., Handbook of Combinatorial Optimization (1999), Kluwer Academic Publishers), 479-532 · Zbl 0934.90056 |
| [314] | Sherali, H. D.; Adams, W. P., A Reformulation-linearization Technique for Solving Discrete and Continuous Nonconvex Optimization Problems (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands · Zbl 0926.90078 |
| [315] | Shin, I.; Niitsuma, H., Lambda-opt neural approaches to quadratic assignment problems, Neural Computation, 12, 2209-2225 (2000) |
| [316] | Simeone, B., An asymptotically exact polynomial time algorithm for equipartition problems, Discrete Applied Mathematics, 14, 283-293 (1986) · Zbl 0593.90053 |
| [317] | Simeone, B., Topological network synthesis, (Simeone, B., Combinatorial Optimization. Combinatorial Optimization, Lecture Notes in Mathematics, vol. 1403 (1986), Springer-Verlag), 282-303 · Zbl 0678.90087 |
| [318] | Siu, F.; Chang, R. K.C., Effectiveness of optimal node assignments in wavelength division multiplexing networks with fixed regular virtual topologies, Computer Networks, 38, 1, 61-74 (2002) |
| [319] | Skorin-Kapov, J., Tabu search applied to the quadratic assignment problem, ORSA Journal on Computing, 2, 1, 33-45 (1990) · Zbl 0752.90054 |
| [320] | Skorin-Kapov, J., Extensions of a tabu search adaptation to the quadratic assignment problem, Journal of Computers and Operations Research, 21, 8, 855-865 (1994) · Zbl 0812.90098 |
| [321] | Smith, J. M.; Li, W. J., Quadratic assignment problems and M/G/C/C state dependent network flows, Journal of Combinatorial Optimization, 5, 4, 421-443 (2001) · Zbl 1135.90311 |
| [322] | Solimanpur, M.; Vrat, P.; Shankar, R., Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing, European Journal of Operational Research, 157, 3, 592-606 (2004) · Zbl 1067.90035 |
| [323] | Spiliopoulos, K.; Sofianopoulou, S., An optimal tree search method for the manufacturing systems cell formation problem, European Journal of Operational Research, 105, 3, 537-551 (1998) · Zbl 0960.90506 |
| [324] | Steinberg, L., The backboard wiring problem: A placement algorithm, SIAM Review, 3, 37-50 (1961) · Zbl 0097.14703 |
| [325] | Stützle, T., in press. Iterated local search for the quadratic assignment problem. European Journal of Operational Research, doi:10.1016/j.ejor.2005.01.066; Stützle, T., in press. Iterated local search for the quadratic assignment problem. European Journal of Operational Research, doi:10.1016/j.ejor.2005.01.066 · Zbl 1103.90066 |
| [326] | Stützle, T.; Dorigo, M., ACO algorithms for the quadratic assignment problem, (Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw-Hill), 33-55 |
| [327] | Stützle, T.; Fernandes, S., New benchmark instances for the QAP and the experimental analysis of algorithms, Lecture Notes in Computer Science, 3004, 199-209 (2004) · Zbl 1177.90424 |
| [328] | Stützle, T.; Holger, H., MAX-MIN ant system, Future Generation Computer Systems, 16, 8, 889-914 (2000) |
| [329] | Sylla, C.; Babu, A. J.G., Methodology for an orderly quadratic assignment problem, Computers and Industrial Engineering, 13, 1-4, 281-284 (1987) |
| [330] | Taillard, E., Robust taboo search for the quadratic assignment problem, Parallel Computing, 17, 443-455 (1991) |
| [331] | Taillard, E., Comparison of iterative searches for the quadratic assignment problem, Location Science, 3, 2, 87-105 (1995) · Zbl 0916.90235 |
| [332] | Taillard, E., Gambardella, L., 1999. Adaptive memories for the quadratic assignment problem. Technical Report I-87-97, IDSIA, Lugano.; Taillard, E., Gambardella, L., 1999. Adaptive memories for the quadratic assignment problem. Technical Report I-87-97, IDSIA, Lugano. · Zbl 1054.90621 |
| [333] | Taillard, E.; Gambardella, L. M.; Gendreau, M.; Potvin, J. Y., Adaptive memory programming: A unified view of metaheuristics, European Journal of Operational Research, 135, 1, 1-16 (2001) · Zbl 1051.90032 |
| [334] | Takagi, M., Optimization of placement by candidate sieving, IEEE Transactions on Electronics Packaging Manufacturing, 24, 3, 178-187 (2001) |
| [335] | Talbi, E.-G.; Hafidi, Z.; Kebbal, D.; Geib, J.-M., A fault-tolerant parallel heuristic for assignment problems, Future Generation Computer Systems, 14, 5-6, 425-438 (1998) |
| [336] | Talbi, E.-G.; Hafidi, Z.; Geib, J.-M., A parallel adaptive tabu search approach, Parallel Computing, 24, 14, 2003-2019 (1998) · Zbl 0908.68044 |
| [337] | Talbi, E.-G.; Roux, O.; Fonlupt, C.; Robillard, D., Parallel ant colonies for the quadratic assignment problem, Future Generation Computer Systems, 17, 4, 441-449 (2001) · Zbl 1016.68170 |
| [338] | Talbot, N.L.C., Cawley, G.C., 1996. A quadratic index assignment algorithm for vector quantization over noisy transmission channels. In: Proceedings of the Institute of Acoustics Autumn Conference (Speech and Hearing 96) 18, 195-199.; Talbot, N.L.C., Cawley, G.C., 1996. A quadratic index assignment algorithm for vector quantization over noisy transmission channels. In: Proceedings of the Institute of Acoustics Autumn Conference (Speech and Hearing 96) 18, 195-199. |
| [339] | Tansel, B. C.; Bilen, C., Move based heuristics for the unidirectional loop network layout problem, European Journal of Operational Research, 108, 1, 36-48 (1998) · Zbl 0943.90024 |
| [340] | Tate, D. E.; Smith, A. E., A genetic approach to the quadratic assignment problem, Computers and Operations Research, 22, 73-83 (1995) · Zbl 0812.90099 |
| [341] | Tavakkoli-Moghaddain, R.; Shayan, E., Facilities layout design by genetic algorithms, Computers and Industrial Engineering, 35, 3-4, 527-530 (1998) |
| [342] | Tian, P.; Wang, H. C.; Zhang, D. M., Simulated annealing for the quadratic assignment problem: A further study, Computers and Industrial Engineering, 31, 3-4, 925-928 (1996) |
| [343] | Tian, P.; Ma, J.; Zhang, D.-M., Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: An investigation of generation mechanism, European Journal of Operational Research, 118, 1, 81-94 (1999) · Zbl 0945.90051 |
| [344] | Torki, A.; Yajima, Y.; Enkawa, T., A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem, European Journal of Operational Research, 94, 2, 384-391 (1996) · Zbl 0953.90544 |
| [345] | Tsuchiya, K.; Bharitkar, S.; Takefuji, Y., A neural network approach to facility layout problems, European Journal of Operational Research, 89, 3, 556-563 (1996) · Zbl 0915.90179 |
| [346] | Tsuchiya, K.; Nishiyama, T.; Tsujita, K., A deterministic annealing algorithm for a combinatorial optimization problem using replicator equations, Physica D: Nonlinear Phenomena, 149, 3, 161-173 (2001) · Zbl 1049.90081 |
| [347] | Urban, T. L., Solution procedures for the dynamic facility layout problem, Annals of Operations Research, 76, 323-342 (1998) · Zbl 0895.90162 |
| [348] | Urban, T. L.; Chiang, W. C.; Russell, R. A., The integrated machine allocation and layout problem, International Journal of Production Research, 38, 13, 2911-2930 (2000) |
| [349] | Uwate, Y.; Nishio, Y.; Ushida, A., Markov chain modeling of intermittency chaos and its application to Hopfield NN, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E87A, 4, 774-779 (2004) |
| [350] | Vlach, M., A branch-and-bound method for the three-index assignment problem, Ekonomicko-Matematicky Obzor, 3, 181-191 (1967) |
| [351] | Wang, R. L.; Okazaki, K., Solving facility layout problem using an improved genetic algorithm, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E88A, 2, 606-610 (2005) |
| [352] | Wang, S. J.; Sarker, B. R., Locating cells with bottleneck machines in cellular manufacturing systems, International Journal of Production Research, 40, 2, 403-424 (2002) · Zbl 1060.90623 |
| [353] | Wess, B.; Zeitlhofer, T., On the phase coupling problem between data memory layout generation and address pointer assignment, Lecture Notes in Computer Science, 3199, 152-166 (2004) |
| [354] | West, D. H., Algorithm 608: Approximate solution of the quadratic assignment problem, ACM Transactions on Mathematical Software, 9, 461-466 (1983) |
| [355] | White, D. J., A parametric-based heuristic program for the quadratic assignment problem, Naval Research Logistics, 40, 4, 553-568 (1993) · Zbl 0774.90058 |
| [356] | White, D. J., Strengthening Gilmore’s bound for the quadratic assignment problem, European Journal of Operational Research, 77, 1, 126-140 (1994) · Zbl 0810.90095 |
| [357] | White, D. J., The use of specially structured models for obtaining bounds in the quadratic assignment problem, Journal of the Operational Research Society, 45, 4, 451-462 (1994) · Zbl 0807.90077 |
| [358] | White, D. J., Some concave-convex representations of the quadratic assignment problem, European Journal of Operational Research, 80, 2, 418-424 (1995) |
| [359] | White, D. J., A Lagrangean relaxation approach for a turbine design quadratic assignment problem, Journal of the Operational Research Society, 47, 6, 766-775 (1996) · Zbl 0855.90089 |
| [360] | Whitney, H., Congruent graphs and the connectivity of graphs, American Journal of Mathematics, 54, 150-168 (1932) · JFM 58.0609.01 |
| [361] | Wilhelm, M. R.; Ward, T. L., Solving quadratic assignment problems by simulated annealing, IEEE Transactions, 19, 107-119 (1987) |
| [362] | Wolkowicz, H., (Wolkowicz, H.; Saigal, R.; Vandenberghe, L., Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, International Series in Operations Research, vol. 27 (2000), Kluwer) · Zbl 0962.90001 |
| [363] | Wolkowicz, H., Semidefinite programming approaches to the quadratic assignment problem, (Pardalos, P. M.; Pitsoulis, L., Nonlinear Assignment Problems: Algorithms and Applications. Nonlinear Assignment Problems: Algorithms and Applications, Combinatorial Optimization Series, vol. 7 (2000), Kluwer Academic Publishers), 143-174 · Zbl 1038.90045 |
| [364] | Yamada, S., A new formulation of the quadratic assignment problem on \(r\)-dimensional grid, IEEE Transactions on Circuits and Systems I-Fundamental Theory and Applications, 39, 10, 791-797 (1992) · Zbl 0825.90714 |
| [365] | Ying, K. C.; Liao, C. J., An ant colony system for permutation flow-shop sequencing, Computers and Operations Research, 31, 5, 791-801 (2004) · Zbl 1048.90113 |
| [366] | Yip, P. P.C.; Pao, Y. H., A guided evolutionary simulated annealing approach to the quadratic assignment problem, IEEE Transactions on Systems Man and Cybernetics, 24, 9, 1383-1387 (1994) |
| [367] | Youssef, H.; Sait, S. M.; Ali, H., Fuzzy simulated evolution algorithm for VLSI cell placement, Computers and Industrial Engineering, 44, 2, 227-247 (2003) |
| [368] | Yu, J.; Sarker, B. R., Directional decomposition heuristic for a linear machine-cell location problem, European Journal of Operational Research, 149, 1, 142-184 (2003) · Zbl 1036.90048 |
| [369] | Zhao, Q.; Karisch, S. E.; Rendl, F.; Wolkowicz, H., Semidefinite programming relaxations for the quadratic assignment problem, Journal of Combinatorial Optimization, 2, 71-109 (1998) · Zbl 0904.90145 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
