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},
zbl = {1014.90079},
mrnumber = {1868871},
language = {en},
url = {http://www.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
DA  - 2001///
SP  - 251
EP  - 267
VL  - 35
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_2001__35_2_251_0/
UR  - https://zbmath.org/?q=an%3A1014.90079
UR  - https://www.ams.org/mathscinet-getitem?mr=1868871
LA  - en
ID  - RO_2001__35_2_251_0
ER  - 
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://www.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 0798.90105

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

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

[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 0579.90066

[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 0753.90054

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

[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 0877.90055

[10] F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers (1997). | MR 1665424 | Zbl 0930.90083

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

[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 0991.90089

[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 0877.90056

[14] R. Hübscher and F. Glover, Applying Tabu Search with influential diversification to multiprocessor scheduling. Comput. Oper. Res. 13 (1994) 877-884. | Zbl 0814.90048

[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 0877.90058

[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 1602613 | Zbl 0991.90102