An iterative dynamic programming approach for the temporal knapsack problem

In this paper, we address the temporal knapsack problem (TKP), a generalization of the classical knapsack problem, where selected items enter and leave the knapsack at fixed dates. We model 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. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper addresses the temporal knapsack problem and proposes a successive sublimation dynamic programming method to solve it. However, direct application of this method is not effective and further improvements are needed to compete with the best results in the literature.