Department Event / Seminar

[IE] The Risk-Averse Static Stochastic Knapsack Problem


Friday, February 22, 2019 - 1:00pm to 2:00pm


D3 W122

We consider a single-resource allocation problem for multiple items with random, independent resource consumption values and deterministic rewards, known as the Static Stochastic Knapsack Problem (SSKP). Existing SSKP literature generally maximizes the expected profit while admitting the possibility of very high losses in some unfavorable scenarios. In this talk, we consider two popular risk measures, Conditional Value-at-Risk (CVaR) and a Mean-Standard Deviation tradeoff, to address the risk within the problem. We first develop mixed-integer linear programming models (MIP) using a scenario-based approach, which can be exploited to provide exact solutions for discrete distributions. For general distributions, a Sample Average Approximation method (SAA) provides approximate solutions. We also propose a robust MIP for the case of normally distributed resource requirements, and characterize key optimality properties of the continuous relaxation of the MIP model. Then, we develop efficient and high-performing 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.

Upcoming Events / Seminars