.png){kind=icon}
.png){kind=icon}
Return
An iterative dynamic programming approach for the temporal knapsack problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2020.12.036.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Temporal knapsack
Exact algorithm
Lagrangian relaxation
Successive sublimation dynamic programming method
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W