Yasemin Merzifonluoglu, Joseph Geunes and H. Edwin Romeijn. The Static Stochastic Knapsack Problem with Normally Distributed Item Sizes

Abstract. We consider a static stochastic knapsack problem where items with random sizes need to
be assigned to a knapsack whose capacity is known and fixed. An item's value is given by
the realization of the product of a random unit revenue and the random size of the item.
When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty
cost is assessed for each unit of overflow, while our model allows for a salvage value for each
unit of capacity in the knapsack that remains unused. We seek to maximize the expected net
profit resulting from the selection of items in the knapsack. Although the capacity is fixed in
our core model, we show that problems with random capacity as well as problems in which
capacity is a decision variable subject to unit costs and bound constraints fall within this class
of problems as well. We focus on the case where the item sizes are independent and normally
distributed random variables, and provide an exact solution method for a continuous relaxation
of the problem. It is shown that the solution to this relaxation will contain no more than two
fractionally selected items, which is then used in a branch-and-bound algorithm for obtaining
an optimal binary solution. In addition, we present a very efficient heuristic solution method
based on our algorithm for solving the relaxation and empirically show that it provides very
high-quality solutions to the problem.