The Risk-Averse Static Stochastic Knapsack Problem

Professor Joseph Geunes
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.


Joseph Geunes is a Professor and Associate Head for External Education Programs in the ISE department at TAMU. Before joining TAMU, he was a Professor and John and Mary Lib White Chair in Systems Integration at U. Arkansas from 2016 – 2018. From 1998 until 2016 he was a faculty member in the ISE Department at U. Florida. His research focuses on developing optimization models and solution methods for operations planning problems. He has published over 80 refereed papers, a research monograph and a book titled “Operations Planning: Mixed Integer Optimization Models.” He has advised 17 PhD student graduates and is currently supervising three students at TAMU. He is a fellow of IISE (2015) and is the Deputy Editor of Omega and Department Editor for IISE Transactions.