Robuste multikriterielle Optimierung: Analyse und Lösungsverfahren
Theoretische Informatik
Zusammenfassung der Projektergebnisse
In Industrie und Gesellschaft auftretende Optimierungsprobleme sind so gut wie immer durch unterschiedliche Zielvorstellungen und durch Unsicherheiten gekennzeichnet. Im Verkehr möchte man beispielsweise Reisezeiten, Kosten und CO2-Ausstoß minimieren. Bei der Planung sind u.a. die zukünftige Nachfrage und die Entwicklung der Treibstoffpreise unsicher. Solche Probleme fallen in das in den letzten 15 Jahren entstandene Gebiet der robusten multikriteriellen Optimierung, in dem verschiedene Konzepte zur Definition einer „robusten Paretolösung“ entwickelt werden. Algorithmen zum Auffinden solcher Lösungen sowie theoretische Ergebnisse zu deren Eigenschaften gibt es aber noch wenig. In dem vorliegenden Projekt ist es uns einerseits gelungen, die Theorie zur robusten multikriteriellen Optimierung weiterzuentwickeln. Andererseits konnten wir praktisch umsetzbare Lösungsverfahren für die sich ergebenden Probleme entwickeln. In der Theorie gelang es, mittels mengentheoretischer Konzepte, die verschiedenen vorliegenden Konzepte zu evaluieren und ihre unterschiedlichen Eigenschaften herauszuarbeiten. Damit konnte die Aussage, dass so genannte lightly robust effiziente Lösungen einen guten Kompromiss zwischen minmax robust effizienten Lösungen und den nominalen Lösungen darstellen, erstmals analytisch bestätigt werden. Es wurde außerdem ein „Preis“ der multikriteriellen Robustheit definiert und gezeigt, wie er in der Praxis genutzt werden kann. In einer weiteren Arbeit konnten wir das Konzept der Robustheitslücke auf mehrkriterielle Probleme übertragen und diese Lücke durch obere und untere Schranken theoretisch und algorithmisch abschätzen. Die von uns entwickelten Lösungsverfahren kombinieren Verfahren aus der robusten und der multikriteriellen Optimierung in zwei unterschiedlichen Ansätzen. In dem ersten Ansatz interpretiert man das Problem als multikriterielles Problem mit einer Zielfunktion, die eine Maximierung bezüglich der Unsicherheit beinhaltet. Das führt zu einer Weiterentwicklung des bekannten Dichotomic-Search-Verfahrens. Im zweiten Ansatz interpretiert man das Problem alternativ als robustes Problem und wendet ein Schnittebenenverfahren darauf an. Dazu musste dieser aus der robusten Optimierung bekannte Ansatz auf mehrkriterielle Probleme verallgemeinert werden. Zusätzlich entwickeln wir einen auf Dualitätstheorie zurückgreifenden Ansatz für Probleme, die linear über der Unsicherheitsmenge sind. Alle drei Verfahren wurden implementiert und experimentell verglichen. Als typische Anwendungen wurden ganzzahlige Optimierungsprobleme als Testprobleme für die Verfahren gewählt. Außerdem wurde ein Portfolio-Problem analysiert und anhand unserer Ansätze untersucht. Zusätzlich ergaben sich verschiedene Beziehungen zur mengenwertigen Optimierung, die sowohl bei der Evaluierung von robust effizienten Lösungsmengen als auch bei der Entwicklung der Schranken für die Schnittebenenverfahren genutzt wurde.
Projektbezogene Publikationen (Auswahl)
-
On the p-hub interdiction problem. Computers & Operations Research, 124, 105056.
Ullmert, Thomas; Ruzika, Stefan & Schöbel, Anita
-
The price of multiobjective robustness: Analyzing solution sets to uncertain multiobjective problems. European Journal of Operational Research, 291(2), 782-793.
Schöbel, Anita & Zhou-Kangas, Yue
-
The point-based robustness gap for uncertain multiobjective optimization. Optimization, 73(6), 1897-1931.
Krüger, Corinna; Schöbel, Anita; Fritzen, Lena & Wiecek, Margaret M.
-
“Recoverable Robust Periodic Timetabling”. In: 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 115 (2023), pp. 9:1–9:16.
V. Grafe & A. Schöbel
-
Approaches for biobjective integer linear robust optimization. European Journal of Operational Research.
Chlumsky-Harttmann, Fabian; Schmidt, Marie & Schöbel, Anita
