Erweiterung mathematischer Optimierungsmethoden zur Lösung PSPACE-vollständiger Probleme mit Hilfe quantifizierter linearer Programme

• Applicant: Professor Dr. Ulf Lorenz
• Subject Area: Mathematics
• Term: from 2011 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 194664946

Bei klassischen Optimierungsproblemen wird davon ausgegangen, dass der Input für ein gegebenesProblem fest und zum Planungszeitpunkt bekannt ist. In der Praxis stößt man jedoch häufig aufSituationen, bei denen ein Teil dieser Daten mit Unsicherheit behaftet ist und lediglich Schätzungenbekannt sind. Viele interessante Optimierungsprobleme werden PSPACE-vollständig, sobald manauch nur auf einfachste Weise Unsicherheit in die Beschreibung der Inputdaten aufnimmt. Es gibt diverse Ansätze, die im Gebiet der Optimierung unter Unsicherheit erforscht werden. Relativ unerforscht sind jedoch die Möglichkeiten, die quantifizierte Erweiterungen von linearen Programmeneröffnen, wie sie von Subramani vorgestellt wurden. So genannte Quantifizierte lineare Programme(QLPs) sind lineare Programme, bei denen die Variablen existenz- oder allquantifiziert sein können.Bei QLPs geht man davon aus, dass die Variablen kontinuierlich gewählt werden dürfen. QLPs, beidenen alle Variablen ganzzahlig sein müssen, werden QIPs (Quantifizierte Integer Programme)genannt. Letztere sind für diesen Antrag von besonderem Interesse, da sie die Klasse PSPACEbeschreiben. Ziel der Bemühungen ist es, Methoden und Erkenntnisse der mathematischenOptimierung anzuwenden und zu erweitern, so dass sie zur Lösung von QIPs und QLPs genutztwerden können. Es soll erforscht werden, inwieweit sich quantifizierte lineare Programme eignen,interessante Problemstellungen der Praxis zu beschreiben und inwieweit sich Lösungsverfahrenangeben lassen, die zu ähnlich eindrucksvollen Ergebnissen führen, wie es die MIP-Löser für imGrunde NP-vollständige Probleme der Praxis vormachen.

• DFG Programme: Research Grants