Forschungsprojekte
Aktuelle Projekte
OWA Regret - Neue Methoden für die Entscheidungsfindung unter Ungewissheit
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.
| Projektleitung an der Universität Passau | Prof. Dr. Marc Goerigk (Lehrstuhl für Business Decisions und Data Science) |
|---|---|
| Laufzeit | 01.07.2021 - 30.09.2024 |
| Website | https://gepris.dfg.de/gepris/projekt/448792059?context=projekt&task=showDetail&id=448792059& _blank |
| Mittelgeber |  DFG - Deutsche Forschungsgemeinschaft > DFG - Sachbeihilfe |
| Projektnummer | 448792059 |
Abgeschlossene Projekte
NIMROp: Neue Unsicherheitsmodelle für die Robuste Optimierung
Die Zukunft ist unbekannt und Prognosen werden verwendet, Messdaten sind ungenau, und Störungen können einen Plan unbrauchbar machen. Selten sind alle Informationen über das Entscheidungsproblem verfügbar.
Optimierungsmodelle und -algorithmen sind zu mächtigen Werkzeugen für die Entscheidungsfindung und darüber hinaus geworden. Klassische Methoden sind für den optimistischen Fall entwickelt worden, dass alle Informationen über das Entscheidungsproblem verfügbar sind. In der Praxis ist das nur selten der Fall. Robuste Optimierung (RO) bietet einen Ansatz, um Entscheidungen zu treffen, bei denen solche Unsicherheiten im Vorfeld berücksichtigt werden. Im Mittelpunkt der RO steht dabei das Modell der Unsicherheit. In den meisten RO-Ansätzen muss eine Lösung alle Szenarien berücksichtigen, die in einer Unsicherheitsmenge enthalten sind, ohne Verwendung von Wahrscheinlichkeiten. Dies kann auch als ein Spiel mit zwei Spielern gesehen werden, bei dem ein Gegner versucht, eine Lösung mit den durch die Unsicherheitsmenge gegebenen Möglichkeiten zu stören. Das bedeutet, dass Lösungen zu konservativ werden, wenn die Unsicherheitsmenge zu groß ist. Die Wahl der Unsicherheit wird zusätzlich dadurch erschwert, dass sie die Komplexität des resultierenden RO-Problems beeinflusst. Eine komplexe Unsicherheitsmenge kann zu Optimierungsproblemen führen, die nicht in angemessener Zeit gelöst werden können. Aus diesen Gründen ist eine Kernliste von Unsicherheitsmengen, die einen guten Kompromiss zwischen Modellierungsleistung und Komplexität bieten, eine treibende Kraft für die Forschung in RO. Der vielleicht populärste Ansatz ist die budgetierte Unsicherheit, bei der eine einzelne Nebenbedingung die Größe der möglichen Abweichung für unsichere Koeffizienten steuert. Bei der Betrachtung eines Problems der Personaleinsatzplanung wurde uns klar, dass keines der derzeit verfügbaren Unsicherheitsmodelle geeignet ist, Situationen zu behandeln, bei der das Ziel des Gegners darin besteht, so viele Jobs wie möglich unter einer Budgetbeschränkung zu stören. Wir bezeichnen dies als ein RO-Problem mit bounded interdiction. Das Ziel dieses 18-monatigen Projekts ist es, eine detaillierte Studie über RO mit bounded interdiction durchzuführen. Wir analysieren die Komplexität solcher Probleme, leiten Approximationsergebnisse ab, entwickeln kompakte Modellformulierungen und exakte Lösungsalgorithmen, erweitern bounded interdiction auf allgemeinere Situationen wie z.B. zweistufige Probleme und evaluieren den Ansatz auf realen Datensätzen. Die Auswirkungen, die die Einführung von budgetierten Unsicherheiten auf Forschung und Anwendung im Bereich der RO hatte, zeigt das Potential guter Unsicherheitsmodelle. Mit dem vorgeschlagenen Ansatz erweitern wir die Möglichkeiten der RO, um eine breitere Klasse von Entscheidungsfindungsproblemen zu behandeln, und eröffnen gleichzeitig einen interessanten Weg für weitere methodologische Forschung.
| Projektleitung an der Universität Passau | Prof. Dr. Marc Goerigk (Lehrstuhl für Business Decisions und Data Science) |
|---|---|
| Laufzeit | 01.12.2022 - 31.01.2024 |
| Website | https://gepris.dfg.de/gepris/projekt/459533632?context=projekt&task=showDetail&id=459533632& _blank |
| Mittelgeber | DFG - Deutsche Forschungsgemeinschaft > DFG - Sachbeihilfe |
| Projektnummer | 459533632 |
Diese Seite teilen
