Stochastic linear knapsack programming problem and its application to a portfolio selection problem (Q1119471)

The linear knapsack problem with random multinormal cost coefficients is reduced to the maximization of the probability that the total return exceeds a given level subject to the original simple constraints. The probability assumptions, namely, the special block-diagonal shape of the variance matrix of the cost coefficients, help to decompose the equivalence deterministic problem into simple parametric quadratic subprograms and a master problem - a convex nondifferentiable knapsack problem of lower dimension - that can be solved by a modified simple ranking method. The proposed algorithm is applied to the portfolio selection problem.