Extension of Reverse Elimination Method Through a Dynamic Management of the Tabu List

¹ LAMIH, UMR 8530 du CNRS, ROI – Groupe Recherche Opérationnelle et Informatique, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont Houy, 59313 Valenciennes Cedex, France; hanafi@univ-valenciennes.fr.
² LAMIH, UMR 8530 du CNRS, ROI – Groupe Recherche Opérationnelle et Informatique, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont Houy, 59313 Valenciennes Cedex, France; freville@univ-valenciennes.fr.

Received: May 1999

Abstract

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.