Refine
Document Type
- ZIB-Report (11)
- Article (5)
- Book chapter (3)
- In Proceedings (3)
- Doctoral Thesis (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (24)
Keywords
- Pooling Problem (4)
- Cutting Planes (2)
- Gas Network Planning (2)
- Nonconvexity (2)
- Quadratic Programming (2)
- Relaxation (2)
- Relaxations (2)
- Standard Quadratic Programming (2)
- Buchungsvalidierung (1)
- Computations (1)
Institute
A Decomposition Approach for Optimal Gas Network Extension with a Finite Set of Demand Scenarios
(2018)
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, each subproblem
consists of a mixed-integer nonlinear optimization problem (MINLP).
Valid bounds on the objective value 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.
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.
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 trans-
ported 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.
Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning
(2010)
Telecommunication is fundamental for the information society. In both, the
private and the professional sector, mobile communication is nowadays taken
for granted. Starting primarily as a service for speech communication, data
service and mobile Internet access are now driving the evolution of network
infrastructure. In the year 2009, 19 million users generated over 33
million GB of traffic using mobile data services. The 3rd generation
networks (3G or UMTS) in Germany comprises over 39,000 base stations with
some 120,000 cells. From 1998 to 2008, the four network operators in
Germany invested over 33 billion Euros in their infrastructure. A careful
allocation of the resources is thus crucial for the profitability for a
network operator: a network should be dimensioned to match customers
demand. As this demand evolves over time, the infrastructure has to evolve
accordingly. The demand evolution is hard to predict and thus constitutes a
strong source of uncertainty. Strategic network planning has to take this
uncertainty into account, and the planned network evolution should adapt to
changing market conditions. The application of superior planning methods
under the consideration of uncertainty can improve the profitability of the
network and creates a competitive advantage. Multistage stochastic
programming is a suitable framework to model strategic telecommunication
network planning.
We present mathematical models and effective optimization procedures for
strategic cellular network design. The demand evolution is modeled as a
continuous stochastic process which is approximated by a discrete scenario
tree. A tree-stage approach is used for the construction of non-uniform
scenario trees that serve as input of the stochastic program. The model is
calibrated by historical traffic observations. A realistic system model of
UMTS radio cells is used that determines coverage areas and cell capacities
and takes signal propagation and interferences into account. The network
design problem is formulated as a multistage stochastic mixed integer
linear program, which is solved using state-of-the-art commercial MIP
solvers. Problem specific presolving is proposed to reduce the problem
size. Computational results on realistic data is presented. Optimization
for the expected profit and the conditional value at risk are performed and
compared.
The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.
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.
Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty
(2017)
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 and
uncertainty in the data pose principal difficulties.
The first part of the thesis deals with non-convex quadratic programs.
Branch&Bound methods for this problem class depend on tight
relaxations. We contribute in several ways: First, we establish a new
way to handle missing linearization variables in the well-known
Reformulation-Linearization-Technique (RLT). This is implemented
into the commercial software CPLEX. Second, we study the optimization
of a quadratic objective over the standard simplex or a knapsack
constraint. These basic structures appear as part of many complex
models. Exploiting connections to the maximum clique problem and RLT,
we derive new valid inequalities. Using exact and heuristic separation
methods, we demonstrate the impact of the new inequalities on the
relaxation and the global optimization of these problems. Third, we
strengthen the state-of-the-art relaxation for the pooling problem, a
well-known non-convex quadratic problem, which is, for example,
relevant in the petrochemical industry. We propose a novel relaxation
that captures the essential non-convex structure of the problem but is
small enough for an in-depth study. We provide a complete inner
description in terms of the extreme points as well as an outer
description in terms of inequalities defining its convex hull (which
is not a polyhedron). We show that the resulting valid convex
inequalities significantly strengthen the standard relaxation of the
pooling problem.
The second part of this thesis focuses on a common challenge in real
world applications, namely, the uncertainty entailed in the input
data.
We study the extension of a gas transport network, e.g., from our
project partner Open Grid Europe GmbH.
For a single scenario this maps to a challenging non-convex MINLP.
As the future transport patterns are highly uncertain, we propose a
robust model to best prepare the network operator for an array of
scenarios.
We develop a custom decomposition approach that makes use of the
hierarchical structure of network extensions and the loose coupling
between the scenarios.
The algorithm used the single-scenario problem as black-box subproblem
allowing the generalization of our approach to problems with the same
structure.
The scenario-expanded version of this problem is out of reach for
today's general-purpose MINLP solvers.
Yet our approach provides primal and dual bounds for instances with up
to 256 scenarios and solves many of them to optimality.
Extensive computational studies show the impact of our work.
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.