Extension of reverse elimination method through a dynamic management of the tabu list

Saïd Hanafi; Arnaud Fréville

RAIRO - Operations Research - Recherche Opérationnelle (2001)

  • Volume: 35, Issue: 2, page 251-267
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Hanafi, Saïd, and Fréville, Arnaud. "Extension of reverse elimination method through a dynamic management of the tabu list." RAIRO - Operations Research - Recherche Opérationnelle 35.2 (2001): 251-267. <http://eudml.org/doc/105245>.

@article{Hanafi2001,
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.},
author = {Hanafi, Saïd, Fréville, Arnaud},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {reverse elimination method; dynamic management; the tabu list},
language = {eng},
number = {2},
pages = {251-267},
publisher = {EDP-Sciences},
title = {Extension of reverse elimination method through a dynamic management of the tabu list},
url = {http://eudml.org/doc/105245},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 2
SP - 251
EP - 267
AB - 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.
LA - eng
KW - reverse elimination method; dynamic management; the tabu list
UR - http://eudml.org/doc/105245
ER -

References

top
  1. [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. Zbl0798.90105
  2. [2] R. Battiti and G. Tecchiolli, The Reactive Tabu Search. ORSA J. Comput. 6 (1994) 126-140. Zbl0807.90094
  3. [3] F. Dammeyer and S. Voss, Dynamic Tabu List Management using the Reverse Elimination Method. Ann. Oper. Res. 41 (1993) 31-46. Zbl0775.90290
  4. [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. Zbl0579.90066
  5. [5] A. Fréville and G. Plateau, Hard 0–1 Multiknapsack Test Problems for Size Reduction Methods. Investigacion Oper. 1 (1990) 251-270. 
  6. [6] F. Glover, Tabu Search, Part 1. ORSA J. Comput. 1 (1989) 190-206. Zbl0753.90054
  7. [7] F. Glover, Tabu Search, Part 2. ORSA J. Comput. 2 (1990) 4-32. Zbl0771.90084
  8. [8] F. Glover and S. Hanafi, Tabu Search and Finite Convergence, Working paper, LAMIH-UMR CNRS N ∘ 8530. University of Valenciennes, France, presented at INFORMS Meeting, 25-28 October 1998, USA. 
  9. [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. Zbl0877.90055
  10. [10] F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers (1997). Zbl0930.90083MR1665424
  11. [11] S. Hanafi, On the Convergence of Tabu Search. J. Heuristics (to appear). Zbl0967.90054
  12. [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. Zbl0991.90089
  13. [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. Zbl0877.90056
  14. [14] R. Hübscher and F. Glover, Applying Tabu Search with influential diversification to multiprocessor scheduling. Comput. Oper. Res. 13 (1994) 877-884. Zbl0814.90048
  15. [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. Zbl0877.90058
  16. [16] J. Lorie and L.J. Savage, Three Problems in Capital Rationing. J. Bus. 28 (1955) 229-239. 
  17. [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. Zbl0991.90102MR1602613

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.