Approximation nichtlinearer Dynamiken in der gemischt-ganzzahligen Optimierung

• Applicant: Professor Dr. Alexander Martin
• Subject Area: Mathematics
• Term: from 2005 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 19288157

Ausgehend von konkreten Anwendungsfällen aus der Gasnetzoptimierung soll in diesem Projekt das Problem der Approximation nichtlinearer Funktionen mit Methoden der polyedrischen Kombinatorik gelöst werden. Im Mittelpunkt steht dabei die Modellierung nichtlinearer Funktionen, insbesondere partieller Differentialgleichungen, die aus komplexen Geometrien (z.B. Zusammentreffen mehrerer Leitungen an einem Knoten) oder zeitkritischen Dynamiken (z.B. Flussumkehr) entsteht. [...] Es müssen weitere polyedrische Untersuchungen angestellt werden. Dabei werden insbesondere solche Strukturen im Vordergrund stehen, die aus der Kopplung mehrerer stückweise linearer Funktionen über zeitliche und dynamische Beziehungen entstehen. Erkenntnisse, die aus diesen Studien gewonnen werden können, ergeben möglicherweise Einblicke in polyedrische Strukturen, deren Gültigkeit weit über den Kontext der Gasnetzoptimierung hinaus geht. Zur Elimination suboptimaler Teilbäume soll darüber hinaus eine Knotenheuristik entwickelt werden. Zum anderen sollen Sensitivitätsanalysen durchgeführt werden, mit deren Hilfe Aussagen über die Sensitivität diskreter Variablen hinsichtlich der Linearisierungsfehler getroffen werden können. Mit Hilfe dieser Erkenntnisse können in Verbindung mit den im Projekt entwickelten a-posteriori Fehlerschätzern adaptive Approximationen berechnet werden, die das Auffinden zulässiger Lösungen garantieren, wenn solche existieren. Ein dritte Herausforderung bildet die Integration nichtlinearer (konvexer) Löser in unseren Branch and Cut Algorithmus. Ein solches Verfahren kann in jedem Knoten des Branch and Bound Baums aufgerufen werden, um anstatt der linearen Relaxierung eine konvexe Relaxierung des aktuellen Teilproblems zu lösen. Dadurch wird eine Verschärfung der unteren Schranke des Zielfunktionals erzielt, was wiederum dazu führt, dass unzulässige Teilprobleme früher erkannt und der Optimalitätsbeweis schneller erbracht werden kann. Außerdem soll ein Ansatz zur Integration nichtlinearer Funktionen in gemischt-ganzzahlige Programme untersucht werden, der ohne die Einführung zusätzlicher Variablen auskommt und als reines Schnittebenenverfahren aufgefasst werden kann. Dabei handelt es sich um ein Verfahren aus dem Gebiet der Computergrafik, das dort zur Berechnung von Hüllkörpern verwendet wird. Am Ende steht eine Auswertung aller Algorithmen anhand realistischer Testszenarien, die uns von unserem Industriepartner zur Verfügung gestellt wurden, mit dem Ziel einer prototypischen Implementierung.

• DFG Programme: Research Grants
• Participating Person: Professor Dr. Jens Lang