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.

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.

[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

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

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

[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

[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

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

[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

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

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

[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

[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

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

[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

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