On a Stochastic Knapsack Problem and Generalizations

Abstract

We consider an integer stochastic knapsack problem (SKP) where the weight of each item is deterministic, but the vector of returns for the items is random with known distribution. The objective is to maximize the probability that a total return threshold is met or exceeded. We study several solution approaches. Exact procedures, based on dynamic programming (DP) and integer programming (IP), are developed for returns that are independent normal random variables with integral means and variances. Computation indicates that the DP is significantly faster the most efficient algorithm to date. The IP is less efficient, but is applicable to more general stochastic IPs with independent normal returns. We also develop a Monte Carlo approximation procedure to solve SKPs with general distributions on the random returns. This method utilizes upper- and lower-bound estimators on the true optimal solution value in order to construct a confidence interval on the optimality gap of a candidate solution.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1998
Accession Number
ADA495133

Entities

People

  • David P. Morton
  • R. Kevin Wood

Organizations

  • University of Texas at Austin

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computers
  • Demographic Cohorts
  • Dynamic Programming
  • Integer Programming
  • Integrals
  • Intervals
  • Laptop Computers
  • Monte Carlo Method
  • Observation
  • Operations Research
  • Optimization
  • Personal Computers
  • Probability
  • Random Variables

Fields of Study

  • Mathematics

Readers

  • Operations Research
  • Statistical inference.