On a Stochastic Knapsack Problem and Generalizations
MetadataShow full item record
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 toal return threshold is met or exceeded. We study several solution approaches. Exact procedures, based on dynamic programming (DP) and the 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 SKP's with general distribution 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.
in Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, ed. Woodruff, D.L. and pp. 149-168.
Rightsdefined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Dynamic-programming approaches to single-and multi-stage stochastic knapsack problems for portfolio optimization Khoo, Wai Gea (Monterey, California: Naval Postgraduate School, 1999-03);This thesis proposes new methods, based on dynamic programming, for solving certain single-stage and multi-stage integer stochastic knapsack problems. These problems model stochastic portfolio optimization problems (SPOPs) ...
Mun, Johnathan; Housel, Thomas (Monterey, California, Naval Postgraduate School, 2006);In this quick primer, advanced quantitative risk-based concepts will be introduced, namely, the hands-on application of Monte Carlo simulation, real options analysis, stochastic forecasting and portfolio optimization, and ...
A primer on applying Monte Carlo simulation, real options analysis, knowledge value added, forecasting, and portfolio optimization Mun, Johnathan; Housel, Thomas (Monterey, California. Naval Postgraduate School, 2010); NPS-GSBPP-10-001In this quick primer, advanced quantitative risk-based concepts will be introduced--namely, the hands-on applications of Monte Carlo simulation, real options analysis, stochastic forecasting, portfolio optimization, and ...