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

An exact constructive algorithm for the knapsack sharing problem

Abstract : In this paper, we study the knapsack sharing problem (KSP), a variant of the well-known NP-hard single knapsack problem. We propose an exact constructive tree search that combines two complementary procedures: a reduction interval search and a branch and bound. The reduction search has three phases. The first phase applies a polynomial reduction strategy that decomposes the problem into a series of knapsack problems. The second phase is a size reduction strategy that makes the resolution more efficient. The third phase is an interval reduction search that identifies a set of optimal capacities characterizing the knapsack problems. Experimental results provide computational evidence of the better performance of the proposed exact algorithm in comparison to KSPs best exact algorithm, to Cplex and to KSPs latest heuristic approach. Furthermore, they emphasize the importance of the reduction strategies.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03619534
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : vendredi 25 mars 2022 - 10:49:57
Dernière modification le : samedi 26 mars 2022 - 03:02:24

Identifiants

Collections

Citation

Hedi Mhalla. An exact constructive algorithm for the knapsack sharing problem. Optimization Methods and Software, Taylor & Francis, 2017, 32 (5), pp.1078-1094. ⟨10.1080/10556788.2016.1240795⟩. ⟨hal-03619534⟩

Partager

Métriques

Consultations de la notice

5