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.

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},
     pages = {251--267},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     mrnumber = {1868871},
     zbl = {1014.90079},
     language = {en},
     url = {http://archive.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://archive.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://archive.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://archive.numdam.org/item/RO_2001__35_2_251_0/

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

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

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

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

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

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

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

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

[9] F. Glover and G.A. Kochenberger, 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] F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers (1997). | MR | Zbl

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

[12] S. Hanafi and A. Fréville, An efficient Tabu Search Approach for the 0-1 Multidimensional Knapsack Problem. European J. Oper. Res. 106 (1998) 659-675. | Zbl

[13] S. Hanafi, A. Fréville and A. El Abdellaoui, 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] R. Hübscher and F. Glover, Applying Tabu Search with influential diversification to multiprocessor scheduling. Comput. Oper. Res. 13 (1994) 877-884. | Zbl

[15] A. Lokketangen and F. Glover, 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] J. Lorie and L.J. Savage, Three Problems in Capital Rationing. J. Bus. 28 (1955) 229-239.

[17] K. Nonobe and T. Ibaraki, 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