Optimization Online


Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes

Daniel Blado (deblado***at***gatech.edu)
Alejandro Toriello (atoriello***at***isye.gatech.edu)

Abstract: 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.

Keywords: stochastic knapsack, dynamic program

Category 1: Other Topics (Dynamic Programming )

Category 2: Combinatorial Optimization

Citation: Georgia Tech, October 2016

Download: [PDF]

Entry Submitted: 10/28/2016
Entry Accepted: 10/28/2016
Entry Last Modified: 01/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society