EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2767. Sampling methods for multi-stage robust optimization problems

Invited abstract in session MC-35: Urban Logistics and sustainable TRAnsportation: OPtimization under uncertainTY and MAchine Learning, stream Stochastic, Robust and Distributionally Robust Optimization.

Monday, 12:30-14:00
Room: 44 (building: 303A)

Authors (first author is the speaker)

1. Francesca Maggioni
Department of Management, Information and Production Engineering, University of Bergamo
2. Fabrizio Dabbene
CNR
3. Georg Pflug
Department of Statistics and Decision Support Systems, University of Vienna

Abstract

In this talk, we consider multi-stage robust optimization problems of the minimax type. We assume that the total uncertainty set is the cartesian product of stagewise compact uncertainty sets and approximate the given problem by a sampled subproblem. Instead of looking for the worst case among the infinite and typically uncountable set of uncertain parameters, we consider only the worst case among a randomly selected subset of parameters. By adopting such a strategy, two main questions arise: (1) Can we quantify the error committed by the random approximation, especially as a function of the sample size? (2) If the sample size tends to infinity, does the optimal value converge to the ``true'' optimal value? Both questions will be answered. An explicit bound on the probability of violation is given and chain of lower bounds on the original multi-stage robust optimization problem provided. Numerical results dealing with a multi-stage inventory management problem show that the proposed approach works well for problems with two or three time periods while for larger ones the number of required samples is prohibitively large for computational tractability. Despite this, we believe that our results can be useful for problems with such small number of time periods, and it sheds some light on the challenge for problems with more time periods.

Keywords

Status: accepted

Back to the list of papers