RedInv-SA : a simulated annealing for the quadratic assignment problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 3, pp. 249-273.
@article{RO_1999__33_3_249_0,
     author = {de Abreu, N. M. M. and Querido, T. M. and Boaventura-Netto, P. O.},
     title = {RedInv-SA : a simulated annealing for the quadratic assignment problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {249--273},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {3},
     year = {1999},
     mrnumber = {1721636},
     zbl = {1016.90037},
     language = {en},
     url = {http://archive.numdam.org/item/RO_1999__33_3_249_0/}
}
TY  - JOUR
AU  - de Abreu, N. M. M.
AU  - Querido, T. M.
AU  - Boaventura-Netto, P. O.
TI  - RedInv-SA : a simulated annealing for the quadratic assignment problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1999
SP  - 249
EP  - 273
VL  - 33
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1999__33_3_249_0/
LA  - en
ID  - RO_1999__33_3_249_0
ER  - 
%0 Journal Article
%A de Abreu, N. M. M.
%A Querido, T. M.
%A Boaventura-Netto, P. O.
%T RedInv-SA : a simulated annealing for the quadratic assignment problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1999
%P 249-273
%V 33
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_1999__33_3_249_0/
%G en
%F RO_1999__33_3_249_0
de Abreu, N. M. M.; Querido, T. M.; Boaventura-Netto, P. O. RedInv-SA : a simulated annealing for the quadratic assignment problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 3, pp. 249-273. http://archive.numdam.org/item/RO_1999__33_3_249_0/

[Ab84] N. M. M. Abreu, An Algebraic and Combinatorial Study of the Quadratic Assignment Problem as Defined by Koopmans and Beckmann (in Portuguese), D.Sc. Thesis, COPPE/UFRJ, Rio de Janeiro, 1984.

[AB89] N. M. M. Abreu and P. O. Boaventura-Netto, The Quadratic Assignment Problem: Permutation Ordering and Inversions, AMSE Rev., 1989, 10, p. 21-52.

[AV95] N. M. M. Abreu and O. Vernet, Permutation Lattices and the Quadratic Assignment Problem, Tech. Rep. PEP/PO/8, COPPE/UFRJ, Rio de Janeiro, 1995.

[Be68] C. Berge, Principes de Combinatoire, Dunod, Paris, 1968. | MR | Zbl

[Be73] C. Berge, Graphes et Hypergraphes, 2e éd., Dunod, Paris, 1973. | MR | Zbl

[BR84] R. E. Burkard and F. Rendl, A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization Problems, EJOR, 1984, 17, p. 169-174. | Zbl

[BKR94] R. E. Burkard, S. E. Karisch and F. Rendl, QAPLIB - A Quadratic Assignment Problem Library, Rep. 287 CDLDO-41, Technische Universität, Graz, 1994. | Zbl

[BM93] T. N. Bui and B. R. Moon, A Genetic Algorithm for a Special Class of the Quadratic Assignment Problem, P. M. Pardalos, H. Wolkowicz, Ed., Quadratic Assignment and Related Problems, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, American Mathematical Society, Providence, 1994. | MR | Zbl

[LPR94] Y. Li, P. Pardalos and M. G. C. Resende, A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem, P. M. Pardalos, H. Wolkowicz, Ed., Quadratic Assignment and Related Problems, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, American Mathematical Society, Providence, 1994. | MR | Zbl

[BS78] R. E. Burkard and R. H. Stratman, Numerical Investigations on Quadratic Assignment Problem, NRLQ, 1978, 25, p. 129-140. | Zbl

[CB89] N. Christofides and E. Benavent, An Exact Algorithm for the Quadratic Assignment Problem on a Tree, Opns. Res., 1989, 37, p. 760-768. | MR | Zbl

[Con89] D. Connolly, Solution Techniques for the Quadratic Assignment Problem and the Development of a General Purpose Simulated Annealing Algorithm, Ph.D. Thesis, The London School of Economies and Political Science, London, 1989.

[Con90] D. Connolly, An Improved Annealing Scheme for the QAP, EJOR, 1990, 46, p. 93-100. | MR | Zbl

[CSK94] J. C Chakrapani and J. Skorin-Kapov, A Constructive Method for Improving Lower Bounds for a Class of Quadratic Assignment Problems, Opns. Res., 1994, 42, p. 837-845. | MR | Zbl

[Eg90] R. W. Eglese, Simulated Annealing: a Tool for Operations Research, EJOR, 1990, 46, p. 271-281. | MR | Zbl

[F190] M. M. Flood, Exact and Heuristic Algorithms for the Weighted Feedback Arc Set Problem: A Special Case of the Skew-Symrnetric Quadratic Assignment Problem, Networks, 1990, 20, p. 1-23. | MR | Zbl

[FF94] C. Fleurent and J. A. Ferland, Genetic Hybrids for the Quadratic Assignment Problem, P. M. Pardalos, H. Wolkowicz, Ed., Quadratic Assignment and Related Problems, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, American Mathematical Society, Providence, 1994. | MR | Zbl

[GP66] J. W. Gavett and N. V Plyter, The Optimal Assignment of Facilities to Locations by Branch-and-Bound, Opns. Res., 1966, 14, p. 210-232.

[HLP52] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1934. | Zbl

[KB57] T. C. Koopmans and M. Beckmann, Assignment Problems and the Location of Economic Activities, Econometrica, 1957, 25, p. 53-76. | MR | Zbl

[LP92] Y. Li and P. M. Pardalos, Generating Quadratic Assignment Test Problems with Known Optimal Permutations, Comput. Optim. Appl., 1992, 1, p. 163-184. | MR | Zbl

[LPR94] Y. Li, P. M. Pardalos and M. G. C. Resende, A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem, P. M. Pardalos, H.Wolkowicz, Ed., Quadratic Assignment and Related Problems, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, American Mathematical Society, Providence, 1994. | MR | Zbl

[MLP92] K. A. Murthy, Y. Li and P. M. Pardalos, A Local Search Algorithm for the Quadratic Assignment Problem, Informatica, 1992, 4, p. 524-538, 596, 604. | MR | Zbl

[MM92] J. Millis and V. Magirou, A Lagrangean Relaxation Algorithm for the Task and the Quadratic Assignment Problems, Helln Res. In Maths. and Informat. '92, Helln. Math. Soc, Athens, 1992, p. 267-279. | MR | Zbl

[MM95] J. Millis and V. Magirou, A Lagrangean Relaxation Algorithm for Sparse Quadratic Assignment Problems, Oper. Res. Lett., 1995, 17, p. 69-76. | MR | Zbl

[MR94a] T. Mautor and C. Roucairol, A New Exact Algorithm for the Solution of Quadratic Assignment Problems, Discr. Appl. Maths., 1994, 55, p. 281-293. | MR | Zbl

[MR94b] T. Mautor and C. Roucairol, Difficulties of Exact Methods for Solving the Quadratic Assignment Problem, P. M. Pardalos, H. Wolkowicz, Ed., Quadratic Assignment and Related Problems, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, American Mathematical Society, Providence, 1994. | MR | Zbl

[NVR68] C. E. Nugent, T. E. Vollmann and J. Ruml, An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Opns. Res. Qtrly., 1968, 16, p. 150-173.

[Pa88] G. S. Palubetskis, A Generator of Quadratic Assignment Test Problems with a Known Optimal Solution, Zh. Vychisl. Mat. I Mat Fiz, 1988, 28, p. 1740-1743. | MR | Zbl

[PRRL97] P. Pardalos, K. G. Ramakrishnan, M. G. C. Resende and Y. Li, Implementation of a Variance Reduction-Based Lowed Bound in a Branch-and-Bound Algorithm for the Quadratic Assignment Problem, SIAM J. Optim., 1997, 7, p. 280-294. | MR | Zbl

[PW94] P. M. Pardalos and H. Wolkowicz, The Quadratic Assignment Problem: A Survey of Recent Developments, P. M.Pardalos, H.Wolkowicz, Ed., Quadratic Assignment and Related Problems, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, American Mathematical Society, Providence, 1994. | MR | Zbl

[PW94ed] P. M. Pardalos and H. Wolkowicz, Quadratic Assignment and Related Problems, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, American Mathematical Society, Providence, 1994. | MR | Zbl

[Que94] T. M. Querido, Simulated Annealing in the Inversion Graph of the Quadratic Assignment Problem (in Portuguese), D. Sc. Thesis, COPPE/UFRJ, 1994.

[Re85] F. Rendl, Ranking Scalar Products to Improve Bounds for the Quadratic Assignment Problem, EJOR, 1985, 20, p. 363-372. | MR | Zbl

[Ro87] C. Roucairol, A Parallel Branch-and-Bound Algorithm for the Quadratic Assignment Problem, Discr. Appl. Maths., 1987, 18, p. 211-225. | MR | Zbl

[RRP96] K. G. Ramakrishnan, M. G. C. Resende and P. M. Pardalos, A Branch-and-Bound Algorithm for the Quadratic Assignment Problem Using a Lower Bound on Linear Programming, Nonconvex Optim. Appl., 1996, 7, p. 57-73. | MR | Zbl

[SK89] J. Skorin-Kapov, Tabu Search Applied to the Quadratic Assignment Problem, ORSA J. Comp., 1989, 2, p. 33-45. | Zbl

[SK94] J. Skorin-Kapov, Extensions of a Tabu Search Adaptation to the Quadratic Assignment Problem, Comput Opns. Res., 1994, 21, p. 855-865. | MR | Zbl

[Ta91] E. Taillard, Robust Taboo Search for the Quadratic Assignment Problem, Parallel Comput., 1991, 17, p. 443-455. | MR

[Wh93] D. J. White, A Parametric-Based Heuristic Program for the Quadratic Assignment Problem, NRL, 1993, 40, p. 553-568. | MR | Zbl

[Wi58] R. J. Wimmert, A Mathematical Model of Equipment Location, J.J.E, 1958, 9, p. 498-505.

[WW87] M. Wilhelm and T. L. Ward, Solving Quadratic Assignment Problems by "Simulated Annealing", IEEE Trans., 1987, 19, p. 107-119.