The problem of gas network optimization is as follows. Gas flows through the network and due to friction with the pipe walls, pressure gets lost. This pressure loss has to be compensated. Therefore there are machines, the so called compressors. A running compressor always consumes some amount of the gas flowing through it as fuel gas. Further, there are consumers that need a certain amount of gas at a specified pressure level, and sources where some gas is fed into the network with a certain pressure. The goal of the so called Transient Technical Optimization (TTO) is to operate the gas network in such a way that the consumer demands are satisfied and the compressors are set in cost-efficiently. This TTO problem leads to a complex mixed integer nonlinear optimization problem.

In a first step we treat the stationary case of gas network optimization where just one time step is considered. We develop techniques for a piece-wise linear approximation of the nonlinearities, where we generalize the so called SOS Type 2 constraints. This results in a large mixed integer linear program. We study sub-polyhedra linking these piece-wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complement the separation algorithms and guarantee the SOS conditions. Our computational results demonstrate the success of this approach.

In a next step we consider the time-dependent case which is also called transient case. At first we need an appropriate modeling of the gas dynamics in pipes. Again we approximate nonlinearities by piece-wise linear functions. In the transient case we also get further conditions. For example we have min-up and min-down times as well as switching costs for compressors.

We compare several modeling techniques for the approximations and study sub-polyhedra in order to strengthen our model by adding valid or even facet-defining inequalities. Finally we need a feasible solution for an upper bound in our branch-and-cut algorithm. Therefore we develop a simulated annealing algorithm.

The first project phase was carried out together with University of Duisburg, Mathematical Programming and Algorithmic Discrete Mathematics, and with Zuse-Institute Berlin.

The second project phase is carried out together with University of Erlangen-Nürnberg, Institute of Applied Mathematics, and with Research Group Numerical Analysis and Scientific Computing.

We are thankful to our industry partners from E.ON Ruhrgas AG and PSI AG.

We also kindly acknowledge the support of BMBF (German ministry of education and sciences) from 2001-2003 and of German Research Association DFG from 2006-2008.

For further details about this project please contact Björn Geißler (geissler [at] mathematik.tu-darmstadt.de)

1. M. Möller,
   Mixed Integer Models for the Optimisation of Gas Networks,
   PhD thesis, Technische Universität Darmstadt, 2004
   
   
2. P. Marcinkowski,
   Schaltbedingungen bei der Optimierung von Gasnetzen: Polyedrische  Untersuchungen und Schnittebenen,
   Masters thesis, Technische Universität Darmstadt, 2005
   
   
3. D. Mahlke,
   Der Simulated Annealing Algorithmus zur transienten Optimierung von Gasnetzen,
   Masters thesis, Technische Universität Darmstadt, 2005
   
   
4. S. Moritz,
   A Mixed Integer Approach for the Transient Case of Gas Network Optimization,
   PhD thesis, Technische Universität Darmstadt, 2006
   
   
5. A. Martin, M. Möller, S. Moritz,
   Mixed integer models for the stationary case of gas network optimization,
   Mathematical Programming, 105: 563 - 582, 2006
   
   
6. D. Mahlke, A. Martin, S. Moritz,
   A Simulated Annealing Algorithm for Transient Optimization in Gas Networks,
   Mathematicals Methods of Operations Research, 66:99 - 115, 2007
   
   
7. P. Bales, B. Geißler, O. Kolb, J. Lang, A. Martin, A. Morsi,
   Comparison of Linear and Nonlinear Optimization of Transient Gas Networks,
   Darmstadt University of Technology, Department of Mathematics, Preprint 2552, 2008