EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO Oper. Res.
Volume 35, Number 2, April-June 2001
Page(s) 251 - 267
DOI 10.1051/ro:2001113

DOI: 10.1051/ro:2001113


RAIRO Oper. Res. 35 (2001) 251-267

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

Saïd Hanafi1 and Arnaud Fréville1

1  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) (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.



© EDP Sciences 2001


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.