EURO 2025 Leeds
Abstract Submission

247. Mixed-Integer Linear Programming Approximations for the Stochastic Knapsack

Invited abstract in session TD-17: Optimizing Complex Systems: Advances in Combinatorial and Stochastic Techniques, stream Combinatorial Optimization.

Tuesday, 14:30-16:00
Room: Esther Simpson 2.08

Authors (first author is the speaker)

1. Roberto Rossi
Business School, University of Edinburgh
2. Steven Prestwich
Computer Science, Insight Centre for Data Analytics
3. Armagan Tarim
University College Cork

Abstract

We develop a general approximation framework based on mathematical programming to tackle the stochastic knapsack problem. In this problem, the decision maker considers items for which either weights or values, or both, are random. The aim is to select a subset of these items to be included into their knapsack. We consider both static (pre-determined) and dynamic (sequential) decision settings. The knapsack has a given capacity, and if the total realised weight exceeds this capacity then a penalty cost is incurred for each unit of excess capacity utilised. The goal is to maximise the expected net profit. We develop mathematical programming heuristics that can tackle probability distributions of item weights belonging to the exponential family of distributions, as well as a dynamic cut generation heuristic to tackle the case in which item weights follow generic probability distributions. In contrast to other competing approaches in the literature, our heuristics extend seamlessly to the case in which item weights are correlated and follow a multivariate normal distribution. In an extensive computational study we demonstrate that our models are efficient, scalable, and near-optimal.

Keywords

Status: accepted

Back to the list of papers