COmPwise: Computing Optimal Piecewise Linear Functions and Their Applications

Berechnung von optimalen stückweise linearen Funktionen und deren Anwendungen

Förderdauer: 1. Juni 2021 - 31. Mai 2025

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. 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 (nichtkonvexen) GGNL Optimierungsprobleme entwerfen, welche eine entsprechende Zerlegung erlauben, z.B. durch eine L-Struktur der Nebenbedingungsmatrix.