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

Saïd Hanafi; Arnaud Fréville

RAIRO - Operations Research (2010)

  • 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 35.2 (2010): 251-267. <http://eudml.org/doc/197806>.

@article{Hanafi2010,
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},
keywords = {reverse elimination method; dynamic management; the tabu list},
language = {eng},
month = {3},
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/197806},
volume = {35},
year = {2010},
}

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
DA - 2010/3//
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/197806
ER -

References

top
  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.  
  2. R. Battiti and G. Tecchiolli, The Reactive Tabu Search. ORSA J. Comput.6 (1994) 126-140.  
  3. F. Dammeyer and S. Voss, Dynamic Tabu List Management using the Reverse Elimination Method. Ann. Oper. Res.41 (1993) 31-46.  
  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.  
  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.  
  7. F. Glover, Tabu Search, Part 2. ORSA J. Comput.2 (1990) 4-32.  
  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. 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.  
  10. F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers (1997).  
  11. S. Hanafi, On the Convergence of Tabu Search. J. Heuristics (to appear).  
  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.  
  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.  
  14. R. Hübscher and F. Glover, Applying Tabu Search with influential diversification to multiprocessor scheduling. Comput. Oper. Res.13 (1994) 877-884.  
  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.  
  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.  

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.