The Risk-Averse Static Stochastic Knapsack Problem

This paper considers a single-resource allocation problem for multiple items with random, independent resource consumption values, known as the static stochastic knapsack problem (SSKP). Whereas the existing SSKP literature generally assumes a risk-neutral objective using an expected value approach, such an approach can maximize expected profit while admitting the possibility of very high losses in some unfavorable scenarios. Because of this, we consider two popular risk measures, conditional value-at-risk (CVaR) and a mean-standard deviation trade-off, in order to address risk within this problem class. Optimizing the trade-offs associated with these risk measures presents significant modeling and computational challenges. To address these challenges, we first provide mixed-integer linear programming models using a scenario-based approach, which can be exploited to provide exact solutions for discrete distributions. For general distributions, a sample average approximation method provides approximate solutions. We then propose a general mixed integer nonlinear optimization modeling approach for the special case of normally distributed resource requirements. This modeling approach incorporates a new class of normalized penalty functions that account for both the expected costs and risks associated with uncertainty, and it can be specialized to a broad class of risk measures, including CVaR and mean-standard deviation. Our results characterize key optimality properties for the associated continuous relaxation of the proposed general model and provide insights on valuable rank-ordering mechanisms for items with uncertain resource needs under different risk measures. For this broadly applicable case, we present a class of efficient and high-performing asymptotically optimal heuristic methods based on these optimality conditions. An extensive numerical study evaluates the efficiency and quality of the proposed solution methods, identifies optimal item selection strategies, and examines the sensitivity of the solution to varying levels of risk, excess weight penalty values, and knapsack capacity values. Summary of Contribution: This research proposes and analyzes new models for a stochastic resource allocation problem that arises in a variety of operations contexts. One of the primary contributions of the paper lies in providing a succinct, robust, and general model that can address a range of different risk-based objectives and cost assumptions under uncertainty. While the model expression is relatively simple, it embeds a reasonably high degree of underlying complexity, as the analysis shows. In addition, in-depth analysis of the model, both in its general form and under various specific risk measures, uncovers some interesting and powerful insights regarding the problem tradeoffs. Furthermore, this analysis leads to a highly efficient class of heuristic algorithms for solving the problem, which we demonstrate via numerical experimentation to provide close-to-optimal solutions. This computational benefit is a critical element for solving a class of broadly applicable larger problems for which our problem arises as a subproblem that requires repeated solution.