Optimization Online


Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes

Daniel Blado(deblado***at***gatech.edu)
Weihong Hu(weihongh***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 choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We propose a new semi-infinite relaxation based on an affine value function approximation, and show that an existing pseudo-polynomial relaxation corresponds to a non-parametric value function approximation. We compare both theoretically to other relaxations from the literature and also perform a computational study. Our main empirical conclusion is that our new relaxation provides tight bounds over a variety of different instances and becomes tighter as the number of items increases.

Keywords: stochastic knapsack, relaxation, dynamic program

Category 1: Integer Programming (0-1 Programming )

Category 2: Other Topics (Dynamic Programming )

Citation: School of Industrial and Systems Engineering, Georgia Institute of Technology, August 2015

Download: [PDF]

Entry Submitted: 08/20/2015
Entry Accepted: 08/20/2015
Entry Last Modified: 08/20/2015

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