Fortgeschrittene Algorithmen und Heuristiken zur Lösung quantifizierter gemischt - ganzzahliger linearer Programme

• Antragsteller: Professor Dr. Ulf Lorenz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 399489083

Bei klassischen Optimierungsproblemen wird davon ausgegangen, dass der Input für ein gegebenes Problem fest und zum Planungszeitpunkt bekannt ist. Die Berücksichtigung von Unsicherheit schon im Planungs- und Entscheidungsprozess ist für viele Anwendungen allerdings ein essentieller Aspekt. Es gibt verschiedene Arten in der Literatur, mit dieser Unsicherheit umzugehen, eine davon ist die Modellierung mit Hilfe von quantifizierten, ggfs. gemischt-ganzzahligen, linearen Programmen. Quantifizierte lineare Programme sind lineare Programme, bei denen die Variablen entweder Existenz- oder All-quantifiziert wurden. Sie können als Zweipersonen-Nullsummenspiel zwischen einem Existenz- und Allspieler, oder als Multistage-Optimierungsproblem unter Unsicherheit interpretiert werden. Lösungen von quantifizierten Programmen bilden so genannte Strategien für den Existenzspieler, die spezifiziert, wie er auf Aktionen des Allspielers - also Setzungen von Allvariablen - reagieren soll.Langfristiges Ziel ist die Entwicklung eines Werkzeugs zur Lösung Quantifizierter gemischt- ganzzahliger linearer Programme, welches im Stile von Cplex, Gurobi oder Scip einer breiten Öffentlichkeit den Zugang zu robusten Optimierungsproblemen öffnet. Auf dem Weg dahin wollen wir Lösungsverfahren für quantifizierte Programme entwickeln, verfeinern und theoretisch untermauern, um das mächtige Modellierungs-Werkzeug der quantifizierten gemischt-ganzzahligen linearen Programme auch für praxisrelevante Problemstellungen einsetzen zu können. Ein Schritt dorthin ist auch, dass wir den Löser Yasol öffentlich zur Verfügung gestellt haben. Wir erhoffen und erwarten, dass die Ergebnisse dieses Projektes weitreichende Auswirkungen sowohl auf Bereiche der Forschung, als auch auf praktische Anwendung haben, bei denen robuste Lösungen von Optimierungsproblemen erforderlich sind.Durch eine signifikante Erweiterung der quantifizierten Programme wollen wir zudem eine aktive Beeinflussung der Unsicherheitsmenge ermöglichen, wodurch die Modellierungsmöglichkeiten und somit die Anwendbarkeit in realen Problem deutlich gesteigert wird.

• DFG-Verfahren: Sachbeihilfen