Algorithmen und Komplexitätsanalyse für Robuste Kombinatorische Optimierung

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

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Zur Lösung von Entscheidungsfindungsproblemen stehen inzwischen leistungsfähige und standardisierte algorithmische Werkzeuge zur Verfügung. Insbesondere bei der gemischt-ganzzahligen linearen Programmierung gibt es einen produktiven Kreislauf zwischen der Entwicklung neuer und anspruchsvoller Probleme, Lösungsmethoden und deren Umsetzung in kommerzieller und akademischer Software. Ein solcher Erfolg ist nur möglich, wenn die abstrakte Form der betrachteten Probleme wohldefiniert ist. Gleichzeitig fehlt diese Standardisierung bei Entscheidungsproblemen unter Unsicherheit weitgehend. Neben der Struktur der Menge der machbaren Lösungen müssen wir auch eines der vielen verfügbaren Entscheidungskriterien und Arten von Unsicherheitsmengen auswählen. Dies trägt dazu bei, dass die Landschaft der Benchmarking-Probleme, -Algorithmen und -Software sehr viel zerklüfteter ist. In diesem Projekt haben wir uns auf robuste kombinatorische Optimierungsprobleme konzentriert, die oft zur Klasse der schwierigen Probleme gehören. Um das Feld auf eine sicherere experimentelle Basis zu stellen, untersuchten wir verschiedene Methoden zur Konstruktion von harten Instanzen. Ein weit verbreiteter Standard ist die Auswahl von Parameterwerten aus einer Gleichverteilung. Mit einer breiteren Palette von Zufallsmethoden konnten wir Instanzen finden, die um mehrere Größenordnungen schwieriger zu lösen sind. Welche Methode zu wählen ist, hängt vom Entscheidungskriterium und natürlich von der Art der Unsicherheit ab. In den meisten Fällen können diese Instanzen durch die Anwendung eines Optimierungsmodells zur Modifizierung von Problemparametern noch schwieriger gemacht werden. Mit der Generierung von Instanzen ist das Problem der Reduzierung von Instanzen verbunden, um die wesentlichen Probleminformationen zu erhalten. Wenn zum Beispiel ein Szenario von einem anderen Szenario dominiert wird, kann es aus dem Problem entfernt werden. Wir haben dieses Szenarioaggregationsproblem als Optimierungsproblem formuliert, das eine Approximationsgarantie für die Qualität der Aggregation bietet. Dies führt zu einer Heuristik, die darauf basiert, ein großes Problem zunächst zu verkleinern, bevor es gelöst wird. Darüber hinaus haben wir datengesteuerte Methoden des maschinellen Lernens eingesetzt um Unsicherheitsmengen zu modellieren, die gut zu den historischen Daten passen, und um effektive Algorithmen auf der Grundlage einer Menge zuvor gelöster Problemen zu erlernen. Wir haben das derzeitige Wissen über Problemkomplexität erweitert, indem wir neue Arten von Unsicherheitsmengen und dynamische Entscheidungsprobleme mit mehr als einer Stufe untersucht und deren Komplexität bestimmt haben.

Projektbezogene Publikationen (Auswahl)

• On the recoverable robust traveling salesman problem. Optimization Letters, 10(7), 1479-1492.
  Chassein, André & Goerigk, Marc
  
• Robust Combinatorial Optimization with Locally Budgeted Uncertainty. Open Journal of Mathematical Optimization, 2, 1-18.
  Goerigk, Marc & Lendl, Stefan
  
• Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty. Journal of Combinatorial Optimization, 43(3), 497-527.
  Goerigk, Marc; Kasperski, Adam & Zieliński, Paweł
  
• Data-driven robust optimization using deep neural networks. Computers & Operations Research, 151, 106087.
  Goerigk, Marc & Kurtz, Jannis
  
• Optimal scenario reduction for one- and two-stage robust optimization with discrete uncertainty in the objective. European Journal of Operational Research, 310(2), 529-551.
  Goerigk, Marc & Khosravi, Mohammad
  
• Benchmarking problems for robust discrete optimization. Computers & Operations Research, 166, 106608.
  Goerigk, Marc & Khosravi, Mohammad
  
• On the complexity of robust multi-stage problems with discrete recourse. Discrete Applied Mathematics, 343, 355-370.
  Goerigk, Marc; Lendl, Stefan & Wulf, Lasse
  
• Data-driven prediction of relevant scenarios for robust combinatorial optimization. Computers & Operations Research, 174, 106886.
  Goerigk, Marc & Kurtz, Jannis