Premium
An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
Author(s) -
Carraway Robert L.,
Schmidt Robert L.,
Weatherford Lawrence R.
Publication year - 1993
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.3220400203
Subject(s) - knapsack problem , mathematical optimization , continuous knapsack problem , mathematics , set (abstract data type) , dynamic programming , change making problem , expected value , computer science , stochastic dominance , preference , algorithm , statistics , programming language
We consider the stochastic linear knapsack problem in which costs are known with certainty but returns are independent, normally distributed random variables. The objective is to maximize the probability that the overall return equals or exceeds a specified target value. A previously proposed preference order dynamic programming‐based algorithm has been shown to be potentially suboptimal. We offer an alternative hybrid DP/branch‐and‐bound algorithm that both guarantees optimality and significantly outperforms generating the set of Pareto optimal returns.© 1993 John Wiley & Sons, Inc.