Refine
Keywords
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.
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.
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.
Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy networks.
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 optimal control problems for the flow of gas or fresh water in pipe networks as well as drainage or sewer systems in open canals. The equations of motion are taken to be represented by the nonlinear isothermal Euler gas equations, the water hammer equations, or the St.~Venant equations for flow. We formulate model hierarchies and derive an abstract model for such network flow problems including pipes, junctions, and controllable elements such as valves, weirs, pumps, as well as compressors. We use the abstract model to give an overview of the known results and challenges concerning equilibria, well-posedness, controllability, and optimal control. A major challenge concerning the optimization is to deal with switching on-off states that are inherent to controllable devices in such applications combined with
continuous simulation and optimization of the gas flow. We formulate the corresponding mixed-integer nonlinear optimal control problems and outline a decomposition approach as a solution technique.
Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for 60% of all instances in at most 10s.
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.
We consider uniqueness and multiplicity of market equilibria in a short-run setup where traded quantities of electricity are transported through a capacitated network in which power flows have to satisfy the classical lossless DC approximation. The firms face fluctuating demand and decide on their production, which is constrained by given capacities. Today, uniqueness of such market outcomes are especially important in more complicated multilevel models for measuring market (in)efficiency. Thus, our findings are important prerequisites for such studies. We show that market equilibria are unique on tree networks under mild assumptions and we also present a priori conditions under which equilibria are unique on cycle networks. On general networks, uniqueness fails to hold and we present simple examples for which multiple equilibria exist. However, we prove a posteriori criteria for the uniqueness of a given solution and characterize situations in which multiple solutions exist.
Detailed modeling of gas transport problems leads to nonlinear
and nonconvex mixed-integer optimization or feasibility models
(MINLPs) because both the incorporation of discrete controls of the
network as well as accurate physical and technical modeling is
required in order to achieve practical solutions. Hence, ignoring
certain parts of the physics model is not valid for practice. In the
present contribution we extend an approach based on linear relaxations
of the underlying nonlinearities by tailored model reformulation
techniques yielding block-separable MINLPs. This combination of
techniques allows us to apply a penalty alternating direction method
and thus to solve highly detailed MINLPs for large-scale real-world
instances. The practical strength of the proposed method is
demonstrated by a computational study in which we apply the method to
instances from steady-state gas transport
including both pooling effects with respect to the mixing of gases of
different composition and a highly detailed compressor station model.
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.
In this paper we analyze peak-load pricing in the presence of network constraints. In our setup, firms facing fluctuating demand decide on the size and location of production facilities. They make production decisions constrained by the invested capacities, taking into account that market prices reflect scarce transmission capacities. We state general conditions for existence and uniqueness of the market equilibrium and provide a characterization of equilibrium investment and production. The presented analysis covers the cases of perfect competition and monopoly - the case of strategic firms is approximated by a conjectural variations approach. Our result is a prerequisite for analyzing regulatory policy options with computational multilevel equilibrium models, since uniqueness of the equilibrium at lower levels is of key importance when solving these models. Thus, our paper contributes to an evolving strand of literature that analyzes regulatory policy based on computational multilevel equilibrium models and aims at taking into account individual objectives of various agents, among them not only generators and customers but also, e.g., the regulator deciding on network expansion.
We present a solution algorithm for problems from
steady-state gas transport optimization.
Due to nonlinear and nonconvex physics and engineering models as
well as discrete controllability of active network devices, these
problems lead to difficult nonconvex mixed-integer nonlinear optimization
models.
The proposed method is based on mixed-integer linear techniques using
piecewise linear relaxations of the nonlinearities and a tailored
alternating direction method.
Most other publications in the field of gas transport optimization only consider
pressure and flow as main physical quantities. In this work, we additionally
incorporate heat power supplies and demands as well as a mixing model for
different gas qualities.
We demonstrate the capabilities of our method on Germany's largest
transport networks and hereby present numerical results on the largest
instances that were ever reported in the literature for this problem
class.
Common energy system models that integrate hydrogen transport in pipelines typically simplify fluid flow models and reduce the network size in order to achieve solutions quickly. This contribution analyzes two different types of pipeline network topologies (namely, star and tree networks) and two different fluid flow models (linear and nonlinear) for a given hydrogen capacity scenario of electrical reconversion in Germany to analyze the impact of these simplifications. For each network topology, robust demand and supply scenarios are generated. The results show that a simplified topology, as well as the consideration of detailed fluid flow, could heavily influence the total pipeline investment costs. For the given capacity scenario, an overall cost reduction of the pipeline costs of 37% is observed for the star network with linear cost compared to the tree network with nonlinear fluid flow. The impact of these improvements regarding the total electricity reconversion costs has led to a cost reduction of 1.4%, which is fairly small. Therefore, the integration of nonlinearities into energy system optimization models is not recommended due to their high computational burden. However, the applied method for generating robust demand and supply scenarios improved the credibility and robustness of the network topology, while the simplified fluid flow consideration can lead to infeasibilities. Thus, we suggest the utilization of the nonlinear model for post- processing to prove the feasibility of the results and strengthen their credibility, while retaining the computational performance of linear modeling.
Every optimization problem has a corresponding verification problem which verifies whether a given optimal solution is in fact optimal. In the literature there are a lot of such ways to verify optimality for a given solution, e.g., the branch-and-bound tree. To simplify this task, Baes et al. introduced optimality certificates for convex mixed-integer nonlinear programs and proved that these are bounded in the number of integer variables. We introduce an algorithm to compute the certificates and conduct computational experiments. Through the experiments we show that the optimality certificates can be surprisingly small.
Since 2005, the gas market in the European Union is liberalized and
the trading of natural gas is decoupled from its transport.
The transport is done by so-called transmissions system operators (TSOs).
The market model established by the European Union views the gas
transmission network as a black box, providing shippers (gas traders
and consumers) the opportunity to transport gas from any entry to
any exit.
TSOs are required to offer maximum independent capacities at each
entry and exit such that the resulting gas flows can be realized by
the network without compromising security of supply.
Therefore, evaluating the available transport capacities is extremely
important to the TSOs.
This paper gives an overview of the toolset for evaluating gas
network capacities that has been developed within the ForNe project,
a joint research project of seven research partners initiated by
Open Grid Europe, Germany's biggest TSO.
While most of the relevant mathematics is described in the
book "Evaluating Gas Network Capacities", this article
sketches the system as a whole, describes some developments that have
taken place recently, and gives some details about the current
implementation.
In entry-exit gas markets as they are currently implemented in Europe, network constraints do not affect market interaction beyond the technical capacities determined by the TSO that restrict the quantities individual firms can trade at the market. It is an up to now unanswered question to what extent existing network capacity remains unused in an entry-exit design and to what extent feasible adjustments of the market design could alleviate inefficiencies. In this paper, we offer a four-level modeling framework that is capable of analyzing these issues and provide some first results on the model structure. In order to decouple gas trading from network congestion management, the TSO is required to determine technical capacities and corresponding booking fees at every entry and exit node up front. Firms book those capacities, which gives them the right to charge or discharge an amount of gas at a certain node up to this capacity in every scenario. Beyond these technical capacities and the resulting bookings, gas trade is unaffected by network constraints. The technical capacities have to ensure that transportation of traded quantities is always feasible. We assume that the TSO is regulated and determines technical capacities, fees, and transportation costs under a welfare objective. As a first step we moreover assume perfect competition among gas traders and show that the booking and nomination decisions can be analyzed in a single level. We prove that this aggregated model has a unique solution. We also show that the TSO's decisions can be subsumed in one level as well. If so, the model boils down to a mixed-integer nonlinear bilevel problem with robust aspects. In addition, we provide a first-best benchmark that allows to assess welfare losses that occur in an entry-exit system. Our approach provides a generic framework to analyze various aspects in the context of semi-liberalized gas markets. Therefore, we finally discuss and provide guidance on how to include several important aspects into the approach, such as network and production capacity investment, uncertain data, market power, and intra-day trading.
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.
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.