Refine
Document Type
- ZIB-Report (11) (remove)
Has Fulltext
- yes (11)
Is part of the Bibliography
- no (11)
Keywords
- Pooling Problem (3)
- Relaxation (2)
- Buchungsvalidierung (1)
- Cutting Planes (1)
- Entry-Exit Model (1)
- Extreme Points (1)
- Gas Distribution Networks (1)
- Gas Market Liberalization (1)
- Gas Network Access Regulation (1)
- Gas Network Planning (1)
Institute
In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent so-called transmissions system operators or 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 the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.
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 or 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.
The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties.
This paper summarizes the dissertation of Jonas Schweiger for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quadratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch&Bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases.
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 one bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. We formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition. We solve MINLP single-scenario sub-problems and obtain valid bounds even without solving them to optimality. Heuristics prove capable of improving the initial solutions substantially. Results of computational experiments are presented.
Gas distribution networks are complex structures that consist of
passive pipes, and active, controllable elements such as valves and
compressors. Controlling such network means to find a suitable setting
for all active components such that a nominated amount of gas can be
transmitted from entries to exits through the network, without
violating physical or operational constraints. The control of a
large-scale gas network is a challenging task from a practical point
of view. In most companies the actual controlling process is supported
by means of computer software that is able to simulate the flow of the
gas. However, the active settings have to be set manually within such
simulation software. The solution quality thus depends on the
experience of a human planner.
When the gas network is insufficient for the transport then topology
extensions come into play. Here a set of new pipes or active elements
is determined such that the extended network admits a feasible control
again. The question again is how to select these extensions and where
to place them such that the total extension costs are
minimal. Industrial practice is again to use the same simulation
software, determine extensions by experience, add them to the virtual
network, and then try to find a feasible control of the active
elements. The validity of this approach now depends even more on the
human planner.
Another weakness of this manual simulation-based approach is that it
cannot establish infeasibility of a certain gas nomination, unless all
settings of the active elements are tried. Moreover, it is impossible
to find a cost-optimal network extension in this way.
In order to overcome these shortcomings of the manual planning
approach we present a new approach, rigorously based on mathematical
optimization. Hereto we describe a model for finding feasible
controls and then extend this model such that topology extensions can
additionally and simultaneously be covered. Numerical results for real-world instances are presented and
discussed.
The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators.
While previously network operator and gas vendor where united, they were forced to split up into independent companies.
The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way.
We show that these new paradigms lead to new and challenging mathematical optimization problems.
In order to solve them and to provide meaningful results for practice, all aspects of the underlying problems, such as combinatorics, stochasticity, uncertainty, and nonlinearity, have to be addressed.
With such special-tailored solvers, free network capacities and topological network extensions can, for instance, be determined.
Mobile communication is nowadays taken for granted. Having started
primarily as a service for speech communication, data service and
mobile Internet access are now driving the evolution of network
infrastructure. Operators are facing the challenge to match the
demand by continuously expanding and upgrading the network
infrastructure. However, the evolution of the customer's demand is uncertain.
We introduce a novel (long-term) network planning approach based on
multistage stochastic programming, where demand evolution is considered as
a stochastic process and the network is extended as to maximize the
expected profit. The approach proves capable of designing large-scale
realistic UMTS networks with a time-horizon of several years. Our
mathematical optimization model, the solution approach, and computational
results are presented in this paper.
Die mittel- und längerfristige Planung für den Gastransport hat sich durch
Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert.
Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel
diskutiert die hieraus resultierenden mathematischen Planungsprobleme,
welche als Validierung von Nominierungen und Buchungen, Bestimmung der
technischen Kapazität und Topologieplanung bezeichnet werden. Diese
mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze
skizziert.
We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound.
We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which products are mixed in intermediate pools in order to meet quality targets at their destinations. In this technical report, we characterize the extreme points of the convex hull of our non-convex set, and show that they are not finite, i.e., the convex hull is not polyhedral. This analysis was used to derive valid nonlinear convex inequalities and show that, for a specific case, they characterize the convex hull of our set. The new valid inequalities and computational results are presented in ZIB Report 18-12.