TU Darmstadt / ULB / TUbiblio

Optimal Operation of Water Supply Networks by Mixed Integer Nonlinear Programming and Algebraic Methods

Huang, Wei (2019)
Optimal Operation of Water Supply Networks by Mixed Integer Nonlinear Programming and Algebraic Methods.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

In this thesis we are dealing with the operative planning of water supply networks. The task of an operative planning is to create a pump and valve configuration such that the water requirement from consumers is fulfilled with necessary quality. An optimal operation corresponds to a configuration that minimizes the operation cost as well as potential water procurement cost.

There are different ways to handle this problem. We solve it as an optimization problem using mathematical programming. On the one hand, the network problem contains some discrete variables, for example, the pump or valve status; on the other hand, nonlinearities and nonconvexities from physical behaviors make the mathematical model extremely difficult. We model the optimization problem as a mixed-integer nonlinear program (MINLP).

We choose MINLP solver SCIP, developed mainly at Zuse Insitute Berlin. We use two real-world instances provided by industrial partner Siemens and a further real-world instance obtained from the Department of Hydraulic Engineering of Tsinghua University.

In this thesis, we first show that our solver SCIP is able to solve the optimal operation problem to global optimality in a fixed point of time. However, for a daily operation which contains 24 coupled time periods (hours), "good" solutions are usually found rapidly, but the dual gap cannot verify the solution quality.

In a further chapter we show that a class of subnetworks which only contains pipes and consumers, can be simplified and the original nonlinear constraints can be replaced by few (or single) nonlinear constraints, without changing the feasible region. Computation shows that this simplification makes the MINLP easier to solve.

The algorithm which solves our nonconvex MINLP generates at every iteration a convex relaxation of the feasible region. A lot of theories and experiments showed that tighter convex relaxation is quite relevant for the branch-and-bound approach.

In the objective of our model, we have bivariate polynomial term with degree 3. Based on the default construction of convex relaxation, we want to find additional linear constrains ("valid cuts") to make the relaxation tighter. We investigate the graph of general polynomial functions over a polytope in general dimension and develop theory to describe the convex hull of the graph and to find halfspaces which contain the convex hull. After that we define "tight" halfspaces which denote the "efficient" halfspaces when forming the convex hull. For bivariate polynomial functions with degree 3, algorithms are designed to find such tight halfspaces. After adding these halfspaces (linear constraints) into the MINLP, computation shows that both primal and dual bound are definitively improved within the same time limit.

Typ des Eintrags: Dissertation
Erschienen: 2019
Autor(en): Huang, Wei
Art des Eintrags: Erstveröffentlichung
Titel: Optimal Operation of Water Supply Networks by Mixed Integer Nonlinear Programming and Algebraic Methods
Sprache: Englisch
Referenten: Pfetsch, Prof. Dr. Marc E. ; Hemmecke, PD Dr. Raymond
Publikationsjahr: 2019
Ort: Darmstadt
Verlag: tuprints
Datum der mündlichen Prüfung: 16 April 2019
URL / URN: https://tuprints.ulb.tu-darmstadt.de/8657
Kurzbeschreibung (Abstract):

In this thesis we are dealing with the operative planning of water supply networks. The task of an operative planning is to create a pump and valve configuration such that the water requirement from consumers is fulfilled with necessary quality. An optimal operation corresponds to a configuration that minimizes the operation cost as well as potential water procurement cost.

There are different ways to handle this problem. We solve it as an optimization problem using mathematical programming. On the one hand, the network problem contains some discrete variables, for example, the pump or valve status; on the other hand, nonlinearities and nonconvexities from physical behaviors make the mathematical model extremely difficult. We model the optimization problem as a mixed-integer nonlinear program (MINLP).

We choose MINLP solver SCIP, developed mainly at Zuse Insitute Berlin. We use two real-world instances provided by industrial partner Siemens and a further real-world instance obtained from the Department of Hydraulic Engineering of Tsinghua University.

In this thesis, we first show that our solver SCIP is able to solve the optimal operation problem to global optimality in a fixed point of time. However, for a daily operation which contains 24 coupled time periods (hours), "good" solutions are usually found rapidly, but the dual gap cannot verify the solution quality.

In a further chapter we show that a class of subnetworks which only contains pipes and consumers, can be simplified and the original nonlinear constraints can be replaced by few (or single) nonlinear constraints, without changing the feasible region. Computation shows that this simplification makes the MINLP easier to solve.

The algorithm which solves our nonconvex MINLP generates at every iteration a convex relaxation of the feasible region. A lot of theories and experiments showed that tighter convex relaxation is quite relevant for the branch-and-bound approach.

In the objective of our model, we have bivariate polynomial term with degree 3. Based on the default construction of convex relaxation, we want to find additional linear constrains ("valid cuts") to make the relaxation tighter. We investigate the graph of general polynomial functions over a polytope in general dimension and develop theory to describe the convex hull of the graph and to find halfspaces which contain the convex hull. After that we define "tight" halfspaces which denote the "efficient" halfspaces when forming the convex hull. For bivariate polynomial functions with degree 3, algorithms are designed to find such tight halfspaces. After adding these halfspaces (linear constraints) into the MINLP, computation shows that both primal and dual bound are definitively improved within the same time limit.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

In dieser Arbeit beschäftigen wir uns mit der operativen Planung von Wasserversorgungsnetzen. Die Aufgabe einer operativen Planung ist eine Pump- und Ventilkonfiguration zu erstellen, so dass der Wasserbedarf von Verbrauchern mit notwendiger Qualität erfüllt wird.

Ein optimaler Betrieb entspricht einer Konfiguration, welche die Betriebskosten sowie Mögliche Wasserbeschaffungskosten minimiert. Es gibt verschiedene Möglichkeiten, dieses Problem zu lösen. Wir lösen es als ein Optimierungsproblem mit mathematischer Optimierung. Einerseits enthält das Netzwerkproblem einige diskrete Variablen, zum Beispiel der Pumpen- oder Ventilstatus; andererseits, machen Nichtlinearitäten und Nichtkonvexitäten aus physikalischem Verhalten das mathematische Modell extrem schwierig. Wir modellieren das Optimierungsproblem als ein gemischt-ganzzahliges nichtlineares Programm (MINLP).

Wir haben uns für den MINLP-Solver SCIP entschieden, der im Zuse Institut Berlin entwickelt wird. Wir verwenden zwei reale Instanzen bereitgestellt von dem Industriepartner Siemens und eine weitere reale Instanz versorgt von der Fakultät Hydraulic Engineering der Tsinghua- Universität.

Wir zeigen zuerst, dass unser Solver SCIP in der Lage ist, das optimale Planungsproblem der Wasserversorgungsnetzen in einem festen Zeitpunkt zu globaler Optimalität zu lösen. Allerdings können zwar gute Lösungen für den täglichen Betrieb, welcher 24 gekoppelte Zeiträume (Stunden) enthält, gefunden werden. Deren Qualität kann allerdings wegen der schwachen dualen Schranke nicht bestätigt werden.

In einem weiteren Kapitel zeigen wir, dass eine Klasse von Teilnetzen, welche nur Wasserrohren und Verbraucher enthalten, vereinfacht werden kann. Mathematisch zeigen wir, dass die ursprünglichen nichtlinearen Nebenbedingungen durch wenige (oder einzelne) Nebenbedingungen ersetzt werden können ohne den zulässigen Bereich zu ändern. Numerische Ergebnisse zeigen, dass diese Vereinfachung die MINLPs deutlich einfacher lösbar macht.

Der Algorithmus, welcher unser nichtkonvexes MINLP löst, erzeugt bei jeder Iteration eine konvexe Relaxation des zulässigen Bereichs. Viele Theorien und Experimente zeigten, dass eine engere konvexe Relaxation für den Branch-and-Bound-Ansatz ziemlich relevant ist.

In der Zielfunktion unseres Modells haben wir nichtlineare Funktionen in Form von bivariaten Polynomen mit Grad 3. Basierend auf der Standardkonstruktion der konvexen Relaxation wollen wir noch zusätzliche lineare Nebenbedingungen (gültige Schnitte), um die Relaxation enger zu machen. Wir untersuchen den Graphen von allgemeinen Polynomfunktionen, der auf einem Polytop definiert ist, und entwickeln eine Theorie, um die konvexe Hülle des Graphen zu beschreiben und um Halbräume zu finden, welche die konvexe Hülle enthalten. Danach definieren wir enge Halbräume, die die effizienten Halbräume bei Darstellung der konvexen Hülle bezeichnen. Für bivariate Polynomfunktionen mit Grad 3 werden Algorithmen entwickelt, um solche engen Halbräume zu finden. Nach dem Hinzufügen solcher engen Halbräume (lineare Nebenbedingungen) in das MINLP, zeigen unsere weiteren numerischen Berechnungen, dass sowohl die primale als die duale Schranke innerhalb derselben Zeitlimite definitiv verbessert werden.

Deutsch
URN: urn:nbn:de:tuda-tuprints-86575
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 500 Naturwissenschaften und Mathematik > 510 Mathematik
Fachbereich(e)/-gebiet(e): 04 Fachbereich Mathematik
04 Fachbereich Mathematik > Optimierung
04 Fachbereich Mathematik > Optimierung > Discrete Optimization
Hinterlegungsdatum: 09 Jun 2019 19:55
Letzte Änderung: 09 Jun 2019 19:55
PPN:
Referenten: Pfetsch, Prof. Dr. Marc E. ; Hemmecke, PD Dr. Raymond
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 16 April 2019
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen