An exact constructive algorithm for the knapsack sharing problem - Université de Picardie Jules Verne Accéder directement au contenu
Article Dans Une Revue Optimization Methods and Software Année : 2017

An exact constructive algorithm for the knapsack sharing problem

Résumé

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

Dates et versions

hal-03619534 , version 1 (25-03-2022)

Identifiants

Citer

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

Collections

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

Altmetric

Partager

Gmail Facebook X LinkedIn More