Operations Research 2025
Abstract Submission

2334. Fast scenario addition for two-stage robust mixed-integer programs

Invited abstract in session WB-2: Robust Optimization, stream Discrete and Combinatorial Optimization.

Wednesday, 10:45-12:15
Room: H4

Authors (first author is the speaker)

1. Johannes Kager
TUM Campus Straubing for Biotechnology and Sustainability, Technical University of Munich
2. Marc Goerigk
Business Decisions and Data Science, University of Passau
3. Dorothee Henke
University of Passau
4. Fabian Schäfer
Supply and Value Chain Management, Technical University of Munich
5. Clemens Thielen
TUM Campus Straubing for Biotechnology and Sustainability, Technical University of Munich

Abstract

We consider two-stage robust mixed-integer programs with finite uncertainty sets and present a new approximate scenario addition method to efficiently solve such problems. Our method builds upon the classical scenario-addition framework and introduces several enhancements aimed at improving scalability, particularly when the second-stage problems are computationally demanding. Key features include the use of dual bounds for second-stage problems to accelerate the identification of promising scenarios to be added to the master problem and adaptive time limits to prevent stagnation on particularly hard second-stage problems. Gaps are propagated between master problem and second-stage problems to enable earlier termination in cases where only a non-zero optimality gap is to be reached.

We evaluate our method on two application problems: a robust capacitated location routing problem and a robust integrated berth allocation and quay crane assignment and scheduling problem. The first problem features a particularly hard second stage, whereas the second problem features an easier second stage and is used to show the general applicability of our method. Our results demonstrate significant performance improvements over existing scenario addition methods in terms of solvable instance size and time efficiency, highlighting the potential of the proposed algorithm for handling large instance sizes.

We also given an outlook on a possible extension of the method to bi-objective two-stage robust problems.

Keywords

Status: accepted

Back to the list of papers