On two-stage stochastic knapsack problems

In this paper we study a particular version of the stochastic knapsack problem with normally distributed weights: the two-stage stochastic knapsack problem. Contrary to the single-stage knapsack problem, items can be added to or removed from the knapsack at the moment the actual weights become known (second stage). In addition, a chance-constraint is introduced in the first stage in order to restrict the percentage of cases where the items chosen lead to an overload in the second stage. To the best of our knowledge, there is no method known to exactly evaluate the objective function for a given first-stage solution. Therefore, we propose methods to calculate the upper and lower bounds. These bounds are used in a branch-and-bound framework in order to search the first-stage solution space. Special interest is given to the case where the items have similar weight means. Numerical results are presented and analyzed.