Operationale Parametrisierung für Heuristiken (OPERAH)

• Antragsteller: Professor Dr. Christian Komusiewicz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 428493315

Viele praktisch motivierte Berechnungsprobleme etwa im Datenclustern oder in der Transportoptimierung sind NP-schwer. Daher können diese Probleme nach aktuellem Ermessen im Allgemeinen nicht effizient gelöst werden. Ein theoriegetriebener Ansatz um dieser algorithmischen Schwierigkeit zu begegnen ist die parametrisierte Algorithmik. Diese versucht, effiziente Algorithmen dadurch zu erhalten, dass man die Struktur typischer Eingabedaten ausnutzt. Diese Struktur wird durch problemspezifische 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 sie in der Praxis, in der vor allem Heuristiken Anwendung finden, selten eingesetzt. Zwei wichtige heuristische Verfahren sind lokale Suche und Greedyalgorithmen.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 steht dabei ein sogenannter operationaler Parameter. Dieser wird im Gegensatz zum Standardvorgehen in der parametrisierten Algorithmik nicht durch die Struktur der Eingabe bestimmt wird, sondern vom Anwender selbst 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.Durch diese Art der Parametrisierung soll ein Nachteil der parametrisierten Algorithmen, zu große Parameterwerte in realistischen Eingabeinstanzen, abgeschwächt werden. So soll die Arbeit in diesem Projekt die Praxisrelevanz der parametrisierten Algorithmik weiter erhöhen. 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 implementiert und experimentell mit State-of-the-Art-Heuristiken verglichen werden. Dabei soll insbesondere auch der oben beschriebene Trade-off zwischen Laufzeit und Lösungsgüte untersucht werden.

• DFG-Verfahren: Sachbeihilfen