The Reverse Elimination Method (REM) is a dynamic strategy for managing the tabu list. It is based on logical interdependencies between the solutions encountered during recent iterations of the search. REM provides both a necessary and sufficient condition to prevent cycling. The purpose of this paper is first to incorporate in REM a chronological order rule when cycling is unavoidable, thereby assuring the finite convergence of Tabu Search. Secondly, we correct a generalization of REM, the so-called REM-$t$ method proposed by Glover (1990) where $t$ is an integer parameter which controls the number of tabu attributes. A suitable adjustment of this parameter $t$ can be designed in order to create a balance between diversification and intensification. In this paper, new dynamic rules for controlling the adjustment of the parameter $t$, are proposed. Finally, to illustrate the differences between the variants proposed for managing the tabu list, we test some of them on the 0-1 multidimensional knapsack problem.

@article{RO_2001__35_2_251_0, author = {Hanafi, Sa\"\i d and Fr\'eville, Arnaud}, title = {Extension of reverse elimination method through a dynamic management of the tabu list}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, publisher = {EDP-Sciences}, volume = {35}, number = {2}, year = {2001}, pages = {251-267}, zbl = {1014.90079}, mrnumber = {1868871}, language = {en}, url = {http://www.numdam.org/item/RO_2001__35_2_251_0} }

Hanafi, Saïd; Fréville, Arnaud. Extension of reverse elimination method through a dynamic management of the tabu list. RAIRO - Operations Research - Recherche Opérationnelle, Volume 35 (2001) no. 2, pp. 251-267. http://www.numdam.org/item/RO_2001__35_2_251_0/

[1] Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic. ORSA J. Comput. 6 (1994) 82-93. | Zbl 0798.90105

and ,[2] The Reactive Tabu Search. ORSA J. Comput. 6 (1994) 126-140. | Zbl 0807.90094

and ,[3] Dynamic Tabu List Management using the Reverse Elimination Method. Ann. Oper. Res. 41 (1993) 31-46. | Zbl 0775.90290

and ,[4] Heuristics and Reduction Methods for Multiple Constraints 0-1 Linear Programming Problems. European J. Oper. Res. 24 (1986) 206-215. | Zbl 0579.90066

and ,[5] Hard 0-1 Multiknapsack Test Problems for Size Reduction Methods. Investigacion Oper. 1 (1990) 251-270.

and ,[6] Tabu Search, Part 1. ORSA J. Comput. 1 (1989) 190-206. | Zbl 0753.90054

,[7] Tabu Search, Part 2. ORSA J. Comput. 2 (1990) 4-32. | Zbl 0771.90084

,[8] Tabu Search and Finite Convergence 25-28 October 1998, USA.

and ,[9] Critical Events Tabu Search for Multidimensional Knapsack Problems, in Metaheuristics: Theory and Applications, edited by I.H. Osman and J.P. Kelly. Kluwer (1996) 407-428. | Zbl 0877.90055

and ,[10] Tabu Search. Kluwer Academic Publishers (1997). | MR 1665424 | Zbl 0930.90083

and ,[11] On the Convergence of Tabu Search. J. Heuristics (to appear). | Zbl 0967.90054

,[12] An efficient Tabu Search Approach for the 0-1 Multidimensional Knapsack Problem. European J. Oper. Res. 106 (1998) 659-675. | Zbl 0991.90089

and ,[13] Comparison of Heuristics for the 0-1 Multi-dimensional Knapsack Problem, in Metaheuristics: Theory and Applications, edited by I.H. Osman and J.P. Kelly. Kluwer (1996) 449-466. | Zbl 0877.90056

, and ,[14] Applying Tabu Search with influential diversification to multiprocessor scheduling. Comput. Oper. Res. 13 (1994) 877-884. | Zbl 0814.90048

and ,[15] Probabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems, in Metaheuristics: Theory and Applications, edited by I.H. Osman and J.P. Kelly. Kluwer (1996) 467-488. | Zbl 0877.90058

and ,[16] Three Problems in Capital Rationing. J. Bus. 28 (1955) 229-239.

and ,[17] A Tabu Search Approach to the CSP (Constraint Satisfaction Problem) as a General Problem Solver. European J. Oper. Res. 106 (1998) 599-623. | MR 1602613 | Zbl 0991.90102

and ,