Article ID: | iaor20053279 |
Country: | France |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 251 |
End Page Number: | 267 |
Publication Date: | Apr 2001 |
Journal: | RAIRO Operations Research |
Authors: | Frville Arnaud, Hanafi Sad |
Keywords: | optimization |
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 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.