B07
Refine
Keywords
- Gas networks (4)
- Mixed-Integer Nonlinear Programming (4)
- Networks (4)
- Mixed-integer optimization (3)
- Pricing (3)
- Uniqueness (3)
- Bilevel optimization (2)
- Bookings (2)
- Combinatorial optimization (2)
- Convergence (2)
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.
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.
While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas market. For this nontrivial class of games, we develop a solution algorithm that is able to compute the complete set of Nash equilibria instead of just individual solutions or a bigger set of stationary points. Additionally, we prove that for this class of games, the solution set is finite and provide examples for instances without any Nash equilibria in pure strategies. We apply the algorithm to a case study in which we compute strategic booking and nomination decisions in a model of the European entry-exit gas market system. Finally, we use our algorithm to provide a publicly available test library for the considered class of multi-leader multi-follower games. This library contains problem instances with different economic and mathematical properties so that other researchers in the field can test and benchmark newly developed methods for this challenging class of problems.
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.
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.
As a result of its liberalization, the European gas market is organized as an entry-exit system in order to decouple the trading and transport of natural gas. Roughly summarized, the gas market organization consists of four subsequent stages. First, the transmission system operator (TSO) is obliged to allocate so-called maximal technical capacities for the nodes of the network. Second, the TSO and the gas traders sign mid- to long-term capacity-right contracts, where the capacity is bounded above by the allocated technical capacities. These contracts are called bookings. Third, on a day-ahead basis, gas traders can nominate the amount of gas that they inject or withdraw from the network at entry and exit nodes, where the nominated amount is bounded above by the respective booking. Fourth and finally, the TSO has to operate the network such that the nominated amounts of gas can be transported. By signing the booking contract, the TSO guarantees that all possibly resulting nominations can indeed be transported. Consequently, maximal technical capacities have to satisfy that all nominations that comply with these technical capacities can be transported through the network. This leads to a highly challenging mathematical optimization problem. We consider the specific instantiations of this problem in which we assume capacitated linear as well as potential-based flow models. In this contribution, we formally introduce the problem of Computing Technical Capacities (CTC) and prove that it is NP-complete on trees and NP-hard in general. To this end, we first reduce the Subset Sum problem to CTC for the case of capacitated linear flows in trees. Afterward, we extend this result to CTC with potential-based flows and show that this problem is also NP-complete on trees by reducing it to the case of capacitated linear flow. Since the hardness results are obtained for the easiest case, i.e., on tree-shaped networks with capacitated linear as well as potential-based flows, this implies the hardness of CTC for more general graph classes.
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.
In this paper we analyze a uniform price electricity spot market that is followed by redispatch in the case of network congestion. We assume that the transmission system operator is incentivized to minimize redispatch cost and compare a cost-based redispatch (CBR) to a market-based redispatch (MBR) mechanism. For networks with at least three nodes we show that in contrast to CBR, in the case of MBR the redispatch cost minimizing allocation may not be short-run efficient. As we demonstrate, in case of MBR the possibility of the transmission system operator to reduce redispatch cost at the expense of a reduced welfare may be driven by the electricity supply side or the electricity demand side. If, however, the transmission system operator is obliged to implement the welfare maximizing (instead of the redispatch cost minimizing) dispatch by regulation, this will result in an efficient dispatch also in case of MBR.
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.
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.