Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

An exact decomposition algorithm for the generalized knapsack sharing problem

Abstract : This paper presents an exact algorithm for solving the knapsack sharing problem with common items. In literature, this problem is also denominated the Generalized Knapsack Sharing Problem (GKSP). The GKSP is NP-hard because it lays on the 0-1 knapsack problem and the knapsack sharing problem. The proposed exact method is based on a rigorous decomposition technique which leads to an intense simplification of the solution procedure for the GKSP. Furthermore, in order to accelerate the procedure for finding the optimum solution, an upper bound and several reduction strategies are considered. Computational results on two sets of benchmark instances from literature show that the proposed method outperforms the other approaches in most instances. (C) 2016 Elsevier B.V. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617903
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:19
Dernière modification le : jeudi 24 mars 2022 - 03:00:21

Identifiants

Collections

Citation

Isma Dahmani, Mhand Hifi, Lei Wu. An exact decomposition algorithm for the generalized knapsack sharing problem. European Journal of Operational Research, 2016, 252 (3), pp.761-774. ⟨10.1016/j.ejor.2016.02.009⟩. ⟨hal-03617903⟩

Partager

Métriques

Consultations de la notice

4