Berechnung von optimalen stückweise linearen Funktionen und deren Anwendungen

• Antragsteller: Professor Steffen Rebennack, Ph.D.
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 445857709

Stückweise lineare (SWL) Funktionen bestehen aus affinen Segmenten. Daher können SWL Funktionen in praktischen Anwendungen leicht interpretiert und gehandhabt werden. Weil SWL Funktionen mittels gemischt-ganzzahligen linearen (GGL) Techniken modelliert werden können, sind diese für Optimierungsalgorithmen besonders interessant. SWL Funktionen sind weit verbreitet und werden in verschiedenen Disziplinen angewendet. In der mathematischen Optimierung werden SWL Funktion zur Approximation von nichtlinearen Funktionen verwendet, um gemischt-ganzzahlige nichtlineare (GGNL) Modelle mittels GGL Techniken lösen zu können. Wir wollen Beiträge in zwei Richtungen leisten. Erstens, für die Berechnung von SWL Funktion wollen wir existierende Methoden und Modelle verbessern und erweitern und neue Lösungsalgorithmen entwerfen. Zweitens wollen wir SWL Funktionsapproximationen in die Benders Dekomposition integrieren um einen exakten Algorithmus für GGNL Probleme spezieller Struktur zu entwerfen. Die erste Richtung beschäftigt sich mit Methoden zur Berechnung von SWL Funktionen sowohl für Datenpunkte als auch für kontinuierliche Funktionen, wobei wir uns auf exakte Verfahren beschränken. Dafür wollen wir die Rechenbarkeit der existierenden Methoden für eindimensionale Funktionen verbessern. Dies wollen wir durch Stärkung der Modelle und dem Design spezialisierter Algorithmen erreichen. Hiebei wollen wir logarithmische Reformulierungen untersuchen und wir wollen ausnutzen, dass konvexe SWL Funktionen wesentlich leichter zu berechnen sind. Dies wollen wir algorithmisch für DC Funktionen verwenden; eine sehr mächtige Funktionenklasse, welche z.B. alle zweifach stetig differenzierbaren Funktionen umfasst. Algorithmisch bietet sich eine kombinatorische Benders Dekomposition an, um die spezielle Struktur der Big-M Bedingungen in den existierenden exakten Modellen auszunutzen und starke Optimalitätsschnitte zu berechnen. Für zweidimensionale Funktionen wollen wir die ersten exakten Modelle entwickeln – bisher sind nur Heuristiken bekannt. Hierbei ist unsere Idee, die neuesten Umformulierungstricks aus der eindimensionalen Funktionsapproximation zu verwenden. In der zweiten Richtung wollen wir Benders Algorithmen für solche (nicht-konvexen) GGNL Optimierungsprobleme entwerfen, welche eine entsprechende Zerlegung erlauben, z.B. durch eine L-Struktur der Nebenbedingungsmatrix. Hierfür wollen wir drei unterschiedliche Verfahren aus zwei Disziplinen verwenden: Die GGNL Teilprobleme werden dynamisch mittels SWL Funktionen approximiert um GGL Probleme zu erhalten. Stützende Optimalitätsschnitte werden dann mittels der neuesten Ergebnisse aus der stochastischen GGL Optimierung berechnet. Da diese allerdings binäre Zustandsvariablen voraussetzen, müssen diese erst durch binär-Erweiterung approximiert werden. Um einen exakten Dekompositionsalgorithmus zu erhalten müssen alle Approximationsfehler genau kontrolliert werden.

• DFG-Verfahren: Sachbeihilfen