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.