Extension of reverse elimination method through a dynamic management of the tabu list

Hanafi, Saïd  ; Fréville, Arnaud 

RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 251-267

Résumé

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.