# Mixed Integer Models for the Optimisation of Gas Networks in the Stationary Case

### Möller, Markus (2004)Mixed Integer Models for the Optimisation of Gas Networks in the Stationary Case. Technische Universität DarmstadtPh.D. Thesis, Primary publication

 Preview
PDF
moeller-20040514.pdf

Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Mixed Integer Models for the Optimisation of Gas Networks in the Stationary Case
Language: English
Referees: Martin, Prof. Dr. Alexander ; Leugering, Prof. Dr. Guenter
Date: 19 May 2004
Date of oral examination: 14 May 2004
Abstract:

Through out the world the natural gas resources will be one of the most important sources of energy in the future. The development of optimised possibilities for the distribution of gas through a network of pipelines will be very important for an effective operation of a gas transmission network. The aim of this thesis is to formulate this problem as a suitable mathematical mixed integer problem and to find advanced solutions, using techniques of mixed integer programming. The main problem of the so called Transient Technical Optimisation (TTO) is to minimise the total supply costs of a gas transmission company that has to satisfy demands of different kinds. A gas network basically consists of a number of compressors and valves that are connected via pipes. The gas transmission companies dispatchers decide how to run the compressors and how to switch the valves cost-efficiently such that all demands of all customers are satisfied. The cost function mainly consists of the supply costs of driving the compressors. Note that the compressors consum a fraction of the gas transported through the pipelines. The costs imposed by consumed gas should be minimised. The gas transmission network has to satisfy several demands that are described by a minimal or maximal pressure requirement at a certain node or in a pipe. Also the consumers want to get gas of a certain volume and quality. Furthermore some physical constraints, like Kirchhoff's laws have to be modelled. There are also some combinatorial constraints, e.g. the different possibilities of switching the valves or compressor configurations. Note, that some of the constraints are nonlinear, like the pressure loss in a pipeline or the fuel-gas consumption of the compressors. In order to formulate TTO as a mixed integer program we approximate the nonlinear constraints by piecewise linear functions. Considering the experiences of other projects where mixed integer programs have been used, e.g. VLSI-Design or Telecommunications, we know that the problem can be solved by examination of the underlying polyhedra of such complex and high-dimensional mixed integer programs. We know from earlier test evaluations of smaller problems that it is not possible to solve real gas transmission problems with state-of-the-art general mixed integer programming solvers. One programming approach is the search of better valid (or even facet-defining) inequalities of the polyhedra for the use in a Branch-and-Cut Algorithm. We have developed a new class of valid inequalities that have been integrated in a general MIP solver algorithm. Summarising the results it was possible to develop a polynomial separation algorithm for a special class of polyhedra. The use of these cuts reduces the calculation time by a significant factor. A suitable branch-and-bound algorithm is also added. The cuts and the branching algorithms have been tested on several test-models of real gas-networks.

Alternative Abstract:
Alternative AbstractLanguage

Die reichen Gasvorkommen der Erde werden in den nächsten Jahren eine der Hauptenergiequellen unserer Gesellschaft darstellen. Aus diesem Grund gewinnt die Suche nach optimierten Verfahren, große Gasmengen effizient durch weitverzweigte Gasnetze transportieren zu können immer größere Bedeutung. Das Ziel der vorliegenden Arbeit, dieses Problem, das als Transiente Technische Optimierung (TTO) bezeichnet wird, in Form eines gemischt ganzzahligen linearen Optimierungsproblems so zu formulieren, dass die Kosten, die einem Gasversorgungsunternehmen bei der Gasverteilung in einem Gasnetz entstehen, minimiert werden. Das Hauptproblem der Transienten Technischen Optimierung (TTO) besteht darin, die Gesamtheit der Verteilungskosten eines Gasversorgungsunternehmens zu minimieren, so dass alle Anforderungen, die an das Gasnetz gestellt sind, erfüllt werden können. Ein Gasnetzwerk besteht im Wesentlichen aus einer Menge von Kompressoren (Kompressorstationen) und Ventilen, die über Leitungen miteinander verbunden sind. Die Kompressoren werden dazu benutzt, um den in den Gasleitungen durch Reibung entstehenden Druckabfall wieder auszugleichen. Die Dispatcher der Gasversorgungsunternehmen müssen Entscheidungen darüber treffen, wie die Kompressoren und die Ventile kosteneffizient geschaltet werden können, so dass alle Bedingungen, die aufgrund physikalischer oder marktgegebener Situationen an das Gasnetz gestellt werden, erfüllt werden können. Die Kostenfunktion besteht in der Hauptsache aus der Summe der Betriebskosten der einzelnen Verdichter. Hierbei ist zu bedenken, dass die Kompressoren einen gewissen Anteil des durch die Gasleitungen transportierten Gases verbrauchen. Die Kosten und damit die Menge des benötigten Gases sollen minimiert werden. Das Gasnetzwerk muss zusätzlich einige weitere Bedingungen erfüllen, die beispielsweise darin bestehen, dass in einem Knoten oder in einer Leitung ein minimaler Druck nicht unterschritten und ein maximaler Druck nicht überschritten werden darf. Desgleichen ergeben sich aus der Strömungsmechanik physikalische Bedingungen, die ein Gasnetz erfüllen muss, ebenso gelten Erhaltungsgleichungen, wie sie durch die Kirchhoffschen Gesetze beschrieben werden. Besondere Bedeutung bei der Formulierung des Problems der Transienten Technischen Optimierung als gemischt ganzzahliges Optimierungsproblem haben die auftretenden kombinatorischen Nebenbedingungen, z.B. die verschiedenen Möglichkeiten, die Ventile zu schalten oder die verschiedenen Fahrwege von Kompressoren. Hierbei besteht eine wichtige Problematik darin, dass einige Bedingungen nichtlinear sind, wie z.B. der Druckverlust innerhalb der einzelnen Leitungen oder der Brenngasverbrauch der Kompressoren. Um das Problem der TTO als ein gemischt ganzzahliges Programm formulieren zu können, approximieren wir die nichtlinearen Nebenbedingungen durch stückweise lineare Funktionen. Wenn wir die Erfahrungen, die in anderen Projekten, bei denen gemischt ganzzahlige Modelle zur Modellierung eines Problems genutzt wurden, heranziehen (so z.B. im VLSI-Design oder in der Telekommunikation), so war zu erwarten, dass auch das Problem der TTO schnell und effizient gelöst werden kann, wenn die Polyeder der zugrundeliegenden komplexen und hochdimensionalen gemischt ganzzahligen Probleme analysiert werden. Denn Erfahrungen mit früheren Testrechnungen anhand kleiner und stark vereinfachter Gasnetze zeigten, dass es unmöglich ist, reale Gasnetzoptimierungsprobleme mit derzeitig üblichen Standardlösern für allgemeine gemischt ganzzahlige Programme zu lösen. Der Ansatz, der daher in dieser Arbeit verfolgt wird, besteht in der Suche nach besseren gültigen (evtl. sogar facettendefinierenden) Ungleichungen der zugrundeliegenden (Teil-) Polyeder als Voraussetzung für die Anwendung von LP-basierten Branch-and-Bound Verfahren, wobei die LP-Relaxierung durch Schnittebenen verschärft wird (sog. Branch-and-Cut oder Schnittebenenverfahren). Die in dieser Arbeit entwickelten Typen von gültigen Ungleichungen wurden in einen allgemeinen Löser für gemischt ganzzahlige Modelle integriert. Insgesamt konnte ein polynomialer Separierungsalgorithmus für eine spezielle Klasse von Polyedern entwickelt werden. Die Anwendung dieser Schnitte kann die Rechenzeit deutlich reduzieren. Ein ebenfalls entwickeltes Branch-and-Bound Verfahren vervollständigt das erarbeitete Schnittebenenverfahren. Die Schnitte und die Branchingalgorithmen wurden anhand der Berechnungen bei einigen kleineren Gasnetzen getestet.

German
Uncontrolled Keywords: Gemischt Ganzzahlige Optimierung, Gasnetzoptimierung, SOS-Bedingungen, Schnittebenenverfahren
Alternative keywords:
Alternative keywordsLanguage
Gemischt Ganzzahlige Optimierung, Gasnetzoptimierung, SOS-Bedingungen, SchnittebenenverfahrenGerman
Mixed-Integer-Programming, Gas Network Optimization, SOS-Constraints, Branch-and-CutEnglish
URN: urn:nbn:de:tuda-tuprints-4385
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 04 Department of Mathematics
Date Deposited: 17 Oct 2008 09:21