Treewidth-Based Problem Solving: Neue Ansätze
Kombinatorisch harte Probleme lassen sich lösen, indem sie in Teilprobleme aufgeteilt werden. Für seine Arbeit an dieser Thematik wurde Dr. Markus Hecher dieses Jahr mit dem GI-Dissertationspreis ausgezeichnet. In einem Gastbeitrag schreibt er über seine Ergebnisse und neue Ansätze des „Treewidth-Based Problem Solving”.
In den frühen Kinderschuhen der Informatik hat man damit begonnen, wichtige, wiederkehrende Aufgabenstellungen (Probleme) anhand ihrer Komplexität zu klassifizieren, was vor allem dazu geführt hat, eine Partitionierung dieser in „praktisch lösbar“ und „eher nicht praktisch lösbar“ zu erhalten. Mittlerweile ist die Kategorie „eher nicht praktisch lösbar“ noch viel weiter unterteilt, genauer erforscht und es gibt neben schnellen Computerprogrammen (Solvern; zum Beispiel jku.at) inzwischen sogar allgemeine und gut untersuchte Methoden, um solche Probleme dennoch praktisch lösen zu können.
Eine dieser Methoden nennt sich dynamische Programmierung (youtube.com), welche dem Prinzip „Teile-und-Herrsche“ (divide and conquer) folgt. Dabei werden Probleme so lange in kleinere Teilprobleme zerlegt (aufgeteilt), bis diese praktisch lösbar sind, sodass die Teillösungen kombiniert werden können, um eine Gesamtlösung des ursprünglichen Problems zu erhalten. Nehmen wir als Beispiel eine Logistikaufgabe, bei der ein Transportnetzwerk zwischen Wien und Berlin bedient werden soll, um Waren zu bestimmten Lagerhallen auf der Strecke zu bringen. Aufgrund horrender Treibstoffpreise sollen kostengünstige Transportwege erreicht werden, indem Lösungen von Teilaufgaben über potenzielle Zwischenlager entsprechend kombiniert werden. Natürlich gibt es verschiedene Möglichkeiten, wie man diese Teilaufgaben erhält.
Ein sehr allgemeines Maß ist die sogenannte Baumweite (pacechallenge.org); ein struktureller Parameter, der die strukturelle Abhängigkeit von solchen Netzwerken misst. Dabei ist dieser Parameter sehr vielseitig einsetzbar und gibt in gewisser Weise den Abstand zu einfachen Strukturen, nämlich zu sogenannten Bäumen, welche zumeist strukturell einfachere Teilprobleme erlauben. Jetzt möchte man meinen, dass strukturell einfachere Teilprobleme (von kleiner Baumweite) immer einfacher zu lösen sind, als Teilprobleme größerer Baumweite. Nun, das kann man so allgemein nicht behaupten, denn zusätzlich hängt der erforderliche Lösungsaufwand der Teilprobleme auch immer von der Art des Problems ab. So gibt es beispielsweise Fragestellungen, bei denen sich viele Forschende einig sind, dass sie sehr viel aufwändiger zu lösen sind, als das oben erwähnte Logistikproblem. Wie verhalten sich denn nun strukturelle Abhängigkeit und Lösungsaufwand zueinander und was genau ist jetzt mein Beitrag?
Mein Forschungsthema befasst sich mit dem Lösen schwieriger bzw. kombinatorisch harter Probleme durch Aufteilung, bei Verwendung struktureller Eigenschaften wie der Baumweite. Im Konkreten konnte ich für eine Familie an kanonischen Problemen beweisen, dass unter üblichen Annahmen in der Komplexitätstheorie für jedes dieser Probleme ein gewisser Teilproblemlösungsaufwand in der Baumweite notwendig ist (youtu.be). Eine Bestätigung dieser Vermutung ist eigentlich seit beinahe 20 Jahren offengeblieben. Dabei habe ich einen neuen Ansatz entwickelt, um gezielt hohe strukturelle Abhängigkeit in der Form von Baumweite gegen höheren Teilproblemlösungsaufwand (und retour) zu tauschen. Das hat aber auch weitreichende Konsequenzen für eine Vielzahl an Problemen in der Logik, Wissensrepräsentation und der Künstlichen Intelligenz. Es hat sich gezeigt, dass mein Ansatz zu einer Vielzahl neuer Resultate (untere Laufzeitschranken) und einer Klassifikation, die Probleme entsprechend des Teilproblemlösungsaufwandes bei Verwendung von Baumweite einteilt, führen.
Alles nur theoretisch, meinen Sie? Eigentlich nicht! Ich habe des Weiteren noch konkrete Ansätze gebaut, wie man aufwändige Probleme auf diese Art auch praktisch lösen kann, und das funktioniert noch dazu erstaunlich gut. Kanonische Probleme in der Aussagenlogik (Zählprobleme, mccompetition.org) beim quantitativen Schließen können damit bis zu Baumweiten von ca. 200 praktisch gelöst werden, was in etwa einem worst-case Aufwand von 2^200 entspricht. Aufwändigere Erweiterungen davon können bis Baumweite von ca. 100 gelöst werden. Allerdings wird hier bereits im Allgemeinen ein Aufwand von 2^2^100 erwartet. Mittels einer hybriden Technik können bestehende Solver substanziell erweitert und verbessert werden, indem strukturelle Abhängigkeiten gezielt ausgenutzt werden. Man sieht also, dass entsprechende Forschung nicht nur wesentliche Beiträge zur Klassifikation von Problemen liefern kann. In weiterer Folge kann dies zu neuen, kompetitiven Lösungsansätzen führen, sodass die theoretische Klassifikation bereits entsprechende Erwartungen andeutet bzw. Erfolgsaussichten bereitstellt. Für mehr Details, verweise ich auf eine Kurzfassung in englischer Sprache (arxiv.org) sowie auf die Dissertation (tuwien.at) und Folgearbeiten (tuwien.ac.at).
Dieser Beitrag erschien in unserem Newsletter GI-Radar, der alle zwei Wochen erscheint und viele weitere spannende Einblicke in die Informatik bietet. Alle Ausgaben gibt es hier zum Nachlesen.
