OWA Regret – Neue Methoden für die Entscheidungsfindung unter Ungewissheit

• Antragsteller: Professor Dr. Marc Goerigk
• Fachliche Zuordnung: Accounting und Finance ; Theoretische Informatik
• Förderung: Förderung von 2020 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 448792059

Entscheidungen müssen allgegenwärtig getroffen werden, aber nur selten sind alle Informationen verfügbar, um mit Sicherheit die beste Alternative bestimmen zu können. Entscheidungen unter Ungewissheit, bei denen nur mögliche Ergebnisse ohne Wahrscheinlichkeiten bekannt sind, treten zum Beispiel natürlich auf, wenn historische Daten zur Entscheidungsfindung zur Verfügung stehen.Die Entscheidungsfindung wird häufig weiter dadurch erschwert, dass nicht alle Alternativen explizit gelistet zur Verfügung stehen, sondern implizit durch Nebenbedingungen definiert sind. Zum Beispiel gibt es bei der Routenfindung bis zu exponentiell viele mögliche Wege von einem Start- zu einem gewünschten Zielort. Sie alle aufzulisten und zu bewerten würde zu lange dauern. In diesem Projekt werden solche Probleme betrachtet, bei denen jede Entscheidungsvariable den Wert 0 oder 1 annehmen kann (zum Beispiel, liegt eine Straße auf der Route oder nicht). Solche Probleme werden als kombinatorische Probleme unter Ungewissheit bezeichnet.Verschiedene Ansätze, welche Entscheidung in einem solchen Setting gewählt werden sollte, wurden bereits in der Literatur analysiert. Es stellt sich leider heraus, dass es aus axiomatischer Sicht kein eindeutig bestes Entscheidungskriterium existiert. Zwei häufig verwendete Kriterien sind min-max regret und ordered weighted averaging (OWA). Im ersten Ansatz wird zunächst für jedes mögliche Szenario ein bestmöglicher Zielfunktionswert bestimmt. Dann wird diejenige Alternative gewählt, bei der die größte Differenz zum besten Zielfunktionswert über alle Szenarios möglichst klein ist. Im zweiten Ansatz wird ein Gewichtungsvektor verwendet, der eine Kontrolle erlaubt, wie konservativ eine Entscheidung sein soll. Die Ergebniswerte einer Alternative über alle Szenarios werden sortiert, und der Gewichtungsvektor mit diesem sortierten Ergebnisvektor skalar multipliziert. Dieser Ansatz beinhaltet die Extreme der Entscheidung bezüglich dem schlimmsten Ergebniswert (robuste Optimierung), dem gemittelten Ergebnis und dem besten Fall.In diesem Projekt untersuchen wir eine Kombination dieser beiden Kriterien, bei der das OWA Krtierum angewandt wird auf den Vektor der Differenzen zu den besten Zielfunktionswerten. Das heißt, anstelle vom maximalen regret betrachten wir den allgemeineren und weniger konservativen OWA regret Ansatz. Diese Methode ist neu in der kombinatorischen Optimierung. Wir modellieren diesen Ansatz, untersuchen ihn auf Komplexität und Approximierbarkeit hin, entwicklen heuristische und exakte Lösungsverfahren, und bewerten ihn anhand realer Daten. Darüber hinaus erweitern wir den Ansatz von diskreten Szenariomengen auf intervallbasierte Szenarios.Da sowohl min-max regret als auch das OWA Kriterium aktive Forschungsfelder im Bereich der kombinatorischen Optimierung sind, werden die in diesem Projekt erzielten Ergebnisse auf breites Interesse in der Community stoßen und darüber hinaus neue Möglichkeiten zur Entscheidungsfindung öffnen.

• DFG-Verfahren: Sachbeihilfen