The Stochastic Knapsack Problem

Considered is a knapsack with integer volume F and which is capable of holding K different classes of objects. An object from class k has integer volume bk, k = 1, …, K. Objects arrive randomly to the knapsack; interarrivals are exponential with mean depending on the state of the system. The sojourn time of an object has a general class-dependent distribution. An object in the knapsack from class k accrues revenue at a rate rk. The problem is to find a control policy in order to accept/reject the arriving objects as a function of the current state in order to maximize the average revenue. Optimization is carried out over the class of coordinate convex policies. For the case of K = 2, we show for a wide range of parameters that the optimal control is of the threshold type. In the case of Poisson arrivals and of knapsack and object volumes being integer multiples of each other, it is shown that the optimal policy is always of the double-threshold type. An O(F) algorithm to determine the revenue of threshold policies is also given. For the general case of K classes, we consider the problem of finding the optimal static control where for each class a portion of the knapsack is dedicated. An efficient finite-stage dynamic programming algorithm for locating the optimal static control is presented. Furthermore, variants of the optimal static control which allow some sharing among classes are also discussed.