Risk Criteria in a Stochastic Knapsack Problem

Abstract

We consider an investor who wants to allocate funds among several projects. Each project is expected to yield a certain reward, and the objective is that a total reward will achieve a certain given amount, called the target. This problem is relatively easy to solve when rewards are deterministic, but may be hard in a more realistic setting when the rewards are stochastic and the investor wants to maximize the probability of attaining the target. We show that, by combining dynamic programming with a search procedure, the stochastic version of the problem can be solved relatively fast when rewards are normally distributed. The procedure is also useful for other risk criteria, which involve both the mean and the variance of the total reward.