Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

An iterative algorithm for the Max-Min knapsack problem with multiple scenarios

Abstract : In this paper, we propose to solve the max-min knapsack problem with multiple scenarios by using an iterative algorithm that uses three main phases: (1) construction phase, (2) improvement phase, and (3) destroying/repairing phase. The first phase yields a (starting) pool of elite solutions for the problem by applying a greedy randomized search. The second phase tries to improve each solution at hand by using an intensification search using path-relinking combined with a look-ahead strategy. The third phase can be viewed as a diversification strategy, where the iterative algorithm tries to avoid premature convergence towards local optima. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature. Its obtained results are compared to those reached by recent algorithms available in the literature. The computational part shows that the method remains competitive (in term of the quality of solutions achieved), where it is able to provide better bounds than those already published ones.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617883
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:04
Dernière modification le : samedi 17 septembre 2022 - 17:36:25

Identifiants

Collections

Citation

Thekra Al-Douri, Mhand Hifi, Vassilis Zissimopoulos. An iterative algorithm for the Max-Min knapsack problem with multiple scenarios. Operational Research, Springer, 2021, 21 (2), pp.1355-1392. ⟨10.1007/s12351-019-00463-7⟩. ⟨hal-03617883⟩

Partager

Métriques

Consultations de la notice

6