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 dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We build on a semi-infinite relaxation introduced in previous work, known as the Multiple Choice Knapsack (MCK) bound. Our first contribution is an asymptotic analysis of MCK showing that it is asymptotically tight under appropriate assumptions. In our second contribution, we examine a new, improved relaxation based on a quadratic value function approximation, which introduces the notion of diminishing returns by encoding interactions between remaining items. We compare the bound to previous bounds in literature, including the best known pseudo-polynomial bound. The quadratic bound is theoretically more efficient than the pseudo-polynomial bound, yet empirically comparable to it in both value and running time.
Citation
Georgia Tech, October 2016
Article
View Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes