Friedrich-Alexander-Universität Erlangen-Nürnberg
Refine
Year of publication
- 2017 (33) (remove)
Language
- English (33)
Keywords
- Networks (4)
- Uniqueness (4)
- robust optimization (3)
- Market Equilibria (2)
- Mixed-Integer Nonlinear Optimization (2)
- Mixed-Integer Nonlinear Programming (2)
- Multiplicity (2)
- gas networks (2)
- 28 (1)
- Adaptive error control (1)
- Boundary feedback control, feedback stabilization, exponential stability, isothermal Euler equations, second-order quasilinear equation, Lyapunov function, stationary state, non-stationary state, gas pipeline. (1)
- Complementarity constraints (1)
- DC Power Flow (1)
- Decomposition Methods (1)
- Dynamic Network Flows (1)
- Dynamic Robust Flow (1)
- Electricity Market Design} (1)
- Electricity System (1)
- Entry-Exit System (1)
- Extended Incremental Method (1)
- First-Discretize-Then-Optimize (1)
- Fundamental Welfare Theorems (1)
- Galerkin projection (1)
- Gas Market (1)
- Gas Transport (1)
- Gas network optimization (1)
- Gas networks (1)
- Gas transport networks (1)
- GasLib (1)
- Generalized Benders Decomposition (1)
- Global classical solutions Ideal gas Bi-directional flow Transsonic flow (1)
- Graph Partitioning (1)
- Instantaneous control (1)
- Inverse parametric quadratic programming (1)
- Isothermal stationary Euler equations (1)
- MPCC (1)
- Marking strategy (1)
- Maximum flow problem (1)
- Mixed-Integer (Non)Linear Programming (1)
- Mixed-Integer Nonlinear Optimization, Lipschitz Optimization, Inexact Function Evaluations, Decomposition Methods, Gas Networks (1)
- Mixed-integer linear optimization (1)
- Mixed-integer optimal control (1)
- Mixing (1)
- Model hierarchy (1)
- Multilevel Modeling (1)
- Multilevel Optimization (1)
- Natural Gas Markets (1)
- Natural Gas System (1)
- Network reduction (1)
- Nonconvex Equilibrium Models (1)
- Optimal control, Gas networks, Euler's equation, Semilinear PDE, Nonoverlapping domain decomposition (1)
- Outer Approximation (1)
- Partial differential equations on graphs (1)
- Peak-Load Pricing (1)
- Perfect Competition (1)
- Piecewise Linearization (1)
- Potential networks (1)
- Potential-based flows (1)
- Power-to-Gas (1)
- Pricing (1)
- Problem Instances (1)
- Risk Aversion (1)
- Semidefinite Programming (1)
- Series-parallel graphs (1)
- Stochastic Programming (1)
- Storage Capacity Maximization (1)
- Transient Gas Transport Optimization (1)
- Transport Costs (1)
- Uncertain Travel Times (1)
- Unit Commitment with AC Power Flow (1)
- chance constraint (1)
- chance constraints (1)
- coupling conditions (1)
- isothermal Euler equations (1)
- multilevel (1)
- network (1)
- nonoverlapping omain decomposition, optimal control of semi-linear ellioptic systems on netowrks (1)
- optimal control (1)
- p-system (1)
- partial differential-algebraic equations (1)
- polynomial optimization (1)
- port-Hamiltonian systems (1)
- relaxations (1)
- spheric-radial decomposition (1)
- spherical radial decomposition (1)
- stationary gas transport (1)
Joint model of probabilistic/robust (probust) constraints applied to gas network optimization
(2017)
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.
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.
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.
In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations (PDEs). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic PDEs and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem (MINLP). For the numerical solution of the MINLP, we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems (MIPs). Finally, we present two case studies that illustrate the applicability of our approach.
Solving Mixed-Integer Nonlinear Programs using Adaptively Refined Mixed-Integer Linear Programs
(2017)
We propose a method for solving mixed-integer nonlinear programs (MINLPs) to global optimality by discretization of occuring nonlinearities. The main idea is based on using piecewise linear functions to construct mixed-integer linear program (MIP) relaxations of the underlying MINLP. In order to find a global optimum of the given MINLP we develope an iterative algorithm which solves MIP relaxations that are adaptively refined. We are able to give convergence results for a wide range of MINLPs requiring only continuous nonlinearities with bounded domains and an oracle computing maxima of the nonlinearities on their domain. Moreover, the practicalness of our approach is shown numerically by an application from the field of gas network optimization.
We consider the discretization and subsequent model reduction of a system of partial differential-algebraic equations describing the propagation of pressure waves in a pipeline network. Important properties like conservation of mass, dissipation of energy, passivity, existence of steady states, and exponential stability can be preserved by an appropriate semi-
discretization in space via a mixed finite element method and also during the further dimension reduction by structure preserving Galerkin projection which is the main focus of this paper. Krylov subspace methods are employed for the construction of the reduced models and we discuss modifications needed to satisfy certain algebraic compatibility conditions; these are required to ensure the well-posedness of the reduced models and the preservation of the key properties. Our analysis is based on the underlying infinite dimensional problem and its Galerkin approximations. The proposed algorithms therefore have a direct interpretation in function spaces; in principle, they are even applicable directly to the original system of partial differential-algebraic
equations while the intermediate discretization by finite elements is only required for the actual
computations. The performance of the proposed methods is illustrated with numerical tests and the necessity for the compatibility conditions is demonstrated by examples.
Feasibility pumps are highly effective primal heuristics for
mixed-integer linear and nonlinear optimization.
However, despite their success in practice there are only few works
considering their theoretical properties.
We show that feasibility pumps can be seen as alternating
direction methods applied to special reformulations of the original
problem, inheriting the convergence theory of these methods.
Moreover, we propose a novel penalty framework that encompasses
this alternating direction method, which allows us to refrain from random
perturbations that are applied in standard versions of feasibility
pumps in case of failure.
We present a convergence theory for the new penalty based alternating
direction method and compare the new variant of the feasibility
pump with existing versions in an extensive numerical study for
mixed-integer linear and nonlinear problems.
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.
This paper provides a first approach to assess gas market interaction on a network with nonconvex flow models. In the simplest possible setup that adequately reflects gas transport and market interaction, we elaborate on the relation of the solution of a simultaneous competitive gas market game, its corresponding mixed nonlinear complementarity problem (MNCP), and a first-best benchmark. We provide conditions under which the solution of the simultaneous game is also the solution of the corresponding MNCP. However, equilibria cannot be determined by the MNCP as the transmission system operator's (TSO’s) first-order conditions are insufficient, which goes back to nonconvexities of the gas flow model. This also implies that the welfare maximization problem may have multiple solutions that sometimes do not even coincide with any of the market equilibria. Our analysis shows that, even in the absence of strategic firms, market interaction fails to implement desirable outcomes from a welfare perspective due to the TSO’s incentive structure. We conclude that the technical environment calls for a market design that commits the TSO to a welfare objective through regulation and propose a design where the market solution corresponds to a welfare maximum and vice versa.
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.