Skip to Main content Skip to Navigation
Journal articles

Scatter Search for the 0–1 Multidimensional Knapsack Problem

Abstract : The evolutionary metaheuristic called scatter search has been applied successfully to optimization problems for several years. In this paper, we apply the scatter search technique to the well-known 0-1 multidimensional knapsack problem. We propose a new relaxation-based diversification generator, which produces an initial population with elite solutions. The computational results obtained for a set of classic and correlated instances clearly show that (1) this generator can also be used as a heuristic for solving the multidimensional knapsack problem; (2) using the population produced by our generator as a starting point for the scatter search algorithm leads to better performance. We also enhance the scatter search algorithm by integrating memory and by using adapted intensification phases. Overall, the results are interesting and competitive compared to other population-based algorithms, such as genetic algorithms.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03723754
Contributor : Christophe Wilbaut Connect in order to contact the contributor
Submitted on : Friday, July 15, 2022 - 10:46:08 AM
Last modification on : Thursday, July 21, 2022 - 3:54:55 AM

File

Hanafi et Wilbaut - 2008 - Sca...
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Said Hanafi, Christophe Wilbaut. Scatter Search for the 0–1 Multidimensional Knapsack Problem. Journal of Mathematical Modelling and Algorithms, Springer Verlag, 2008, 7, pp.143 - 159. ⟨10.1007/s10852-008-9078-9⟩. ⟨hal-03723754⟩

Share

Metrics

Record views

2

Files downloads

3