19.02.2020 Parametrisierte Algorithmen für Heuristiken: DFG fördert Forschungsprojekt der AG Algorithmik (Prof. Komusiewicz) im Umfang von 285.000 Euro

Viele praktisch motivierte Optimierungssprobleme etwa im Datenclustern oder in der Transportoptimierung können mutmaßlich nicht in annehmbarer Rechenzeit gelöst werden. Ein Ansatz um solchen schweren Problemen zu begegnen ist die parametrisierte Algorithmik. Diese versucht, effiziente Algorithmen dadurch zu erhalten, dass man die Struktur typischer Eingabedaten ausnutzt. Diese Struktur wird durch Parameter beschrieben, die von den Eingabedaten abhängen. Parametrisierte Algorithmen sind schnell, wenn diese Parameter kleine Werte annehmen. Einige parametrisierte Algorithmen können als Basis von State-of-the-Art Algorithmen für NP-schwere Probleme dienen. Dennoch werden in der Praxis vor allem Heuristiken wie lokale Suche und Greedyalgorithmen eingesetzt. Diese berechnen schnell gute, aber nicht unbedingt optimale Lösungen.

Das Projekt "Operationale Parametrisierung für Heuristiken (OPERAH)" soll untersuchen, inwiefern sich parametrisierte Algorithmen gewinnbringend in lokalen Suchverfahren und Greedyheuristiken einsetzen lassen. Im Zentrum der Untersuchungen stehen dabei ein operationaler Parameter. Dieser wird nicht durch die Eingabestruktur bestimmt, sondern vom Anwender gewählt. Der operationale Parameter beschreibt einen Trade-off zwischen höherer Laufzeit und besserer Lösungsgüte: Je höher der Parameterwert ist, desto besser ist die Lösung, aber desto größer wird die Laufzeit. Ein Anwender kann durch die Wahl des Parameterwerts die Laufzeit des Algorithmus bestimmen und erhält eine Lösung mit entsprechender Güte.

Im Einzelnen ist das Ziel, für mehrere praxisrelevante Optimierungsprobleme effiziente Algorithmen für die parametrisierte lokale Suche und das sogenannte Turbocharging von Greedyheuristiken zu entwickeln oder zu zeigen, dass solche Algorithmen nach aktuellem Ermessen nicht existieren. Die entwickelten Algorithmen sollen mit State-of-the-Art-Heuristiken verglichen werden. Dabei soll insbesondere auch der Trade-off zwischen Laufzeit und Lösungsgüte untersucht werden.

Die Deutsche Forschungsgemeinschaft (DFG) fördert das Projekt der AG Algorithmik (Prof. Komusiewicz) von 2020-2022 mit einem Betrag von 233.900 Euro zuzüglich 51.500 Euro Programmpauschale.