@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} } @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} } @article{CacchianiJuengerLiersetal.2016, author = {Cacchiani, Valentina and J{\"u}nger, Michael and Liers, Frauke and Lodi, Andrea and Schmidt, Daniel}, title = {Single-commodity robust network design with finite and Hose demand sets}, series = {Mathematical Programming}, volume = {157}, journal = {Mathematical Programming}, number = {1}, doi = {10.1007/s10107-016-0991-9}, pages = {297 -- 342}, year = {2016}, abstract = {We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as {0, 1/2}-Chv{\´a}tal-Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver.}, language = {en} } @article{GottschalkKosterLiersetal.2017, author = {Gottschalk, Corinna and Koster, Arie M.C.A. and Liers, Frauke and Peis, Britta and Schmand, Daniel and Wierz, Andreas}, title = {Robust Flows over Time: Models and Complexity Results}, doi = {10.1007/s10107-017-1170-3}, year = {2017}, abstract = {We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an arc. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most Γ travel times may be prolonged simultaneously due to delay. We develop and study a mathematical model for this problem. As the dynamic robust flow problem generalizes the static version, it is NP-hard to compute an optimal flow. However, our dynamic version is considerably more complex than the static version. We show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we investigate temporally repeated flows and show that in contrast to the non-robust case (i.e., without uncertainties) they no longer provide optimal solutions for the robust problem, but rather yield a worst case optimality gap of at least T. We finally show that for infinite delays, the optimality gap is at most O(k log T), where k is a newly introduced instance characteristic. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times.}, language = {en} } @article{SchweigerLiers2016, author = {Schweiger, Jonas and Liers, Frauke}, title = {A Decomposition Approach for Optimum Gas Network Extension with a Finite Set of Demand Scenarios}, year = {2016}, abstract = {Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, euch subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time.}, language = {en} } @unpublished{GutinaBaermannRoederetal.2022, author = {Gutina, Daria and B{\"a}rmann, Andreas and Roeder, Georg and Schellenberger, Martin and Liers, Frauke}, title = {Optimisation over Decision Trees - A Case Study for the Design of Stable Direct-Current Electricity Networks}, year = {2022}, abstract = {In many real-world mixed-integer optimisation problems from engineering, the side constraints can be subdivided into two categories: constraints which describe a certain logic to model a feasible allocation of resources (such as a maximal number of available assets, working time requirements, maintenance requirements, contractual obligations, etc.), and constraints which model physical processes and the related quantities (such as current, pressure, temperature, etc.). While the first type of constraints can often easily be stated in terms of a mixed-integer program (MIP), the second part may involve the incorporation of complex non-linearities, partial differential equations or even a black-box simulation of the involved physical process. In this work, we propose the integration of a trained tree-based classifier - a decision-tree or a random forest, into a mixed-integer optimization model as a possible remedy. We assume that the classifier has been trained on data points produced by a detailed simulation of a given complex process to represent the functional relationship between the involved physical quantities. We then derive MIP-representable reformulations of the trained classifier such that the resulting model can be solved using state-of-the-art solvers. At the hand of several use cases in terms of possible optimisation goals, we show the broad applicability of our framework that is easily extendable to other tasks beyond engineering. In a detailed real-world computational study for the design of stable direct- current power networks, we demonstrate that our approach yields high-quality solutions in reasonable computation times.}, 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{AignerSchaumannvonLoeperetal., author = {Aigner, Kevin-Martin and Schaumann, Peter and von Loeper, Freimut and Martin, Alexander and Schmidt, Volker and Liers, Frauke}, title = {Robust DC Optimal Power Flow with Modeling of Solar Power Supply Uncertainty via R-Vine Copulas}, abstract = {We present a robust approximation of joint chance constrained DC Optimal Power Flow in combination with a model-based prediction of uncertain power supply via R-vine copulas. It is applied to optimize the discrete curtailment of solar feed-in in an electrical distribution network and guarantees network stability under fluctuating feed-in. This is modeled by a two-stage mixed-integer stochastic optimization problem proposed by Aigner et al. (European Journal of Operational Research, (2021)). The solution approach is based on the approximation of chance constraints via robust constraints using suitable uncertainty sets. The resulting robust optimization problem has a known equivalent tractable reformulation. To compute uncertainty sets that lead to an inner approximation of the stochastic problem, an R-vine copula model is fitted to the distribution of the multi-dimensional power forecast error, i.e., the difference between the forecasted solar power and the measured feed-in at several network nodes. The uncertainty sets are determined by encompassing a sufficient number of samples drawn from the R-vine copula model. Furthermore, an enhanced algorithm is proposed to fit R-vine copulas which can be used to draw conditional samples for given solar radiation forecasts. The experimental results obtained for real-world weather and network data demonstrate the effectiveness of the combination of stochastic programming and model-based prediction of uncertainty via copulas. We improve the outcomes of previous work by showing that the resulting uncertainty sets are much smaller and lead to less conservative solutions while maintaining the same probabilistic guarantees.}, language = {en} } @article{GrimmKleinertLiersetal.2017, author = {Grimm, Veronika and Kleinert, Thomas and Liers, Frauke and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, number = {34(2)}, pages = {406 -- 436}, year = {2017}, abstract = {Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design yields welfare-optimal outcomes. This problem leads to a challenging multilevel model that contains a graph-partitioning problem with multi-commodity flow connectivity constraints and nonlinearities due to proper economic modeling. Furthermore, it has highly symmetric solutions. We develop different problem-tailored solution approaches. In particular, we present an extended KKT transformation approach as well as a generalized Benders approach that both yield globally optimal solutions. These methods, enhanced with techniques such as symmetry breaking and primal heuristics, are evaluated in detail on academic as well as on realistic instances. It turns out that our approaches lead to effective solution methods for the difficult optimization tasks presented here, where the problem-specific generalized Benders approach performs considerably better than the methods based on KKT transformation.}, language = {en} } @unpublished{AssmannLiersStingletal., author = {Aßmann, Denis and Liers, Frauke and Stingl, Michael and Vera, Juan}, title = {Deciding Robust Feasibility and Infeasibility Using a Set Containment Approach: An Application to Stationary Passive Gas Network Operations}, abstract = {In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding set containment of a projection of the feasible region and the uncertainty set. For answering this question, two very general approaches using methods from polynomial optimization are presented --- one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a \nonconvex quadratic problem with absolute values functions. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, removing the absolute values and solving the problem can be decided with linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. For instances where robust feasibility or infeasibility can be decided, level~2 or level~3 of the Lasserre relaxation hierarchy is typically sufficient.}, language = {en} } @article{AmbrosiusGrimmKleinertetal.2018, author = {Ambrosius, Mirjam and Grimm, Veronika and Kleinert, Thomas and Liers, Frauke and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {Endogenous Price Zones and Investment Incentives in Electricity Markets: An Application of Multilevel Optimization with Graph Partitioning}, series = {Energy Economics}, journal = {Energy Economics}, number = {92}, pages = {47}, year = {2018}, abstract = {In the course of the energy transition, load and supply centers are growing apart in electricity markets worldwide, rendering regional price signals even more important to provide adequate locational investment incentives. This paper focuses on electricity markets that operate under a zonal pricing market design. For a fixed number of zones, we endogenously derive the optimal configuration of price zones and available transfer capacities on a network in order to optimally govern investment and production decisions in the long run. In a multilevel mixed-integer nonlinear model that contains a graph partitioning problem on the first level, we determine welfare-maximizing price zones and available transfer capacities for a given electricity market and analyze their impact on market outcomes. Using a generalized Benders decomposition approach developed in Grimm et al. (2019) and a problem-tailored scenario clustering for reducing the input data size, we are able to solve the model to global optimality even for large instances. We apply the approach to the German electricity market as an example to examine the impact of optimal zoning on key performance indicators such as welfare, generation mix and locations, or electricity prices. It turns out that even for a small number of price zones, an optimal configuration of zones induces a welfare level that almost approaches the first best.}, language = {en} } @unpublished{LiersMartinMerkertetal.2020, author = {Liers, Frauke and Martin, Alexander and Merkert, Maximilian and Mertens, Nick and Michaels, Dennis}, title = {Solving Mixed-Integer Nonlinear Optimization Problems using Simultaneous Convexification - a Case Study for Gas Networks}, pages = {36}, year = {2020}, abstract = {Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each constraint function is considered separately. Instead, a considerably tighter relaxation can be found via so-called simultaneous convexification, where convex underestimators are derived for more than one constraint function at a time. In this work, we present a global solution approach for solving mixed-integer nonlinear problems that uses simultaneous convexification. We introduce a separation method that relies on determining the convex envelope of linear combinations of the constraint functions and on solving a nonsmooth convex problem. In particular, we apply the method to quadratic absolute value functions and derive their convex envelopes. The practicality of the proposed solution approach is demonstrated on several test instances from gas network optimization, where the method outperforms standard approaches that use separate convex relaxations.}, 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{AignerClarnerLiersetal.2021, author = {Aigner, Kevin-Martin and Clarner, Jan-Patrick and Liers, Frauke and Martin, Alexander}, title = {Robust Approximation of Chance Constrained DC Optimal Power Flow under Decision-Dependent Uncertainty}, year = {2021}, abstract = {We propose a mathematical optimization model and its solution for joint chance constrained DC Optimal Power Flow. In this application, it is particularly important that there is a high probability of transmission limits being satisfied, even in the case of uncertain or fluctuating feed-in from renewable energy sources. In critical network situations where the network risks overload, renewable energy feed-in has to be curtailed by the transmission system operator (TSO). The TSO can reduce the feed-in in discrete steps at each network node. The proposed optimization model minimizes curtailment while ensuring that there is a high probability of transmission limits being maintained. The latter is modeled via (joint) chance constraints that are computationally challenging. Thus, we propose a solution approach based on the robust safe approximation of these constraints. Hereby, probabilistic constraints are replaced by robust constraints with suitably defined uncertainty sets constructed from historical data. The uncertainty sets are calculated by encompassing randomly drawn scenarios using the scenario approach proposed by Margellos et al. (IEEE Transactions on Automatic Control, 59 (2014)). The ability to discretely control the power feed-in then leads to a robust optimization problem with decision-dependent uncertainties, i.e. the uncertainty sets depend on decision variables. We propose an equivalent mixed-integer linear reformulation for box uncertainties with the exact linearization of bilinear terms. Finally, we present numerical results for different test cases from the Nesta archive, as well as for a real network. We consider the discrete curtailment of solar feed-in, for which we use real-world weather and network data. The experimental tests demonstrate the effectiveness of this method and run times are very fast. Moreover, on average the calculated robust solutions lead only to a small increase in curtailment, when compared to nominal solutions.}, language = {en} } @article{AdelhuetteAssmannGonzalezGrandonetal.2017, author = {Adelh{\"u}tte, Dennis and Aßmann, Denis and Gonz{\`a}lez Grand{\`o}n, Tatiana and Gugat, Martin and Heitsch, Holger and Liers, Frauke and Henrion, Ren{\´e} and Nitsche, Sabrina and Schultz, R{\"u}diger and Stingl, Michael and Wintergerst, David}, title = {Joint model of probabilistic/robust (probust) constraints applied to gas network optimization}, doi = {10.1007/s10013-020-00434-y}, year = {2017}, abstract = {Optimization tasks under uncertain conditions abound in many real-life applications. Whereas solution approaches for probabilistic constraints are often developed in case the uncertainties can be assumed to follow a certain probability distribution, robust approaches are usually used in case solutions are sought that are feasible for all realizations of uncertainties within some pre-defined uncertainty set. As many applications contain different types of uncertainties that require robust as well as probabilistic treatments, we deal with a class of joint probabilistic/robust constraints as its appears in optimization problems under uncertainty. Focusing on complex uncertain gas network optimization problems, we show the relevance of this class of problems for the task of maximizing free booked capacities in an algebraic model for a stationary gas network. We furthermore present approaches for their solution. Finally, we study the problem of controlling a transient system that is governed by the wave equation. The task consists in determining controls such that a certain robustness measure remains below some given upper bound, with high probability.}, language = {en} } @unpublished{LiersScheweThuerauf2019, author = {Liers, Frauke and Schewe, Lars and Th{\"u}rauf, Johannes}, title = {Radius of Robust Feasibility for Mixed-Integer Problems}, publisher = {Informs Journal on Computing}, doi = {10.1287/ijoc.2020.1030}, year = {2019}, abstract = {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. The approaches for the RRF in the literature are restricted to continuous optimization problems. We first analyze relations between the RRF of a MIP and its continuous linear (LP) relaxation. In particular, we derive conditions under which a MIP and its LP relaxation have the same RRF. Afterward, we extend the notion of the RRF such that it can be applied to a large variety of optimization problems and uncertainty sets. In contrast to the setting commonly used in the literature, we consider for every constraint a potentially different uncertainty set that is not necessarily full-dimensional. Thus, we generalize the RRF to MIPs as well as to include "safe" variables and constraints, i.e., where uncertainties do not affect certain variables or constraints. In the extended setting, we again analyze relations between the RRF for a MIP and its LP relaxation. Afterward, we present methods for computing the RRF of LPs as well as of MIPs with safe variables and constraints. Finally, we show that the new methodologies can be successfully applied to the instances in the MIPLIB 2017 for computing the RRF.}, language = {en} } @unpublished{AssmannLiersStingl2017, author = {Aßmann, Denis and Liers, Frauke and Stingl, Michael}, title = {Decomposable Robust Two-Stage Optimization: An Application to Gas Network Operations Under Uncertainty}, year = {2017}, abstract = {We study gas network problems with compressors and control valves under uncertainty that can be formulated as two-stage robust optimization problems. Uncertain data are present in the physical parameters of the pipes as well as in the overall demand. We show how to exploit the special decomposable structure of the problem in order to reformulate the two-stage robust problem as a standard single-stage optimization problem. Since this structure is present in similar problems on e.g., water or direct current electricity networks, we investigate the consequences of the decomposable structure in an abstract setting: The right-hand side of the single-stage problem can be precomputed by solving a series of optimization problems and multiple elements of the right-hand side can be combined into one optimization task. In order to apply our results to gas network problems, we extend piecewise relaxations and preprocessing techniques to incorporate uncertain input data. The practical feasibility and effectiveness of our approach is demonstrated with benchmarks on realistic gas network instances. We observe large speedups due to the described aggregation method together with the developed preprocessing strategies. Furthermore, we are able to solve even comparably large gas network instances quickly for the price of slightly more conservative solutions.}, language = {en} } @unpublished{AignerBaermannBraunetal.2023, author = {Aigner, Kevin-Martin and B{\"a}rmann, Andreas and Braun, Kristin and Liers, Frauke and Pokutta, Sebastian and Schneider, Oskar and Sharma, Kartikey and Tschuppik, Sebastian}, title = {Data-driven Distributionally Robust Optimization over Time}, year = {2023}, abstract = {Stochastic Optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. As the latter is often unknown, Distributionally Robust Optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy which converges at a rate of \$ O(\log T / \sqrt{T})\$, where \$T\$ is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.}, language = {en} } @unpublished{BernhardLiersStingl, author = {Bernhard, Daniela and Liers, Frauke and Stingl, Michael}, title = {A Gradient-Based Method for Joint Chance-Constrained Optimization with Continuous Distributions}, abstract = {The input parameters of an optimization problem are often affected by uncertainties. Chance constraints are a common way to model stochastic uncertainties in the constraints. Typically, algorithms for solving chance-constrained problems require convex functions or discrete probability distributions. In this work, we go one step further and allow non-convexities as well as continuous distributions. We propose a gradient-based approach to approximately solve joint chance-constrained models. We approximate the original problem by smoothing indicator functions. Then, the smoothed chance constraints are relaxed by penalizing their violation in the objective function. The approximation problem is solved with the Continuous Stochastic Gradient method that is an enhanced version of the stochastic gradient descent and has recently been introduced in the literature. We present a convergence theory for the smoothing and penalty approximations. Under very mild assumptions, our approach is applicable to a wide range of chance-constrained optimization problems. As an example, we illustrate its computational efficiency on difficult practical problems arising in the operation of gas networks. The numerical experiments demonstrate that the approach quickly finds nearly feasible solutions for joint chance-constrained problems with non-convex constraint functions and continuous distributions, even for realistically-sized instances.}, language = {en} }