A dynamic programming method with lists for the knapsack sharing problem

Vincent Boyer (1) , Didier El Baz (1) , Moussa Elkihel (1)

1 LAAS-CDA - Équipe Calcul Distribué et Asynchronisme

In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy.

Mots clés: knapsack sharing problem; combinatorial optimization; Max-min programming; dynamic programming

Domaines: Mathématique discrète [cs.DM]

Vincent Boyer, Didier El Baz, Moussa Elkihel. A dynamic programming method with lists for the knapsack sharing problem. Computers & Industrial Engineering, 2011, 61 (2), pp.274-278. ⟨10.1016/j.cie.2010.10.015⟩. ⟨hal-01152352⟩