HYPAR - Hybrides Parametrisiertes Problemlösen in der Praxis

Eine zentrale Herausforderung in der Informatik ist das Lösen schwerer Berechnungs- probleme. Ein konkreter Ansatz in diesem Zusammenhang verfolgt die Idee der Zerlegung der Probleminstanz in kleinere Bestandteile, die Schritt für Schritt gelöst werden, um schließlich mittels geeigneter Kombination dieser Teillösungen zu einer Lösung des Gesamtproblems zu kommen. Als Beispiel sei das Färben von Landkarten erwähnt, wo man mit einer begrenzten Anzahl von Farben die Länder so einfärben möchte, dass sich benachbarte Länder durch verschiedene Färbungen abgrenzen. Typischerweise löst man dieses Problem so, dass man zuerst einzelne Regionen, z.B. Skandinavien, Osteuropa, den Balkan, etc., unabhängig voneinander einfärbt und dann überprüft, ob sich diese Lösungen auch zu einer gültigen Färbung der gesamten Europalandkarte zusammenfassen lassen. Eine Ausprägung dieser Methode ist als dynamische Programmierung mittels Baumzerlegung bekannt, und ihre Laufzeit hängt von einem speziellen Parameter ab, der durch die maximale Größe eines Teilproblems gegeben ist, wobei sich die Teilprobleme duch entsprechende Zerlegungen ergeben. Daher gilt als Faustregel, dass kleinere Teilprobleme schneller zu Lösungen führen. Diese theoretischen Überlegungen spiegeln sich in der Praxis jedoch nicht notwendigerweise wider, da eine gewisse Balance zwischen dem Aufwand zum Lösen der Teilprobleme, und der Kombination dieser Teillösungen zu berücksichtigen ist. Insbesonders zeigt sich der Effekt, dass größere Teilprobleme weniger Schnittstellen zueinander haben, was die Kombination der Teillösungen weniger aufwändiger macht. Dies kann sogar den höheren Aufwand, der nun zum Lösen der Teilprobleme notwendig ist, wettmachen. Unsere Arbeitshypothese ist, dass man sich diesen Effekt zunutze machen kann, um schnellere Algorithmen zu entwicklen, insbesonders unter der Voraussetzung, dass man für das Lösen der Teilprobleme bereits bestehende Systeme nutzt. Folgerichtig nennen wir unseren Ansatz hybrid, da er sich für das Lösen der Teilprobleme anderer Techniken bedient als die klassische dynamische Programmierung, die wir lediglich für die Kombination von Teillösungen heranziehen. Im Rahmen des Projekts wollen wir ein besseres Verständnis dafür gewinnen, welche Formen von Zerlegungen für diesen Ansatz bestgeeignet sind, und auch entsprechende Methoden zur Generierung solcher Zerlegungen entwickeln. Schließlich soll unser neue Ansatz auf zahlreiche klassische Probleme der Informatik angewandt und seine Effizienz getestet werden.

Eine zentrale Herausforderung in der Informatik ist das Lösen schwerer Berechnungs-probleme. Ein konkreter Ansatz in diesem Zusammenhang verfolgt die Idee der Zerlegung der Probleminstanz in kleinere Bestandteile, die Schritt für Schritt gelöst werden, um schließlich mittels geeigneter Kombination dieser Teillösungen zu einer Lösung des Gesamtproblems zu kommen. Als Beispiel sei das Färben von Landkarten erwähnt, wo man mit einer begrenzten Anzahl von Farben die Länder so einfärben möchte, dass sich benachbarte Länder durch verschiedene Färbungen abgrenzen. Typischerweise löst man dieses Problem so, dass man zuerst einzelne Regionen, z.B. Skandinavien, Osteuropa, den Balkan, etc., unabhängig voneinander einfärbt und dann überprüft, ob sich diese Lösungen auch zu einer gültigen Färbung der gesamten Europalandkarte zusammenfassen lassen. Eine Ausprägung dieser Methode ist als dynamische Programmierung mittels Baumzerlegung bekannt, und ihre Laufzeit hängt von einem speziellen Parameter ab, der durch die maximale Größe eines Teilproblems gegeben ist, wobei sich die Teilprobleme durch entsprechende Zerlegungen ergeben. Unsere Arbeitshypothese ist, dass es in der Praxis aber notwendig ist auch größerer Teilprobleme in Kauf zu nehmen um schnellere Algorithmen zu entwickeln, insbesonders unter der Voraussetzung, dass man für das Lösen der Teilprobleme bereits bestehende Systeme nutzt. Wir konnten diesen Effekt in verschiedenen Anwendungsbereichen demonstrieren, insb. im Bereich der Aussagenlogik und der Logikprogrammierung. Für letztere konnten wir auch noch ein zusätzliches Problem lösen, nämlich die Vermeidung des sogenannten Grounding-Bottlenecks. Hierfür haben wir eine Methodik entwickelt die zum Teil auch auf obengenannten Struktureigenschaften zurückgreift.