Extension of reverse elimination method through a dynamic management of the tabu list
RAIRO - Operations Research - Recherche Opérationnelle, Volume 35 (2001) no. 2, p. 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},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     pages = {251-267},
     zbl = {1014.90079},
     mrnumber = {1868871},
     language = {en},
     url = {http://www.numdam.org/item/RO_2001__35_2_251_0}
}
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, Volume 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