@unpublished{BiefelLiersRolfesetal.2020, author = {Biefel, Christian and Liers, Frauke and Rolfes, Jan and Schmidt, Martin}, title = {Affinely Adjustable Robust Linear Complementarity Problems}, pages = {20}, year = {2020}, abstract = {Linear complementarity problems are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many sub-areas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties - especially in the sense of robust optimization - is still in its infancy. During the last years, robust LCPs have only been studied using the notions of strict and Γ-robustness. Unfortunately, both concepts lead to the problem that the existence of robust solutions cannot be guaranteed. In this paper, we consider affinely adjustable robust LCPs. In the latter, a part of the LCP solution is allowed to adjust via a function that is affine in the uncertainty. We show that this notion of robustness allows to establish strong characterizations of solutions for the cases of uncertain matrix and vector, separately, from which existence results can be derived. Our main results are valid for the case of an uncertain LCP vector. Here, we additionally provide sufficient conditions on the LCP matrix for the uniqueness of a solution. Moreover, based on characterizations of the affinely adjustable robust solutions, we derive a mixed-integer programming formulation that allows to solve the corresponding robust counterpart. If, in addition, the certain LCP matrix is positive semidefinite, we prove polynomial-time solvability and uniqueness of robust solutions. If the LCP matrix is uncertain, characterizations of solutions are developed for every nominal matrix, i.e., these characterizations are, in particular, independent of the definiteness of the nominal matrix. Robust solutions are also shown to be unique for positive definite LCP matrix but both uniqueness and mixed-integer programming formulations still remain open problems if the nominal LCP matrix is not positive definite.}, language = {en} } @unpublished{AignerBurlacuLiersetal., author = {Aigner, Kevin-Martin and Burlacu, Robert and Liers, Frauke and Martin, Alexander}, title = {Solving AC Optimal Power Flow with Discrete Decisions to Global Optimality}, abstract = {We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions. The latter occur, for instance, in the context of the curtailment of renewables or the switching of power generation units and transmission lines. Our approach delivers globally optimal solutions and is provably convergent. We model AC OPF problems with discrete decisions as mixed-integer nonlinear programs. The solution method starts from a known framework that uses piecewise linear relaxations. These relaxations are modeled as as mixed-integer linear programs and adaptively refined until some termination criterion is fulfilled. In this work, we extend and complement this approach by problem-specific as well as very general algorithmic enhancements. In particular, these are mixed-integer second-order cone programs as well as primal and dual cutting planes. For example objective cuts and no-good-cuts help to compute good feasible solutions as where outer approximation constraints tighten the relaxations. We present extensive numerical results for various AC OPF problems where discrete decisions play a major role. Even for hard instances with a large proportion of discrete decisions, the method is able to generate high quality solutions efficiently. Furthermore, we compare our approach with state-of-the-art MINLP. Our method outperforms all other algorithms.}, language = {en} } @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{BiefelLiersRolfesetal., author = {Biefel, Christian and Liers, Frauke and Rolfes, Jan and Schewe, Lars and Z{\"o}ttl, Gregor}, title = {Robust Market Equilibria under Uncertain Cost}, pages = {24}, abstract = {We consider equilibrium problems under uncertainty where firms maximize their profits in a robust way when selling their output. Robust optimization plays an increasingly important role when best guaranteed objective values are to be determined, independently of the specific distributional assumptions regarding uncertainty. In particular, solutions are to be determined that are feasible regardless of how the uncertainty manifests itself within some predefined uncertainty set. Our analysis adopts the robust optimization perspective in the context of equilibrium problems. First, we consider a singlestage, nonadjustable robust setting. We then go one step further and study the more complex two-stage or adjustable case where a part of the variables can adjust to the realization of the uncertainty. We compare equilibrium outcomes with the corresponding centralized robust optimization problem where the sum of all profits are maximized. As we find, the market equilibrium for the perfectly competitive firms differs from the solution of the robust central planner, which is in stark contrast to classical results regarding the efficiency of market equilibria with perfectly competitive firms. For the different scenarios considered, we furthermore are able to determine the resulting price of anarchy. In the case of non-adjustable robustness, for fixed demand in every time step the price of anarchy is bounded whereas it is unbounded if the buyers are modeled by elastic demand functions. For the two-stage adjustable setting, we show how to compute subsidies for the firms that lead to robust welfare optimal equilibria.}, 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{SchmidtAssmannBurlacuetal.2017, author = {Schmidt, Martin and Aßmann, Denis and Burlacu, Robert and Humpola, Jesco and Joormann, Imke and Kanelakis, Nikolaos and Koch, Thorsten and Oucherif, Djamal and Pfetsch, Marc E. and Schewe, Lars and Schwarz, Robert and Sirvent, Mathias}, title = {GasLib - A Library of Gas Network Instances}, series = {Data}, volume = {4}, journal = {Data}, number = {2}, doi = {10.3390/data2040040}, pages = {18}, year = {2017}, abstract = {The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library.}, language = {en} } @article{BaermannLiersMartinetal.2015, author = {B{\"a}rmann, Andreas and Liers, Frauke and Martin, Alexander and Merkert, Maximilian and Thurner, Christoph and Weninger, Dieter}, title = {Solving network design problems via iterative aggregation}, series = {Mathematical Programming Computation}, volume = {7}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-015-0079-1}, pages = {189 -- 217}, year = {2015}, abstract = {In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch.}, language = {en} } @article{LiersMerkert2015, author = {Liers, Frauke and Merkert, Maximilian}, title = {Structural Investigation of Piecewise Linearized Network Flow Problems}, volume = {26}, doi = {10.1137/15M1006751}, pages = {2863 -- 2886}, year = {2015}, abstract = {In this work we study polyhedra in the context of network flow problems, where the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation - a common and established approach in many applications. Several methods for modeling piecewise linear functions are known which provide a complete description for a single network arc. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two-nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on - but not limited to - the multiple choice method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art MIP-solver greatly benefits from using our cutting planes for random and realistic network topologies.}, language = {en} } @unpublished{BaermannGellermannMerkertetal.2016, author = {B{\"a}rmann, Andreas and Gellermann, Thorsten and Merkert, Maximilian and Schneider, Oskar}, title = {Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization}, pages = {24}, year = {2016}, abstract = {We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This case, which we call staircase compatibility, generalizes common properties in applications and allows for a linear description of the integer feasible solutions to (CPMC) with a totally unimodular constraint matrix of polynomial size. We derive two such totally unimodular reformulations for the problem: one that is obtained by a strengthening of the compatibility constraints and one that is based on a representation as a dual network flow problem. Furthermore, we show a natural way to derive integral solutions from fractional solutions to the problem by determining integral extreme points generating this fractional solution. We also evaluate our reformulations from a computational point of view by applying them to two different real-world applications. The first one is a problem in railway timetabling where we try to adapt a given timetable slightly such that energy costs from operating the trains are reduced. The second one is the piecewise linearization of non-linear flow problems on a gas network. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the problem.}, language = {en} }