Designing a system for experimental analysis and visualization of dynamic programming on tree decompositions

Abstract

Um schwere Probleme lösen zu können, gewann das Konzept der dynamischen Programmierung (DP) auf Baumzerlegungen in den letzten Jahren im Forschungsbereich der Informatik immer mehr an Bedeutung. Da das Verständnis und die Verbesserungen von Zerlegungsansätzen und DP Konzepten aufgrund der Komplexität der Algorithmen, der großen Datenmengen und der Schwere der Probleme eine enorme Herausforderung darstellen, wird im Rahmen dieser Diplomarbeit ein Tool entwickelt, um Systeme, die DP auf Baumzerlegungen anwenden, analysieren zu können. Bestehende Systeme bieten keine Möglichkeit um den kompletten DP-Prozess - von der Instanz, über die Baumzerlegung bis hin zur Berechnung, welche durch die Anwendung spezieller Algorithmen auf jeden Knoten der Baumzerlegung entsteht - zu analysieren. Im Speziellen wird der Ansatz des BEB-basierten DP auf Baumzerlegungen betrachtet, welcher das Konzept von DP mit dem Abbilden der Informationen anhand von Binären Entscheidungsbäumen (BEB) verbindet. Um komplexe Probleme lösen zu können, liegt unser Bestreben zusammenfassend im Design und in der Entwicklung eines Tools um Systeme, welche BEB-basierte DP auf Baumzerlegungen anwenden, zu analysieren. Mithilfe der Untersuchung vorhandener Visualisierungskonzepte und einer Analyse der technischen Anforderungen entwickeln wir DecoVis, um - neben der Visualisierungsmöglichkeit von Instanzen, Baumzerlegungen und Berechnungen - mehrere Analysemöglichkeiten für DP Systeme anzubieten. Die Analysemöglichkeiten umfassen unter anderem das Erstellen eines Statistik-Reports, das Hervorheben von Metadaten-Informationen oder die Animation der Ausführung von Algorithmen. Um unterschiedliche Systeme, die DP auf Baumzerlegungen anwenden (dynBDD, D-FLAT, D-FLAT 2 und Sequoia), bezüglich Leistungsfähigkeit und Stabilität vergleichen zu können, werden mehrere Benchmark-Tests erzeugt und deren Resultate analysiert. Die Probleme 3-Colorability, Stable Extension, Hamiltonian Cycle und Preferred Extensions werden durch die Benchmark-Tests abgedeckt. Unterschiedlichste Verhalten von Tools, welche BEB-basierte DP auf Baumzerlegungen anwenden, entstehen durch die Ausführung der Systeme mittels verschiedenster Optionen und Einstellungen. Anhand der Analyse dieser unterschiedlichen Systemverhalten untersuchen wir die Anwendung von DecoVis im Praxiseinsatz. In weiterer Folge vergleichen wir unterschiedliche Konzepte von Algorithmen und Variabelordnungen in BEBs anhand speziell gewählter Instanzen aus den Resultaten der Benchmark Tests.

The concept of dynamic programming (DP) on tree decompositions (TDs) has emerged in recent years as an important research field in computer science for solving hard problems efficiently. Since the understanding and improvements of decomposition approaches and DP concepts represent an enormous challenge due to complex algorithms, large amount of data and the hardness of problems, we put the focus on the development of a tool used for the analysis of systems applying DP on TDs. Moreover, recent systems have failed to address the possibility for analyzing the entire dynamic programming process from the instance, over the tree decomposition to the computation that is resulting from the application of specific algorithms on each TD node. In particular, the approach of BDD-based DP on TDs is considered, that combines the concept of DP with the storage of information by means of Binary Decision Diagrams (BDDs). In summary, our attempt is to design and develop a tool for analyzing systems applying BDD-based DP on TDs for solving complex problems. For this purpose we develop DecoVis, a system that provides - beside the visualization of instances, tree decompositions and computations - several possibilities for analyzing DP systems such as statistic report generation, emphasis of particular metadata information or algorithm execution animation. In order to compare various systems applying DP on TDs (dynBDD, D-FLAT, D-FLAT 2 and Sequoia) regarding performance and stability, several benchmark tests are generated and the results are analyzed. The benchmark tests cover the problems 3-Colorability, Stable Extension, Hamiltonian Cycle and Preferred Extensions. Furthermore, we examine the usage of DecoVis in practice by analyzing different behaviors of various options and settings of systems applying BDD-based DP on TDs. Based on specific instances that are selected from results of benchmark tests, we compare different algorithm concepts and variable orders in the BDDs.