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.
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.
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.
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.
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.
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints.
We describe a two-stage approach to solve the resulting complex and numerically difficult feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before.
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints.
We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.
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 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.