The knapsack problem under uncertainty

In this paper we consider the Knapsack Problem under Uncertainty (KPu). Given a container, the knapsack, characterized by a maximum weight that can be accommodated into and a set of items with given weight and random profit, KPu aims to define the subset of items that can be accommodated into the knapsack such that the sum of the weights of the loaded items does not exceed the knapsack maximum weight, while maximizing the expected value of the total profit of the loaded items. Differently from other papers, where the probability distribution of the profits is known in advance [1], we assume that this distribution is not known a priori, because the random profits are extremely difficult to be measured and it would be rather arbitrary to assume a particular shape for their distribution. Lower and upper bounds based on a deterministic approximation of the stochastic problem are presented. In more details, this approximation is obtained by extending the method presented in [2] and using the method of the asymptotic approximations coming from the extreme values theory. Extensive computational results show the effectiveness of the proposed approach.