Optimality conditions for a nonlinear stochastic "knapsack problem"

A nonlinear stochastic "knapsack model" is investigated, which has applications in the optimal management of scarce resources under stochastic conditions, and so it is of interest for many fields. The problem is described as follows. One has a knapsack of capacity C and k classes of objects. The objects belonging to each class become available randomly. The inter-arrival times are exponentially distributed with means dependent on the class and on the state of the knapsack. The sojourn time of each object is independent of the others and described by a class-dependent distribution. When included into the knapsack, an object from class k generates revenue at a class-dependent positive rate. For each class k, the occupied portion of knapsack is given by a nonlinear function of the number of objects of the class that are currently inside the knapsack. The objects can be inserted as long as the knapsack is not full. The optimization problem consists in deciding either acceptance or rejection of the arriving objects in dependence of the current state of the knapsack, in such a way to maximize the average revenue. The functions used to generate such decisions are called "policies". In the specific application to Call Admission Control (CAC) in telecommunications networks, the objects represent requests of connections, the capacity of the knapsack represents the available bandwidth, and the nonlinearity arises from imposing specific Quality of Service (QoS) requirements to the accepted connections. We focus on the case of 2 classes of objects and coordinate-convex policies, for which we provide some necessary conditions for optimality. Then we give exact expressions for the cardinalities of the sets of policies satisfying all such necessary optimality conditions, or only some of them. Finally, we provide a condition under which these cardinalities are signicantly smaller than the cardinality of the set of all coordinate-convex policies. Possible developments are discussed.