Upper Bounds for the 0-1 Stochastic Knapsack Problem and a B&B Algorithm

In this paper we study and solve two different variants of static knapsack problems with random weights: The stochastic knapsack problem with simple recourse as well as the stochastic knapsack problem with probabilistic constraint. Special interest is given to the corresponding continuous problems and three different problem solving methods are presented. The resolution of the continuous problems allows to provide upper bounds in a branch-and-bound framework in order to solve the original problems. Numerical results on a dataset from the literature as well as a set of randomly generated instances are given.