Title: Robust Discrete Optimization: Globalized Gamma Robustness and Radius of Robust Feasibility
Speaker: Prof. Dr Frauke Liers
Affiliation: Dept of Mathematics, FAU Erlangen-Nürnberg
Location: 217 Huxley Building
Time: 15:00 – 16:00

Abstract. In this talk, we extend the notion of two robust optimization methodologies that were originally introduced for continuous problems towards robust discrete tasks. On the one hand, we look at globalized robust optimization that has been proposed as a generalization of the standard robust optimization framework in order to allow for a controlled decrease in protection. It depends on the distance of the realized from the predefined uncertainty set. In this talk, we specialize the notion of globalized robustness to Gamma-uncertainty in order to extend its usability for discrete optimization. We show that the generalized robust counterpart possesses algorithmically tractable reformulations for mixed-integer linear nominal problems that use only slightly more variables and constraints than the standard robust counterpart under Gamma-uncertainty. For combinatorial problems, our globalized robust counterpart remains fixed-parameter tractable, although with a runtime exponential in Gamma. In computational studies, it turns out that our algorithmically tractable reformulations are not more difficult to solve than the respective standard robust counterparts, while globalized robustness is guaranteed. Secondly, we extend the notion of determining the radius of robust feasibility for a mixed integer linear problem (MIP) with uncertain constraints. The radius of robust feasibility (RRF) determines a value for the maximal size of the uncertainty set such that robust feasibility of the MIP can be guaranteed. We will analyze relations between the RRF of a MIP and its continuous relaxation. In contrast to the general setting of the literature, we extend the concept to computing the RRF to MIPs that might include safe constraints. Finally, we apply our methods to the standard benchmark set of the MIPLIB in order to test their performance and analyze the price of robustness with respect to the RRF.

The work about Globalized Gamma Robustness is joint with Andreas Bärmann (FAU Erlangen-Nürnberg, Germany) and Christina Büsing (RWTH Aachen, Germany). The work about the radius of robust feasibility is joint with Lars Schewe and Johannes Thürauf (both FAU Erlangen-Nürnberg, Germany)