Dennis Fischer: Optimization under Uncertainty
Robust optimisation (RO) is an approach for coping with data uncertainty in optimisation problems. RO does not assume that the underlying probability distributions for the data are known a priori, but instead assumes that the possible scenarios for the uncertain data reside in a so-called uncertainty set. This typically leads to algorithmic problems that are located at the second level of the polynomial hierarchy: Does there exist a solution to the optimisation problem that performs reasonably well under all possible instantiations of the data within the boundaries of the uncertainty set? Dennis Fischer’s research focuses on the complexity and approximability of so-called recoverable RO problems, where the decision variables are split into first stage and second stage decisions; the first stage variables must be chosen before the data scenario is revealed, while the second stage variables are determined when the scenario is known. Fischer concentrates on optimisation problems that go beyond the traditional matroidal structures in recoverable RO; he analyses crucial problem parameters by applying tools from parametrized complexity; for computationally intractable problems, he develops polynomial time approximation algorithms. Furthermore, he looks into cross connections between robust optimization and bilevel optimisation.