Felix Klein Colloquium: 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.

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

Time: 17:15 - 18:30 o'clock

Place: Building 48, room 210

The lectures of the Felix Klein Colloquium will be held at 17:15 in room 210 of the Mathematics Building 48. Beforehand - from 16:45 - there will be an opportunity to meet the speaker at the colloquium tea in room 580.