An iterative dynamic programming approach for the temporal knapsack problem
Language
en
Article de revue
This item was published in
European Journal of Operational Research. 2021-09-01, vol. 293, n° 2
Elsevier
English Abstract
In this paper, we address the temporal knapsack problem (TKP). In this generalization of the classical knapsack problem, selected items enter and leave the knapsack at fixed dates. We solve the TKP with a dynamic program ...Read more >
In this paper, we address the temporal knapsack problem (TKP). In this generalization of the classical knapsack problem, selected items enter and leave the knapsack at fixed dates. We solve the TKP with a dynamic program of exponential size, which is solved using a method called Successive Sublimation Dynamic Programming (SSDP). This method starts by relaxing a set of constraints from the initial problem, and iteratively reintroduces them when needed. We show that a direct application of SSDP to the temporal knapsack problem does not lead to an effective method, and that several improvements are needed to compete with the best results from the literature.Read less <
English Keywords
Temporal knapsack
Exact algorithm
Lagrangian Relaxation
Successive Sublimation Dynamic Programming method
Origin
Hal imported