@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} }