A dynamic programming method with lists for the knapsack sharing problem |
| |
Authors: | V Boyer D El Baz M Elkihel |
| |
Affiliation: | CNRS, LAAS, 7 avenue du Colonel Roche, F-31077 Toulouse, France Université de Toulouse, UPS, INSA, INP, ISAE, LAAS, F-31077 Toulouse, France |
| |
Abstract: | 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. |
| |
Keywords: | Knapsack sharing problem Combinatorial optimization Max-min programming Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|