Skip to Main content Skip to Navigation
Journal articles

Tabu search: global intensification using dynamic programming

Abstract : Tabu search has proven highly successful in solving hard combinatorial optimization problems. In this paper, we propose a hybrid method that combines adaptive memory, sparse dynamic programming, and reduction techniques to reduce and explore the search space. Our approach starts with a bi-partition of the variables, involving a small core problem, which never exceeds 15 variables, solved using the "forward" phase of the dynamic programming procedure. Then, the remaining subspace is explored using tabu search, and each partial solution is completed with the information stored during the forward phase of dynamic programming. Our approach can be seen as a global intensification mechanism, since at each iteration, the move evaluations involve solving a reduced problem implicitly. The proposed specialized tabu search approach was tested in the context of the multidimensional 0-1 knapsack problem. Our approach was compared to ILOG's commercial product CPLEX and to the corresponding "pure" tabu search (i.e., without a core problem) for various sets of test problems available in ORlibraries. The results are encouraging. In particular, this enhances the robustness of the approach, given that it performs better than the corresponding pure tabu search most of the time. Moreover, our approach compares well with CPLEX when the number of variables is large; it is able to provide elite feasible solutions in a very reasonable amount of computational time.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03723758
Contributor : Christophe Wilbaut Connect in order to contact the contributor
Submitted on : Friday, July 15, 2022 - 10:48:07 AM
Last modification on : Monday, September 5, 2022 - 10:37:33 AM

File

Wilbaut et al. - Tabu search g...
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-03723758, version 1

Collections

Citation

Christophe Wilbaut, Saïd Hanafi, Arnaud Fréville, Stefan Balev. Tabu search: global intensification using dynamic programming. Control and Cybernetics, Polish Academy of Sciences, 2006, 35 (3), pp.579-598. ⟨hal-03723758⟩

Share

Metrics

Record views

5

Files downloads

1