The static stochastic knapsack problem with normally distributed item sizes

Yasemin Merzifonluoglu, Joseph Geunes*, H. Edwin Romeijn

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

17 Citations (Scopus)

Abstract

This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item's value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.

Original languageEnglish
Pages (from-to)459-489
JournalMathematical Programming
Volume134
Issue number2
DOIs
Publication statusPublished - Sep 2012
Externally publishedYes

Keywords

  • OPTIMIZATION
  • NEWSVENDOR
  • ALGORITHM
  • PORTFOLIO
  • SELECTION

Cite this