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

Fast jedes Entscheidungsproblem ist von Unsicherheit betroffen: Wie plane ich am besten, wenn ich die Zukunft nicht genau kenne? Ein relativ junger Ansatz, Probleme dieser Art zu behandeln, ist die robuste Optimierung. Wir nehmen an, dass alle möglichen und relevanten Ergebnisse der unsicheren Daten in einer Menge gesammelt wurden (die Unsicherheitsmenge). Eine robuste Lösung ist dadurch gekennzeichnet, dass sie im schlimmsten Fall aus der Unsicherheitsmenge eine nicht schlechtere Performance zeigt als jede andere mögliche Lösung. Während dieser Ansatz zunächst zu konservativ scheint, lässt sich der Grad der Robustheit in der Anwendung dadurch ändern, dass die Größe der Unsicherheitsmenge angepasst wird.Die robuste Optimierung wurde bereits erfolgreich in zahlreichen praktischen Anwendungen eingesetzt, von Flugplanung bis zur logistischen Versorgung im Katastrophenfall. Wir konzentrieren uns hier auf die Klasse der kombinatorischen Probleme, wo jede Entscheidungsvariable entweder 0 oder 1 ist. Die meisten robusten Probleme dieser Art gehören der Klasse der schweren Optimierungsprobleme an. Entsprechend zahlreiche Algorithmen sind bereits entwickelt worden, doch ist deren Vergleich schwierig, weil es keinen einheitlichen Satz an Problem-Instanzen gibt, die für einen Vergleich genutzt werden können. Zudem sind Verfahren nicht frei verfügbar und müssen immer wieder neu implementiert werden.Im besten Fall befruchtet sich experimentelle und theoretische Arbeit gegenseitig: Die aus Experimenten gewonnenen Erkenntnisse machen eine verbesserte Komplexitätsanalyse möglich und führen zu verbesserten Algorithmen. Die schwierige experimentelle Situation in der robusten kombinatorischen Optimierung blockiert diesen Kreislauf (den algorithm engineering cycle). Entsprechend bleiben viele Komplexitätsergebnisse nur oberflächlich und entsprechen nicht praktischen Beobachtungen. Die fehlenden Benchmark Probleme bedeuten zudem, dass Algorithmen nicht hinreichend weiter entwickelt werden können.Die Vision dieses Forschungsvorhabens ist es, die Blockade im Kreislauf zu lösen und so den Weg zu erfolgreicher und effizienter weiterer Forschung im Gebiet der robusten kombinatorischen Optimierung zu ebnen. Wir erzeugen einen Benchmark aus sowohl künstlichen (schweren) wie realistischen Probleminstanzen, der über eine zu diesem Zweck eingerichtete website frei verfügbar gemacht wird. Basierend auf diesen Probleminstanzen wird die Komplexitätsanalyse verfeinert und neue, effizientere Algorithmen entwickelt. Unsere Verfahren werden durch eine Code-Bibliothek ebenfalls öffentlich zugängig gemacht.Der Antragssteller und der Mercator Fellow haben entscheidende Erfahrung in allen zu diesem Vorhaben nötigen Bereichen. Indem der Kreislauf zweimal durchlaufen wird, ist das Ergebnis eine neue toolbox bestehend aus Code, neuen Ansätzen der Komplexitätsanalyse, Algorithmen und Benchmark Problemen, die einen völlig neuen Ansatz auf das Forschungsgebiet gestatten.

• DFG-Verfahren: Sachbeihilfen