Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes
Daniel Blado, Alejandro Toriello · SIAM Journal on Optimization · 2019
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 this bound to others from the literature, including the best known pseudopolynomial bound. The quadratic bound is theoretically more efficient than the pseudopolynomial bound, yet empirically comparable to it in both value and running time.