Felix-Klein-Kolloquium: Solving Robust Combinatorial Optimization Problems under Budget Uncertainty more efficiently

By the seminal work of Bertsimas & Sim in 2003, we can solve robust combinatorial optimization problems under budget uncertainty in theory by either solving n+1 deterministic problems or a compact LP reformulation introducing only additional continuous variables. Hence, the computational complexity does not increase. In practice however, computation times can increase significantly in comparison to the deterministic instance. In this talk, two approaches to speed-up the solving of such problems are presented. On the one hand, we derive a tailored branch-and-bound algorithm. On the other hand, we show how valid inequalities for the deterministic problem can be recycled to obtain new valid inequalities for the robust problem. This is joint work with Timo Gersing and Christina Büsing.

Referent: Prof. Dr. Arie M.C.A. Koster, RWTH Aachen University

Zeit: 17:15 - 18:30 Uhr

Ort: Gebäude 48, Raum 210

Die Vorträge des Felix-Klein-Kolloquiums finden jeweils um 17.15 Uhr im Raum 210 des Mathematik-Gebäudes 48 statt. Zuvor gibt es ab 16.45 Uhr die Gelegenheit, die Sprecherin oder den Sprecher beim Kolloquiumstee in Raum 580 zu treffen.