Parametrisierte Algorithmik und "Programming by Optimization" - Parametergesteuerte Auswahl von Algorithmen für reale Daten

• Antragsteller: Dr. Sepp Hartung
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung in 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 258946267

Die parametrisierte Algorithmik entwickelt exakte Algorithmen für (NP-)schwere Berechnungsprobleme.Genauer werden FPT-Algorithmen (fixed-parameter tractable) für Parameter entwickelt, welche dann effizient auf Instanzen mit kleinem Parameterwert sind.Als Parameter dient dabei oft die Distanz zu effizient lösbaren Spezialfällen.Beispielsweise sind viele Graph-Probleme effizient lösbar auf speziellen Graphen, z.B. auf Bäumen.Da jedoch i. A. die Eingabe nicht aus Bäumen besteht, werden FPT-Algorithmen entwickelt, welche mit der Distanz zu Bäumen parametrisiert werden und deshalb effizient sind, wenn die Eingabe "nah" zu Bäumen ist.Eine Hauptmotivation für die Entwicklung von FPT-Algorithmen ist es, die hohe Effizienz und gute Qualität von heuristischen Algorithmen auf praktischen Instanzen zu verstehen und für die Entwicklung von (beweisbar) exakten Algorithmen zu nutzen.Die Lösungsgüte ist bei Heuristiken i. A. nicht garantiert, jedoch scheinen in praktischen Anwendungen "schwere" Instanzen kaum aufzutreten.Eine weitläufig akzeptierte Erklärung dafür ist, dass praktische Instanzen, je nach Anwendung aus der sie entstehen, gewisse Strukturen (z.B. die Nähe zu Bäumen) aufweisen, welche es erlauben, Heuristiken darauf zu optimieren.Mit dem Ziel solche Strukturen zu finden, wurden in der parametrisierten Algorithmik verstärkt strukturelle Parameter betrachtet.Das zentrale Ziel dieses Forschungsprojektes ist es, diese bislang hauptsächlich theoretischen FPT-Algorithmen für praktische Anwendungen zu erproben.Damit soll die Frage beantwortet werden, ob es durch die Betrachtung von FPT-Algorithmen für strukturelle Parameter gelingt, diejenigen Strukturen zu identifizieren, welche für die gute Leistung von Heuristiken "verantwortlich" sind.Bei der Entwicklung dieser Algorithmen stellt sich nun für eine konkrete Instanz das Problem, anhand der konkreten (strukturellen) Parameterwerte einen möglichst effizienten FPT-Algorithmus auszuwählen. Dieses "Auswahlproblem" wird dadurch erschwert, dass es meist verschiedene Variationen eines FPT-Algorithmus gibt. Weiterhin lassen sich diese auch oft "frei kombinieren" mit Datenreduktionsregeln, Berechnung von unteren Schranken, etc., wodurch sich eine Vielzahl von möglichen Konfigurationen ergibt. Um diese Probleme zu lösen, soll "Programming by Optimization" (PbO) angewendet werden. PbO ermöglicht es durch die Verwendung spezieller Programmierwerkzeuge eine automatische Optimierung des Programmcodes durchzuführen. Dabei ist es mittels spezieller Programmiersprachkonstrukte möglich, verschiedene Konfigurationen (versteckte Konstanten, austauschbare Programmteile) für die spätere Optimierung zu markieren. PbO bewährte sich bereits zur Optimierung von Programmen für NP-schwere Probleme wie "Integer Linear Programming" und "SAT Solving". Es soll gezeigt werden, dass durch PbO optimierte FPT-Algorithmen auf praktischen Instanzen mit der Effizienz von Heuristiken konkurrieren können.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: Kanada
• Gastgeber: Professor Dr. Holger Hoos