Glover, Fred; Hanafi, Saïd Tabu search and finite convergence. (English) Zbl 0994.90116 Discrete Appl. Math. 119, No. 1-2, 3-36 (2002). Authors’ summary: We establish finite convergence for some tabu search algorithms based on recency memory or frequency memory, distinguishing between symmetric and asymmetric neighborhood structures. These are the first demonstrations of explicit bounds provided by such forms of memory, and their finiteness suggests an important distinction between these ideas and those underlying certain “probabilistic” procedures such as annealing. We also show how an associated reverse elimination memory can be used to create a new type of tree search. Finally, we give designs for more efficient forms of convergent tabu search. Reviewer: S.Gal (Haifa) Cited in 15 Documents MSC: 90C27 Combinatorial optimization Keywords:tabu search; annealing; recency memory; tree search Software:Tabu search PDFBibTeX XMLCite \textit{F. Glover} and \textit{S. Hanafi}, Discrete Appl. Math. 119, No. 1--2, 3--36 (2002; Zbl 0994.90116) Full Text: DOI References: [1] Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht [2] Glover, F., Tabu search, Part 2, ORSA J. Comput., 2, 4-32 (1990) · Zbl 0771.90084 [3] S. Hanafi, On the convergence of tabu search, Working paper, University of Valenciennes, France, 1998, J. Heuristics, to appear.; S. Hanafi, On the convergence of tabu search, Working paper, University of Valenciennes, France, 1998, J. Heuristics, to appear. [4] Dammeyer, F.; Voss, S., Dynamic tabu list management using the reverse elimination method, Ann. Oper. Res., 41, 31-46 (1993) · Zbl 0775.90290 [5] S. Hanafi, A. Fréville, Extension of reverse elimination method through a dynamic management of the tabu list, R.A.I.R.O., to appear.; S. Hanafi, A. Fréville, Extension of reverse elimination method through a dynamic management of the tabu list, R.A.I.R.O., to appear. · Zbl 1014.90079 [6] D. Avis, K. Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Proceedings of the Seventh ACM Symposium on Computational Geometry, North Conway, New Hampshire, 1991a, pp. 98-104.; D. Avis, K. Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Proceedings of the Seventh ACM Symposium on Computational Geometry, North Conway, New Hampshire, 1991a, pp. 98-104. · Zbl 0752.68082 [7] Avis, D.; Fukuda, K., A basis enumeration algorithm for linear systems with geometric applications, Appl. Math. Lett., 5, 39-42 (1991) · Zbl 0736.90059 [8] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Appl. Math., 6, 21-46 (1996) · Zbl 0854.68070 [9] Tarry, G., Le problème des labyrinthes, Nouv. Ann. Math., 14, 3, 187-190 (1895) · JFM 26.0645.02 [10] G.L. Thompson, The Tarry Traverse, Class notes, Carnegie-Mellon University, Graduate School of Industrial Administration, 1998.; G.L. Thompson, The Tarry Traverse, Class notes, Carnegie-Mellon University, Graduate School of Industrial Administration, 1998. [11] A. Charnes, W.W. Cooper, Mathematical Models and Industrial Applications of Linear Programming, Vol. I, Wiley, New York and London, 1961, pp. 438-444.; A. Charnes, W.W. Cooper, Mathematical Models and Industrial Applications of Linear Programming, Vol. I, Wiley, New York and London, 1961, pp. 438-444. [12] F. Glover, S. Hanafi, Composite tree searches for global optimization, Research Report, Graduate School of Business and Administration, University of Colorado, Boulder, 1998.; F. Glover, S. Hanafi, Composite tree searches for global optimization, Research Report, Graduate School of Business and Administration, University of Colorado, Boulder, 1998. 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.