RedInv-SA : a simulated annealing for the quadratic assignment problem

 Access to full text

 Full (PDF)

1. [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. 
2. [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. 
3. [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. 
4. [Be68] C. BERGE, Principes de Combinatoire, Dunod, Paris, 1968. Zbl0227.05001MR237346
5. [Be73] C. BERGE, Graphes et Hypergraphes, 2e éd., Dunod, Paris, 1973. Zbl0213.25702MR357171
6. [BR84] R. E. BURKARD and F. RENDL, A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization Problems, EJOR, 1984, 17, p. 169-174. Zbl0541.90070
7. [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. Zbl0729.90993
8. [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. Zbl0817.90053MR1290348
9. [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. Zbl0817.90057MR1290356
10. [BS78] R. E. BURKARD and R. H. STRATMAN, Numerical Investigations on Quadratic Assignment Problem, NRLQ, 1978, 25, p. 129-140. Zbl0391.90066
11. [CB89] N. CHRISTOFIDES and E. BENAVENT, An Exact Algorithm for the Quadratic Assignment Problem on a Tree, Opns. Res., 1989, 37, p. 760-768. Zbl0682.90064MR1021417
12. [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. 
13. [Con90] D. CONNOLLY, An Improved Annealing Scheme for the QAP, EJOR, 1990, 46, p. 93-100. Zbl0715.90079MR1053816
14. [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. Zbl0815.90106MR1299493
15. [Eg90] R. W. EGLESE, Simulated Annealing: a Tool for Operations Research, EJOR, 1990, 46, p. 271-281. Zbl0699.90080MR1064622
16. [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. Zbl0691.90088MR1032172
17. [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. Zbl0817.90056MR1290352
18. [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. 
19. [HLP52] G. H. HARDY, J. E. LITTLEWOOD and G. PÓLYA, Inequalities, Cambridge University Press, Cambridge, 1934. Zbl0047.05302
20. [KB57] T. C. KOOPMANS and M. BECKMANN, Assignment Problems and the Location of Economic Activities, Econometrica, 1957, 25, p. 53-76. Zbl0098.12203MR89106
21. [LP92] Y. LI and P. M. PARDALOS, Generating Quadratic Assignment Test Problems with Known Optimal Permutations, Comput. Optim. Appl., 1992, 1, p. 163-184. Zbl0773.90083MR1226334
22. [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. Zbl0817.90057MR1290356
23. [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. Zbl0937.68511MR1243756
24. [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. Zbl0816.90097MR1381239
25. [MM95] J. MILLIS and V. MAGIROU, A Lagrangean Relaxation Algorithm for Sparse Quadratic Assignment Problems, Oper. Res. Lett., 1995, 17, p. 69-76. Zbl0836.90128MR1336783
26. [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. Zbl0819.90054MR1308884
27. [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. Zbl0817.90058MR1290357
28. [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. 
29. [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. Zbl0658.90076MR976831
30. [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. Zbl0873.90072MR1430568
31. [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. Zbl0817.90059MR1290345
32. [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. Zbl0797.00027MR1290344
33. [Que94] T. M. QUERIDO, Simulated Annealing in the Inversion Graph of the Quadratic Assignment Problem (in Portuguese), D. Sc. Thesis, COPPE/UFRJ, 1994. 
34. [Re85] F. RENDL, Ranking Scalar Products to Improve Bounds for the Quadratic Assignment Problem, EJOR, 1985, 20, p. 363-372. Zbl0565.90055MR800911
35. [Ro87] C. ROUCAIROL, A Parallel Branch-and-Bound Algorithm for the Quadratic Assignment Problem, Discr. Appl. Maths., 1987, 18, p. 211-225. Zbl0632.90047MR911298
36. [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. Zbl0871.90071MR1390526
37. [SK89] J. SKORIN-KAPOV, Tabu Search Applied to the Quadratic Assignment Problem, ORSA J. Comp., 1989, 2, p. 33-45. Zbl0752.90054
38. [SK94] J. SKORIN-KAPOV, Extensions of a Tabu Search Adaptation to the Quadratic Assignment Problem, Comput Opns. Res., 1994, 21, p. 855-865. Zbl0812.90098MR1288637
39. [Ta91] E. TAILLARD, Robust Taboo Search for the Quadratic Assignment Problem, Parallel Comput., 1991, 17, p. 443-455. MR1123015
40. [Wh93] D. J. WHITE, A Parametric-Based Heuristic Program for the Quadratic Assignment Problem, NRL, 1993, 40, p. 553-568. Zbl0774.90058MR1214535
41. [Wi58] R. J. WIMMERT, A Mathematical Model of Equipment Location, J.J.E, 1958, 9, p. 498-505. 
42. [WW87] M. WILHELM and T. L. WARD, Solving Quadratic Assignment Problems by "Simulated Annealing", IEEE Trans., 1987, 19, p. 107-119.