We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We propose an exact algorithm based on a reformulation of the value function linear program, which dynamically prices variables to refine a value function approximation and generates cutting planes to maintain a dual bound. We provide a detailed analysis of the zero-capacity case, theoretical properties of the general algorithm, and an extensive computational study. Our main empirical conclusion is that the algorithm is able to significantly reduce the gap when initial bounds and/or heuristic policies perform poorly.
Citation
Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, October 2019
Article
View A Column and Constraint Algorithm for the Dynamic Knapsack Problem with Stochastic Item Sizes