Friedrich-Alexander-Universität Erlangen-Nürnberg
Refine
Year of publication
Keywords
- Bilevel optimization (8)
- Optimal control (7)
- Gas networks (6)
- Uniqueness (6)
- Convergence (5)
- Networks (5)
- Robust optimization (5)
- robust optimization (5)
- Branch-and-cut (4)
- Mixed-Integer Nonlinear Optimization (4)
We consider uncertain robust electricity market equilibrium problems including transmission and generation investments. Electricity market equilibrium modeling has a long tradition but is, in most of the cases, applied in a deterministic setting in which all data of the model are known. Whereas there exist some literature on stochastic equilibrium problems, the field of robust equilibrium models is still in its infancy. We contribute to this new field of research by considering Γ-robust electricity market equilibrium models on lossless DC networks with transmission and generation investments. We state the nominal market equilibrium problem as a mixed complementarity problem as well as its variational inequality and welfare optimization counterparts. For the latter, we then derive a Γ-robust formulation and show that it is indeed the counterpart of a market equilibrium problem with robustified player problems. Finally, we present two case studies to gain insights into the general effects of robustification on electricity market models. In particular, our case studies reveal that the transmission system operator tends to act more risk-neutral in the robust setting, whereas generating firms clearly behave more risk-averse.
This paper is devoted to analysing the explicit slow decay rate and turnpike in the infinite-horizon linear quadratic optimal control problems for hyperbolic systems. Assume that some weak observability or controllability are satisfied, by which, the lower and upper bounds of the corresponding algebraic Riccati operator are estimated, respectively. Then based on these two bounds, the explicit slow decay rate of the closed-loop system with Riccati-based optimal feedback control is obtained. The averaged turnpike property for this problem is also further discussed.
We then apply these results to the LQ optimal control problems constraint to networks of onedimensional wave equations and also some multi-dimensional ones with local controls which lack of GCC (Geometric Control Condition).
In real life decision problems, one almost always is confronted with uncertainty and risk. For practical optimization problems this is manifested by unknown parameters within the input data, or, an inexact knowledge about the system description itself. In case the uncertain problem data is governed by a known probability distribution, stochastic programming offers a variety of models hedging against uncertainty and risk. Most widely employed are two-stage models, who admit a recourse structure: The first-stage decisions are taken before the random event occurs. After its outcome, a recourse (second-stage) action is made, often but not always understood as some "compensation".
In the present thesis, the optimization problems that involve parameters which are not known with certainty are semidefinite programming problems. The constraint sets of these optimization problems are given by intersections of the cone of symmetric, positive semidefinite matrices with either affine or more general equations. Objective functions, formally, may be fairly general, although they often are linear as in the present thesis.
We consider risk neutral and risk averse two-stage stochastic semidefinite programs with continuous and mixed-integer recourse, respectively. For these stochastic optimization problems we analyze their structure, derive solution methods relying on decomposition, and finally apply our results to unit commitment in alternating current (AC) power systems.
Furthermore, deterministic unit commitment in AC power transmission systems is addressed. Beside traditional unit commitment constraints, the physics of power flow are included. To gain globally optimal solutions a recent semidefinite programming (SDP) approach is used which leads to large-scale semidefinite programs with discrete variables on top. As even the SDP relaxation of these programs is too large for being handled in an all-at-once manner by general SDP solvers, it requires an efficient and reliable method to tackle them. To this end, an algorithm based on Benders decomposition is proposed.
With power demand (load) and in-feed from renewables serving as sources of uncertainty, two-stage stochastic programs are set up heading for unit commitment schedules which are both cost-effective and robust with respect to data perturbations. The impact of different, risk neutral and risk averse, stochastic criteria on the shapes of the optimal stochastic solutions will be examined. To tackle the resulting two-stage programs, we propose to approximate AC power flow by semidefinite relaxations. This leads to two-stage stochastic mixed-integer semidefinite programs having a special structure. To solve the latter, the L-shaped method and dual decomposition have been applied and compared.
Finite Time Blow-up of Traveling Wave Solutions for the Flow of Real Gas through Pipeline Networks
(2016)
In the context of gas transportation, analytical solutions are essential
for the understanding of the underlying dynamics described
by a system of partial differential equations. We derive traveling wave
solutions for the 1-d isothermal Euler equations. A non-constant compressibility
factor is used to describe the correlation between density
and pressure. The blow-up of the traveling wave solution in finite time
is proven. We then extend our analysis to networks under appropriate
coupling conditions and derive compatibility conditions to fulfill these
coupling conditions.
We consider optimization problems with a joint probabilistic constraint under
normally distributed uncertain parameters. The parametric constraints
are replaced by one constraint stating that the probability of being feasible
shall exceed or be equal to a prescribed threshold. In order to apply the
concept to gas network optimization under uncertain boundary flows, which
corresponds to the demand of customers, we derive an analytic gradient formula.
The integral corresponding to the probability can be parameterized by
spherical radial decomposition. For this parameterization gradient formulas
are known under convexity assumptions of the parametric constraints in the
parameter. For the application in gas networks that we have in mind, the
convexity assumption of the parametric constraints is not satisfied. Therefore,
we weaken it to convexity of the region of feasible parameters for a fixed
optimization variable. We proceed to show that the assumptions needed for
the gradient formula are met in the gas network optimization problem on
a tree. For the numerical implementation we propose a multilevel sampling
algorithm that uses a coarse approximation of the chance constraint to generate
a warm start for the expensive approximation with fine sampling. The
numerical results illustrate that this approach significantly reduces the computation
time.
We build up a decomposition for the flow generated by the heat equation with a real analytic memory kernel. It
consists of three components: The first one is of parabolic nature; the second one gathers the hyperbolic component
of the dynamics, with null velocity of propagation; the last one exhibits a finite smoothing effect. This decomposition reveals the hybrid parabolic-hyperbolic nature of the flow and clearly illustrates the significant impact of the memory term on the parabolic behavior of the system in the absence of memory terms.
Home energy storage (HES) poses a promising option to foster flexible electricity demand and grid-stabilising self-supply. Understanding the characteristics of potential storage adopters and their motives for adopting is essential to enable targeted measures to promote diffusion. This paper presents an in-depth analysis of motivational and psychological factors as well as product characteristics that affect the willingness to adopt domestic energy storage. Based on a selective sample of solar panel owners as the main energy storage target group, we find that potential adopters differ systematically in their evaluation of economic and non-economic characteristics of home energy storage. Using correlation-based average linkage clustering, we identify four distinct types of storage adopters: finance-oriented, independence-oriented, idealistic and multilaterally oriented households. Our findings emphasise that segment-specific policy strategies and support mechanisms are needed to stimulate HES adoption to pave the way for a sustainable energy system.
Inspired by the successes of stochastic algorithms in the training of deep neural networks and the simulation of interacting particle systems, we propose and analyze a framework for randomized time-splitting in linear-quadratic optimal control. In our proposed framework, the linear dynamics of the original problem is replaced by a randomized dynamics. To obtain the randomized dynamics, the system matrix is split into simpler submatrices and the time interval of interest is split into subintervals. The randomized dynamics is then found by selecting randomly one or more submatrices in each subinterval.
We show that the dynamics, the minimal values of the cost functional, and the optimal control obtained with the proposed randomized time-splitting method converge in expectation to their analogues in the original problem when the time grid is refined. The derived convergence rates are validated in several numerical experiments. Our numerical results also indicate that the proposed method can lead to a reduction in computational cost for the simulation and optimal control of large-scale linear dynamical systems.
We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general.
In the following paper a combined optimization of a coupled electricity and gas system is presented. For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool, considering all system operational and unit technical constraints is solved. The gas network subproblem is a medium-scale mixed-integer nonconvex and nonlinear programming problem. The coupling constraints between the two networks are nonlinear as well. The resulting mixed-integer nonlinear program is linearized with the extended incremental method and an outer approximation technique. The resulting model is evaluated using the Greek power and gas system comprising fourteen gas-fired units under four different approximation accuracy levels. The results indicate the efficiency of the proposed MIP model and the interplay between computational requirements and accuracy.
A Decomposition Approach for Optimum Gas Network Extension with a Finite Set of Demand Scenarios
(2016)
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.
Uncertainty often plays an important role in dynamic flow problems. In this paper, we consider both, a stationary and a dynamic flow model with uncertain boundary data on networks. We introduce two different ways how to compute the probability for random boundary data to be feasible, discussing their advantages and disadvantages. In this context, feasible means, that the flow corresponding to the random boundary data meets some box constraints at the network junctions. The first method is the spheric radial decomposition and the second method is a kernel density estimation.
In both settings, we consider certain optimization problems and we compute derivatives of the probabilistic constraint using the kernel density estimator. Moreover, we derive necessary optimality conditions for the stationary and the dynamic case.
Throughout the paper, we use numerical examples to illustrate our results by comparing them with a classical Monte Carlo approach to compute the desired probability.
In this paper we analyze the turnpike phenomenon for optimal boundary control problems with a linear transport equation with source term. The convex objective function depends on
the boundary traces of the transport equation and is strictly convex with respect to the boundary control. We show an integral turnpike result for an optimal Dirichlet boundary control problem in the sense that if the time horizon goes to infinity, then the dynamic optimal control converges to
the corresponding steady state optimal control.
The novelty of this work is two-sided. On the one hand, even if turnpike results for this kind of optimal boundary control problem already exist, we present a new direct proof without using adjoint calculus that leads to sharper estimates. On the other hand we consider uncertainty in
the initial data and/or in the source term. We show that the integral turnpike result also holds considering uncertainty. Throughout the paper we use numerical examples to illustrate the results.
Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test algorithms that solve mixed-integer problems with only Lipschitz continuous nonlinearities. Our theoretical results depend on the assumptions made on the (in)exactness of function evaluations and on the knowledge of Lipschitz constants. If Lipschitz constants are known, we prove finite termination at approximate globally optimal points both for the case of exact and inexact function evaluations. If only approximate Lipschitz constants are known, we prove finite termination and derive additional conditions under which infeasibility can be detected. A computational study for gas transport problems and an academic case study show the applicability of our algorithms to real-world problems and how different assumptions on the constraint functions up- or downgrade the practical performance of the methods.
The Cost of Not Knowing Enough: Mixed-Integer Optimization with Implicit Lipschitz Nonlinearities
(2018)
It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit constraint functions that cannot be solved for any parameter analytically. For this class of mixed-integer problems we propose a novel algorithm based on an approximation of the feasible set in the domain of the nonlinear function---in contrast to an approximation of the graph of the function considered in prior work. This method is shown to compute approximate global optimal solutions in finite time and we also provide a worst-case iteration bound. In some first numerical experiments we show that the ``cost of not knowing enough'' is rather high by comparing our approach with the open-source global solver SCIP. This reveals that a lot of work is still to be done for this highly challenging class of problems and we thus finally propose some possible directions of future research.
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.
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.
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.
The European gas market is implemented as an entry-exit system, which aims to decouple transport and trading of gas. It has been modeled in the literature as a multilevel problem, which contains a nonlinear flow model of gas physics. Besides the multilevel structure and the nonlinear flow model, the computation of so-called technical capacities is another major challenge. These lead to nonlinear adjustable robust constraints that are computationally intractable in general. We provide techniques to equivalently reformulate these nonlinear adjustable constraints as finitely many convex constraints including integer variables in the case that the underlying network is tree-shaped. We further derive additional combinatorial constraints that significantly speed up the solution process. Using our results, we can recast the multilevel model as a single-level nonconvex mixed-integer nonlinear problem, which we then solve on a real-world network, namely the Greek gas network, to global optimality. Overall, this is the first time that the considered multilevel entry-exit system can be solved for a real-world sized network and a nonlinear flow model.
In this work we analyze the structural properties of the set of feasible bookings in the European entry-exit gas market system. We present formal definitions of feasible bookings and then analyze properties that are important if one wants to optimize over them. Thus, we study whether the sets of feasible nominations and bookings are bounded, convex, connected, conic, and star-shaped. The results depend on the specific model of gas flow in a network. Here, we discuss a simple linear flow model with arc capacities as well as nonlinear and mixed-integer nonlinear models of passive and active networks, respectively. It turns out that the set of feasible bookings has some unintuitive properties. For instance, we show that the set is nonconvex even though only a simple linear flow model is used.