Optimization Online


A Column and Constraint Algorithm 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 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.

Keywords: knapsack problem, dynamic program, exact algorithm

Category 1: Integer Programming

Category 2: Other Topics (Dynamic Programming )

Citation: Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, October 2019

Download: [PDF]

Entry Submitted: 10/31/2018
Entry Accepted: 10/31/2018
Entry Last Modified: 10/08/2019

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