@article{KleinertGrimmSchmidt2019, author = {Kleinert, Thomas and Grimm, Veronika and Schmidt, Martin}, title = {Outer Approximation for Global Optimization of Mixed-Integer Quadratic Bilevel Problems}, series = {Mathematical Programming (Series B)}, journal = {Mathematical Programming (Series B)}, pages = {28}, year = {2019}, abstract = {Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches.}, language = {en} } @article{KrebsSchmidt2019, author = {Krebs, Vanessa and Schmidt, Martin}, title = {Γ-Robust Linear Complementarity Problems}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, year = {2019}, abstract = {Complementarity problems are often used to compute equilibria made up of specifically coordinated solutions of different optimization problems. Specific examples are game-theoretic settings like the bimatrix game or energy market models like for electricity or natural gas. While optimization under uncertainties is rather well-developed, the field of equilibrium models represented by complementarity problems under uncertainty - especially using the concepts of robust optimization - is still in its infancy. In this paper, we extend the theory of strictly robust linear complementarity problems (LCPs) to Γ-robust settings, where existence of worst-case-hedged equilibria cannot be guaranteed. Thus, we study the minimization of the worst-case gap function of Γ-robust counterparts of LCPs. For box and l1-norm uncertainty sets we derive tractable convex counterparts for monotone LCPs and study their feasibility as well as the existence and uniqueness of solutions. To this end, we consider uncertainties in the vector and in the matrix defining the LCP. We additionally study so-called ρ-robust solutions, i.e., solutions of relaxed uncertain LCPs. Finally, we illustrate the Γ-robust concept applied to LCPs in the light of the above mentioned classical examples of bimatrix games and market equilibrium modeling.}, language = {en} } @article{KrugMehrmannSchmidt2019, author = {Krug, Richard and Mehrmann, Volker and Schmidt, Martin}, title = {Nonlinear Optimization of District Heating Networks}, series = {Optimization and Engineering}, journal = {Optimization and Engineering}, number = {22(2)}, pages = {783 -- 819}, year = {2019}, abstract = {We develop a complementarity-constrained nonlinear optimization model for the time-dependent control of district heating networks. The main physical aspects of water and heat flow in these networks are governed by nonlinear and hyperbolic 1d partial differential equations. In addition, a pooling-type mixing model is required at the nodes of the network to treat the mixing of different water temperatures. This mixing model can be recast using suitable complementarity constraints. The resulting problem is a mathematical program with complementarity constraints subject to nonlinear partial differential equations describing the physics. In order to obtain a tractable problem, we apply suitable discretizations in space and time, resulting in a finite-dimensional optimization problem with complementarity constraints for which we develop a suitable reformulation with improved constraint regularity. Moreover, we propose an instantaneous control approach for the discretized problem, discuss practically relevant penalty formulations, and present preprocessing techniques that are used to simplify the mixing model at the nodes of the network. Finally, we use all these techniques to solve realistic instances. Our numerical results show the applicability of our techniques in practice.}, language = {en} } @unpublished{KrebsMuellerSchmidt2019, author = {Krebs, Vanessa and M{\"u}ller, Michael and Schmidt, Martin}, title = {Γ-Robust Linear Complementarity Problems with Ellipsoidal Uncertainty Sets}, series = {International Transactions in Operational Research}, journal = {International Transactions in Operational Research}, number = {29(1)}, pages = {417 -- 441}, year = {2019}, abstract = {We study uncertain linear complementarity problems (LCPs), i.e., problems in which the LCP vector q or the LCP matrix M may contain uncertain parameters. To this end, we use the concept of Γ-robust optimization applied to the gap function formulation of the LCP. Thus, this work builds upon [16]. There, we studied Γ-robustified LCPs for l1- and box-uncertainty sets, whereas we now focus on ellipsoidal uncertainty set. For uncertainty in q or M, we derive conditions for the tractability of the robust counterparts. For these counterparts, we also give conditions for the existence and uniqueness of their solutions. Finally, a case study for the uncertain traffic equilibrium problem is considered, which illustrates the effects of the values of Γ on the feasibility and quality of the respective robustified solutions.}, language = {en} } @unpublished{SchmidtHillerKochetal.2019, author = {Schmidt, Martin and Hiller, Benjamin and Koch, Thorsten and Pfetsch, Marc and Geißler, Bj{\"o}rn and Henrion, Ren{\´e} and Joormann, Imke and Martin, Alexander and Morsi, Antonio and R{\"o}misch, Werner and Schewe, Lars and Schultz, R{\"u}diger and Steinbach, Marc C.}, title = {Capacity Evaluation for Large-Scale Gas Networks}, pages = {8}, year = {2019}, abstract = {Natural gas is important for the energy turnaround in many countries like in Germany, where it serves as a "bridging energy" towards a fossil-free energy supply in the future. About 20\% of the total German energy demand is provided by natural gas, which is transported through a complex pipeline network with a total length of about 30000 km and the efficient use of the given transport infrastructure for natural gas is of political, economic, and societal importance. As a consequence of the liberalization of the European gas market in the last decades, gas trading and transport have been decoupled. This has led to new challenges for gas transport companies, and mathematical optimization is perfectly suited for tackling many of these challenges. However, the underlying mathematical problems are by far too hard to be solved by today's general-purpose software so that novel mathematical theory and algorithms are needed. The industrial research project "ForNe: Research Cooperation Network Optimization" has been initiated and funded by Open Grid Europe in 2009 and brought together experts in mathematical optimization from seven German universities and research institutes, which cover almost the entire range of mathematical optimization: integer and nonlinear optimization as well as optimization under uncertainty. The mathematical research results have been put together in a software package that has been delivered to Open Grid Europe at the end of the project. Moreover, the research is still continuing - e.g., in the Collaborative Research Center/Transregio 154 "Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks" funded by the German Research Foundation.}, language = {en} } @article{LabbePleinSchmidtetal.2019, author = {Labb{\´e}, Martine and Plein, Fr{\"a}nk and Schmidt, Martin and Th{\"u}rauf, Johannes}, title = {Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks}, series = {Networks}, volume = {78}, journal = {Networks}, number = {2}, doi = {10.1007/s00186-021-00752-y}, pages = {128 -- 152}, year = {2019}, abstract = {We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential-based flows. This enables us to solve the decision variant of the nonlinear potential-difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial-time algorithm. The characterization in terms of potential-difference maximizing load flow scenarios then leads to a polynomial-time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single-cycle networks.}, language = {en} } @article{EgererGrimmKleinertetal.2019, author = {Egerer, Jonas and Grimm, Veronika and Kleinert, Thomas and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment}, series = {European Journal of Operational Research}, journal = {European Journal of Operational Research}, pages = {35}, year = {2019}, abstract = {Many long-term investment planning models for liberalized electricity markets either optimize for the entire electricity system or focus on confined jurisdictions, abstracting from adjacent markets. In this paper, we provide models for analyzing the impact of the interdependencies between a core electricity market and its neighboring markets on key long-run decisions. This we do both for zonal and nodal pricing schemes. The identification of welfare optimal investments in transmission lines and renewable capacity within a core electricity market requires a spatially restricted objective function, which also accounts for benefits from cross-border electricity trading. This leads to mixed-integer nonlinear multilevel optimization problems with bilinear nonconvexities for which we adapt a Benders-like decomposition approach from the literature. In a case study, we use a stylized six-node network to disentangle different effects of optimal regional (as compared to supra-regional) investment planning. Regional planning alters investment in transmission and renewable capacity in the core region, which affects private investment in generation capacity also in adjacent regions and increases welfare in the core region at the cost of system welfare. Depending on the congestion-pricing scheme, the regulator of the core region follows different strategies to increase welfare causing distributional effects among stakeholders.}, language = {en} } @article{KleinertSchmidt2019, author = {Kleinert, Thomas and Schmidt, Martin}, title = {Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method}, series = {INFORMS Journal on Computing}, journal = {INFORMS Journal on Computing}, number = {33 (1)}, doi = {10.1287/ijoc.2019.0945}, pages = {198 -- 215}, year = {2019}, abstract = {Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with mixed-integer linear or quadratic upper level and linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2800 instances - which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method, both in terms of running times and solution quality. This renders the method a suitable sub-routine in global bilevel solvers as well as a reasonable standalone approach.}, language = {en} } @article{GruebelKleinertKrebsetal.2019, author = {Gr{\"u}bel, Julia and Kleinert, Thomas and Krebs, Vanessa and Orlinskaya, Galina and Schewe, Lars and Schmidt, Martin and Th{\"u}rauf, Johannes}, title = {On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM}, series = {Computers \& Operations Research}, journal = {Computers \& Operations Research}, number = {114}, doi = {10.1016/j.cor.2019.104783}, year = {2019}, abstract = {We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, we derive sufficient conditions that ensure uniqueness of generation and demand. We also prove uniqueness of the market equilibrium for the special case of a single storage operator. Nevertheless, in case of multiple storage operators, uniqueness fails to hold in general, which we show by illustrative examples. We conclude the theoretical discussion with a general ex-post condition for proving the uniqueness of a given solution. In contrast to classical settings without storages, the computation of market equilibria is much more challenging since storage operations couple all trading events over time. For this reason, we propose a tailored parallel and distributed alternating direction method of multipliers (ADMM) for efficiently computing spot-market equilibria over long time horizons. We first analyze the parallel performance of the method itself. Finally, we show that the parallel ADMM clearly outperforms solving the respective problems directly and that it is capable of solving instances with more than 42 million variables in less than 13 minutes.}, language = {en} } @unpublished{ScheweSchmidtWeninger2019, author = {Schewe, Lars and Schmidt, Martin and Weninger, Dieter}, title = {A Decomposition Heuristic for Mixed-Integer Supply Chain Problems}, series = {Operations Research Letters}, journal = {Operations Research Letters}, number = {48(3)}, pages = {225 -- 232}, year = {2019}, abstract = {Mixed-integer supply chain models typically are very large but are also very sparse and can be decomposed into loosely coupled blocks. In this paper, we use general-purpose techniques to obtain a block decomposition of supply chain instances and apply a tailored penalty alternating direction method, which exploits the structural properties of the decomposed instances. We further describe problem-specific enhancements of the algorithm and present numerical results on real-world instances that illustrate the applicability of the approach.}, language = {en} } @unpublished{KleinertLabbePleinetal.2019, author = {Kleinert, Thomas and Labb{\´e}, Martine and Plein, Fr{\"a}nk and Schmidt, Martin}, title = {There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization}, series = {Operations Research}, journal = {Operations Research}, number = {68(6)}, pages = {1716 -- 1721}, year = {2019}, abstract = {One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level's dual feasible set such that no bilevel-optimal solution is cut off. In practice, heuristics are often used to find a big-M although it is known that these approaches may fail. In this paper, we consider the hardness of two proxies for the above mentioned concept of a bilevel-correct big-M. First, we prove that verifying that a given big-M does not cut off any feasible vertex of the lower level's dual polyhedron cannot be done in polynomial time unless P=NP. Second, we show that verifying that a given big-M does not cut off any optimal point of the lower level's dual problem (for any point in the projection of the high-point relaxation onto the leader's decision space) is as hard as solving the original bilevel problem.}, language = {en} } @article{GatzertMartinSchmidtetal.2019, author = {Gatzert, Nadine and Martin, Alexander and Schmidt, Martin and Seith, Benjamin and Vogl, Nikolai}, title = {Portfolio Optimization with Irreversible Long-Term Investments in Renewable Energy under Policy Risk: A Mixed-Integer Multistage Stochastic Model and a Moving-Horizon Approach}, series = {European Journal of Operational Research}, journal = {European Journal of Operational Research}, pages = {29}, year = {2019}, abstract = {Portfolio optimization is an ongoing hot topic of mathematical optimization and management science. Due to the current financial market environment with low interest rates and volatile stock markets, it is getting more and more important to extend portfolio optimization models by other types of investments than classical assets. In this paper, we present a mixed-integer multistage stochastic model that includes investment opportunities in irreversible and long-term infrastructure projects in the context of renewable energies, which are also subject to policy risk. On realistic time scales for investment problems of this type, the resulting instances are by far too large to be solved with today's most evolved optimization software. Thus, we present a tailored moving-horizon approach together with suitable approximations and simplifications of the model. We evaluate these approximations and simplifications in a computational sensitivity analysis and derive a final model that can be tackled on a realistic instance by our moving-horizon approach.}, language = {en} } @article{GrimmOrlinskayaScheweetal.2019, author = {Grimm, Veronika and Orlinskaya, Galina and Schewe, Lars and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {Optimal Design of Retailer-Prosumer Electricity Tariffs Using Bilevel Optimization}, series = {Computers \& Operations Research}, journal = {Computers \& Operations Research}, number = {114}, pages = {33}, year = {2019}, abstract = {We compare various flexible tariffs that have been proposed to cost-effectively govern a prosumer's electricity management - in particular time-of-use (TOU), critical-peak-pricing (CPP), and a real-time-pricing tariff (RTP). As the outside option, we consider a fixed-price tariff (FP) that restricts the specific characteristics of TOU, CPP, and RTP, so that the flexible tariffs are at least as profitable for the prosumer as the fixed-price tariff. We propose bilevel models to determine the optimal interplay between the retailer's tariff design and the prosumer's decisions on using the storage, on consumption, and on electricity purchases from as well as electricity sales to the grid. The single-level reformulations of the considered bilevel models are computationally highly challenging optimization problems since they, e.g., combine bilinearities and mixed-integer aspects for modeling certain tariff structures. Based on a computational study using real-world data, we find that RTP increases retailer profits, however, leads to the largest price volatility for the prosumer. TOU and CPP only yield mild additional retailer profits and, due to the multiplicity of optimal plans on the part of the prosumer, imply uncertain revenues for the retailer.}, language = {en} } @article{HauschildMarheinekeMehrmannetal.2019, author = {Hauschild, Sarah-Alexa and Marheineke, Nicole and Mehrmann, Volker and Mohring, Jan and Badlyan, Arbi Moses and Rein, Markus and Schmidt, Martin}, title = {Port-Hamiltonian modeling of district heating networks}, series = {Progress in Differential Algebraic Equations II (edited by Reis T., Grundel S., and Sch{\"o}ps S). Differential-Algebraic Equations Forum}, journal = {Progress in Differential Algebraic Equations II (edited by Reis T., Grundel S., and Sch{\"o}ps S). Differential-Algebraic Equations Forum}, pages = {17}, year = {2019}, abstract = {This paper provides a first contribution to port-Hamiltonian modeling of district heating networks. By introducing a model hierarchy of flow equations on the network, this work aims at a thermodynamically consistent port-Hamiltonian embedding of the partial differential-algebraic systems. We show that a spatially discretized network model describing the advection of the internal energy density with respect to an underlying incompressible stationary Euler-type hydrodynamics can be considered as a parameter-dependent finite-dimensional port-Hamiltonian system. Moreover, we present an infinite-dimensional port-Hamiltonian formulation for a compressible instationary thermodynamic fluid flow in a pipe. Based on these first promising results, we raise open questions and point out research perspectives concerning structure-preserving discretization, model reduction, and optimization.}, language = {en} }