An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns

The authors 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 specific target value. A previously proposed preference order dynamic programming-based algorithm has been shown to be potentially suboptimal. The authors offer an alternative hybrid DP/branch-and-bound algorithm that both guarantees optimality and significantly outperforms generating the set of Pareto optimal returns.