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- method proposed by Glover (1990) where is an integer parameter which controls the number of tabu attributes. A suitable adjustment of this parameter 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 , 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},
pages = {251--267},
publisher = {EDP-Sciences},
volume = {35},
number = {2},
year = {2001},
mrnumber = {1868871},
zbl = {1014.90079},
language = {en},
url = {http://www.numdam.org/item/RO_2001__35_2_251_0/}
}
TY - JOUR AU - Hanafi, Saïd AU - Fréville, Arnaud TI - Extension of reverse elimination method through a dynamic management of the tabu list JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2001 SP - 251 EP - 267 VL - 35 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/item/RO_2001__35_2_251_0/ LA - en ID - RO_2001__35_2_251_0 ER -
%0 Journal Article %A Hanafi, Saïd %A Fréville, Arnaud %T Extension of reverse elimination method through a dynamic management of the tabu list %J RAIRO - Operations Research - Recherche Opérationnelle %D 2001 %P 251-267 %V 35 %N 2 %I EDP-Sciences %U http://www.numdam.org/item/RO_2001__35_2_251_0/ %G en %F 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, Tome 35 (2001) no. 2, pp. 251-267. http://www.numdam.org/item/RO_2001__35_2_251_0/
[1] and, Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic. ORSA J. Comput. 6 (1994) 82-93. | Zbl
[2] and, The Reactive Tabu Search. ORSA J. Comput. 6 (1994) 126-140. | Zbl
[3] and, Dynamic Tabu List Management using the Reverse Elimination Method. Ann. Oper. Res. 41 (1993) 31-46. | Zbl
[4] and, Heuristics and Reduction Methods for Multiple Constraints 0-1 Linear Programming Problems. European J. Oper. Res. 24 (1986) 206-215. | Zbl
[5] and, Hard 0-1 Multiknapsack Test Problems for Size Reduction Methods. Investigacion Oper. 1 (1990) 251-270.
[6] , Tabu Search, Part 1. ORSA J. Comput. 1 (1989) 190-206. | Zbl
[7] , Tabu Search, Part 2. ORSA J. Comput. 2 (1990) 4-32. | Zbl
[8] and, Tabu Search and Finite Convergence 25-28 October 1998, USA.
[9] and, 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
[10] and, Tabu Search. Kluwer Academic Publishers (1997). | MR | Zbl
[11] , On the Convergence of Tabu Search. J. Heuristics (to appear). | Zbl
[12] and, An efficient Tabu Search Approach for the 0-1 Multidimensional Knapsack Problem. European J. Oper. Res. 106 (1998) 659-675. | Zbl
[13] , and, 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
[14] and, Applying Tabu Search with influential diversification to multiprocessor scheduling. Comput. Oper. Res. 13 (1994) 877-884. | Zbl
[15] and, 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
[16] and, Three Problems in Capital Rationing. J. Bus. 28 (1955) 229-239.
[17] and, A Tabu Search Approach to the CSP (Constraint Satisfaction Problem) as a General Problem Solver. European J. Oper. Res. 106 (1998) 599-623. | MR | Zbl
