TU Darmstadt / ULB / tuprints

A Mixed Integer Approach for the Transient Case of Gas Network Optimization

Moritz, Susanne :
A Mixed Integer Approach for the Transient Case of Gas Network Optimization.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2007)

[img]
Preview
Dissertation - PDF
diss.pdf
Available under Simple publication rights for ULB.

Download (1219Kb) | Preview
Item Type: Ph.D. Thesis
Title: A Mixed Integer Approach for the Transient Case of Gas Network Optimization
Language: English
Abstract:

Natural gas is the third most important energy source in the world. Presently, the consumption of natural gas is increasing the most in comparison to other non-renewable energy sources. Therefore, optimization of gas transport in networks poses a very important industrial problem. In this thesis we consider the problem of time-dependent optimization in gas networks, also called Transient Technical Optimization (TTO). A gas network consists of a set of pipes to transport the gas from the suppliers to the consumers. Due to friction with the pipe walls gas pressure gets lost. This pressure loss is compensated by so called compressors. The aim of TTO is to minimize the fuel consumption of the compressors, where the demands of consumers have to be satisfied. Transient optimization of gas transmission is one of the great research challenges in this area. We formulate a mixed integer approach for the problem of TTO which concentrates on time-dependent and discrete aspects. Thereby, the nonlinearities resulting from physical constraints are approximated using SOS (Special Ordered Set) conditions. A branch-and-cut algorithm is developed which guarantees global optimality in dependence on the approximation accuracy. Concerning the nonlinearities, we discuss the quality of approximation grids by calculating approximation errors. The SOS conditions are implicitly handled via a branching scheme, supported by adequate preprocessing techniques. A heuristic approach based on simulated annealing yields an upper bound in our branch-and-cut framework. To improve the lower bound, we incorporate two separation algorithms. The first one results from theoretical studies of the so called switching polytopes which are defined by runtime conditions and switching processes of compressors. Linking of different SOS conditions gives a second separation strategy. We present theoretical investigations of the SOS 2 and SOS 3 polytope. These polytopes arise from the modeling of SOS Type 2 and SOS Type 3 conditions using additional binary variables. The results do not have practical relevance for our solution algorithm, but we characterize facet-defining inequalities providing complete linear descriptions of these polytopes. We evaluate the developed branch-and-cut algorithm using three test networks provided by our project partner E.ON Ruhrgas AG. Two are of artificial nature, as they were developed for test purposes. They contain all important elements of a gas network, but are rather small. The third network characterizes the major part of the Ruhrgas AG network in Western Germany. We test instances from three up to 24 coupled time steps.

Alternative Abstract:
Alternative AbstractLanguage
Erdgas ist der drittwichtigste Energieträger der Welt. Der Verbrauch von Erdgas steigt derzeit am stärksten im Vergleich zu anderen nicht erneuerbaren Energieträgern. Daher stellt Optimierung von Gastransport in Netzwerken eine wichtige logistische Herausforderung dar. In dieser Dissertation betrachten wir das Problem der zeitabhängigen Optimierung von Gasnetzwerken, auch genannt Transiente Technische Optimierung (TTO). Ein Gasnetz besteht aus einer Menge von Leitungen, die das Gas von den Lieferanten zu den Abnehmern transportieren. Aufgrund von Reibung an den Rohrwänden geht Gasdruck verloren. Dieser Druckverlust wird mit sogenannten Kompressoren ausgeglichen. Das Ziel der TTO ist es, den Brenngasverbrauch der Kompressoren zu minimieren, wobei der Bedarf der Abnehmer immer gedeckt werden muß. Transiente Optimierung der Gasverteilung stellt eine große Herausforderung an die Forschung auf diesem Gebiet. Wir formulieren einen gemischt-ganzzahligen Ansatz für das Problem der TTO, der sich auf die zeitabhängigen und diskreten Aspekte konzentriert. Dafür werden die Nichtlinearitäten, die sich aus physikalischen Bedingungen ergeben, unter Verwendung von SOS-Mengen stückweise linear angenähert. Ein Branch-and-Cut Verfahren wird entwickelt, das globale Optimalität in Abhängigkeit von der Approximationsgenauigkeit garantiert. Hinsichtlich der Nichtlinearitäten gehen wir auf die Güte der Approximationsgitter näher ein, indem wir die Näherungsfehler betrachten. Die SOS Bedingungen werden implizit mittels geeigneter Branchingstrategien modelliert, welche durch entsprechende Preprocessing Techniken verbessert werden. Ein heuristischer Ansatz basierend auf Simulated Annealing liefert eine obere Schranke in unserem Branch-and-Cut Verfahren. Zur Verbesserung der unteren Schranke verwenden wir zwei Separierungsalgorithmen. Der erste ergibt sich aus theoretischen Studien der so genannten Switching Polytope, die durch Laufzeitbedingungen und Schaltprozesse von Kompressoren definiert werden. Die Verknüpfung unterschiedlicher SOS Bedingungen liefert eine zweite Separierungsstrategie. Wir präsentieren theoretische Untersuchungen der SOS 2 und SOS 3 Polytope. Diese Polytope ergeben sich aus der Modellierung von SOS Typ 2 und SOS Typ 3 Bedingungen mittels zusätzlicher binärer Variablen. Die Ergebnisse haben keine praktische Bedeutung für unseren Lösungsalgorithmus, jedoch charakterisieren wir Ungleichungen, die Facetten definieren und insgesamt eine vollständige Beschreibung dieser Polytope liefern. Wir evaluieren das entwickelte Branch-and-Cut Verfahren mittels dreier Testnetzwerke, die uns von unserem Projektpartner E.ON Ruhrgas AG zur Verfügung gestellt wurden. Zwei dieser Netzwerke sind künstlicher Art, da sie für Testzwecke entwickelt wurden und keine realen Netze widerspiegeln. Sie enthalten alle wichtigen Elemente eines Gasnetzes, sind jedoch eher klein. Das dritte Netzwerk beschreibt den größten Teil des Transportnetzes der Ruhrgas AG im Westen Deutschlands. Wir testen Instanzen von drei bis zu 24 gekoppelten Zeitschritten.German
Uncontrolled Keywords: Gasnetzoptimierung, SOS Bedingung, stückweise lineare Funktionen, Facette
Alternative keywords:
Alternative keywordsLanguage
Gasnetzoptimierung, SOS Bedingung, stückweise lineare Funktionen, FacetteGerman
gas optimization, SOS condition, piece-wise linear functions, facetEnglish
Classification DDC: 500 Naturwissenschaften und Mathematik > 510 Mathematik
Divisions: Fachbereich Mathematik
Date Deposited: 17 Oct 2008 09:22
Last Modified: 07 Dec 2012 11:52
Official URL: http://elib.tu-darmstadt.de/diss/000785
URN: urn:nbn:de:tuda-tuprints-7850
License: Simple publication rights for ULB
Referees: Martin, Prof. Dr. Alexander and Schultz, Prof. Dr. Rüdiger
Advisors: Martin, Prof. Dr. Alexander
Refereed: 6 December 2006
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/785
Export:

Actions (login required)

View Item View Item