@article{BiefelKuchlbauerLiersetal.2021, author = {Biefel, Christian and Kuchlbauer, Martina and Liers, Frauke and Waldm{\"u}ller, Lisa}, title = {Robust static and dynamic maximum flows}, year = {2021}, abstract = {We study the robust maximum flow problem and the robust maximum flow over time problem where a given number of arcs Γ may fail or may be delayed. Two prominent models have been introduced for these problems: either one assigns flow to arcs fulfilling weak flow conservation in any scenario, or one assigns flow to paths where an arc failure or delay affects a whole path. We provide a unifying framework by presenting novel general models, in which we assign flow to subpaths. These models contain the known models as special cases and unify their advantages in order to obtain less conservative robust solutions. We give a thorough analysis with respect to complexity of the general models. In particular, we show that the general models are essentially NP-hard, whereas, e.g. in the static case with Γ=1 an optimal solution can be computed in polynomial time. Further, we answer the open question about the complexity of the dynamic path model for Γ=1. We also compare the solution quality of the different models. In detail, we show that the general models have better robust optimal values than the known models and we prove bounds on these gaps.}, language = {en} } @article{KuchlbauerLiersStingl2021, author = {Kuchlbauer, Martina and Liers, Frauke and Stingl, Michael}, title = {Outer approximation for mixed-integer nonlinear robust optimization}, year = {2021}, abstract = {Currently, few approaches are available for mixed-integer nonlinear robust optimization. Those that do exist typically either require restrictive assumptions on the problem structure or do not guarantee robust protection. In this work, we develop an algorithm for convex mixed-integer nonlinear robust optimization problems where a key feature is that the method does not rely on a specific structure of the inner worst-case (adversarial) problem and allows the latter to be non-convex. A major challenge of such a general nonlinear setting is ensuring robust protection, as this calls for a global solution of the non-convex adversarial problem. Our method is able to achieve this up to a tolerance, by requiring worst-case evaluations only up to a certain precision. For example, the necessary assumptions can be met by approximating a non-convex adversarial via piecewise relaxations and solving the resulting problem up to any requested error as a mixed-integer linear problem. In our approach, we model a robust optimization problem as a nonsmooth mixed-integer nonlinear problem and tackle it by an outer approximation method that requires only inexact function values and subgradients. To deal with the arising nonlinear subproblems, we render an adaptive bundle method applicable to this setting and extend it to generate cutting planes, which are valid up to a known precision. Relying on its convergence to approximate critical points, we prove, as a consequence, finite convergence of the outer approximation algorithm. As an application, we study the gas transport problem under uncertainties in demand and physical parameters on realistic instances and provide computational results demonstrating the efficiency of our method.}, language = {en} } @unpublished{AdelhuetteBiefelKuchlbaueretal., author = {Adelh{\"u}tte, Dennis and Biefel, Christitan and Kuchlbauer, Martina and Rolfes, Jan}, title = {Pareto Robust optimization on Euclidean vector spaces}, abstract = {Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis in [9]. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with linear uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing a Pareto robustly optimal solution for a robust SDP is tractable and illustrate the benefit of such solutions at the example of the maximal eigenvalue problem. Furthermore, we modify the famous algorithm of Goemans and Williamson [8] in order to compute cuts for the robust max cut problem that yield an improved approximation guarantee in non-worst-case scenarios.}, language = {en} } @article{KreimeierKuchlbauerLiersetal.2022, author = {Kreimeier, Timo and Kuchlbauer, Martina and Liers, Frauke and Stingl, Michael and Walther, Andrea}, title = {Towards the Solution of Robust Gas Network Optimization Problems Using the Constrained Active Signature Method}, year = {2022}, abstract = {This work studies robust gas network optimization under uncertainties in demand and in the physical parameters. The corresponding optimization problems are nonconvex in node pressures and flows along the pipes. They are thus very difficult to solve for realistic instance sizes. In recent approaches, an adaptive bundle method has been developed, where one solves the occurring adversarial problems via iteratively refined piecewise linear relaxations. These subproblems need to be solved always from scratch using mixed-integer linear programming (MIP). As alternative to the MIP solver, we employ here a nonsmooth optimization approach that allows a warm start strategy such that it can profit from the results obtained for coarser relaxations. We evaluate the approach for realistic gas network topologies and outline possibilities for future research.}, language = {en} } @unpublished{KuchlbauerLiersStingl, author = {Kuchlbauer, Martina and Liers, Frauke and Stingl, Michael}, title = {Adaptive bundle methods for nonlinear robust optimization}, abstract = {Currently, there are few theoretical or practical approaches available for general nonlinear robust optimization. Moreover, the approaches that do exist impose restrictive assumptions on the problem structure. We present an adaptive bundle method for nonlinear and non-convex robust optimization problems with a suitable notion of inexactness in function values and subgradients. As the worst case evaluation requires a global solution to the adversarial problem, it is a main challenge in a general non-convex nonlinear setting. Moreover, computing elements of an epsilon-perturbation of the Clarke subdifferential in the l2-norm sense is in general prohibitive for this class of problems. In this article, instead of developing an entirely new bundle concept, we demonstrate how existing approaches, such as Noll's bundle method for non-convex minimization with inexact information (Computational and analytical mathematics 50: 555-592, 2013) can be modified to be able to cope with this situation. Extending the non-convex bundle concept to the case of robust optimization in this way, we prove convergence under two assumptions: Firstly, that the objective function is lower C1 and secondly, that approximately optimal solutions to the adversarial maximization problem are available. The proposed method is hence applicable to a rather general setting of nonlinear robust optimization problems. In particular, we do not rely on a specific structure of the adversary's constraints. The considered class of robust optimization problems covers the case that the worst-case adversary only needs to be evaluated up to a certain precision. One possibility to evaluate the worst case with the desired degree of precision is the use of techniques from mixed-integer linear programming (MIP). We investigate the procedure on some analytic examples. As applications, we study the gas transport problem under uncertainties in demand and in physical parameters that affect pressure losses in the pipes. Computational results for examples in large realistic gas network instances demonstrate the applicability as well as the efficiency of the method.}, language = {en} } @unpublished{Kuchlbauer, author = {Kuchlbauer, Martina}, title = {Outer approximation for generalized convex mixed-integer nonlinear robust optimization problems}, abstract = {We consider nonlinear robust optimization problems with mixed-integer decisions as well as nonconvexities. In detail, we consider cases where objective and constraint functions can be nonsmooth and generalized convex, i.e., f°-quasiconvex or f°-pseudoconvex. We propose an algorithm for such robust optimization problems that does not require a certain structure of the adversarial problem but only requires that approximate worst cases are available. As a result, our algorithm finds a robust optimal solution up to a tolerance. Our method integrates a bundle method into an outer approximation approach where the bundle method is used for the arising continuous subproblems. We rely on methods from the literature, namely a bundle method for nonlinear and nonconvex robust optimization problems and outer approximation approaches for quasiconvex settings. Our contribution is to combine them to one convergent robust optimization method that can cope with inexactness of worst-case evaluations. Further, we propose the gas transport under uncertainties as a relevant application and demonstrate that generalized convexity is fulfilled for a type of a network structure.}, language = {en} }