An iterative algorithm for the Max-Min knapsack problem with multiple scenarios - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Operational Research Année : 2021

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

, (1) , (2)
1
2

Résumé

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.
Fichier non déposé

Dates et versions

hal-03617883 , version 1 (23-03-2022)

Identifiants

Citer

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

Collections

U-PICARDIE EPROAD
19 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More