[Back]

B. Bliem:
"Decompose, guess and check : declarative problem solving on tree decompositions";
Supervisor: S. Woltran, R. Pichler; Institut für Informationssysteme, 2012; final examination: 11-19-2012.

Many practically relevant problems are infeasible for large instances. However, often they become tractable when only instances where a certain parameter is bounded by a constant are considered.
Especially treewidth has proven to be an attractive parameter because it applies to many different problems. Bounded treewidth leading to tractability can frequently be exploited by dynamic programming on a tree decomposition of the original instance. Until now, implementing such algorithms, however, has usually been quite intricate which is due to the lack of supporting tools that offer an adequate language for conveniently specifying such algorithms.
In this thesis, we therefore present a method for problem solving called Decompose, Guess & Check that enables the user to specify such algorithms in a declarative way. For this, we employ Answer Set Programming - a logic programming formalism which supports a programming paradigm called Guess & Check and is recognized for its capability to express hard problems quite succinctly. Using Answer Set Programming as a language to specify the problem-specific parts of dynamic programming algorithms, Decompose, Guess & Check benefits from efficient solvers as well as from a rich language that allows for easily readable and maintainable code.
We conduct an analysis of the proposed approach that shows it to be powerful enough to efficiently solve a large class of problems on instances of bounded treewidth. Furthermore, we present a software framework called D-FLAT that provides this method and makes rapid prototyping of algorithms on tree decompositions possible. We finally apply Decompose, Guess & Check to a selection of different problems to illustrate the versatility of the approach.
Because instances in practical applications often exhibit small treewidth, our approach has great practical relevance. For many problems that are hard in general, Decompose, Guess & Check is thus a promising candidate for solving large instances which have so far been out of reach for existing Answer Set Programming systems.

Für große Instanzen sind viele praktisch relevante Probleme nicht effizient lösbar. Oftmals werden sie jedoch bewältigbar, wenn die Eingaben auf solche Instanzen beschränkt werden, die einen durch eine Konstante beschränkten Parameter aufweisen. Besonders die Baumweite hat sich als attraktiver Parameter erwiesen, da sie auf viele unterschiedliche Probleme anwendbar ist. Beschränkte Baumweite, die zu praktischer Lösbarkeit führt, kann häufig durch dynamische Programmierung auf einer Baumzerlegung der ursprünglichen Instanz ausgenutzt werden. Bisher war es jedoch üblicherweise äußerst aufwendig, solche Algorithmen zu implementieren, was auf den Mangel an unterstützenden Werkzeugen, die eine angemessene Sprache zur einfachen Spezifizierung bereitstellen, zurückzuführen ist.
In dieser Diplomarbeit stellen wir deshalb eine Problemlösungsmethode namens Decompose, Guess & Check vor, die es ermöglicht, solche Algorithmen deklarativ zu spezifizieren. Dafür verwenden wir Antwortmengenprogrammierung - einen logischen Programmierformalismus, der ein Programmierparadigma namens Guess & Check unterstützt und für seine Eignung geschätzt wird, schwierige Probleme sehr prägnant auszudrücken. Durch die Anwendung von Antwortmengenprogrammierung als Sprache zum Spezifizieren der problembezogenen Teile der dynamischen Programmierungsalgorithmen profitiert Decompose, Guess & Check von effizienten Solvern sowie von einer reichhaltigen Sprache, die leicht lesbaren und wartbaren Code ermöglicht.
Wir führen eine Analyse des vorgeschlagenen Ansatzes durch, die zeigt, dass dieser mächtig genug ist, um eine große Klasse an Problemen auf Instanzen beschränkter Baumweite effizient zu lösen. Weiters stellen wir ein Softwaregerüst namens D-FLAT vor, das diese Methode bereitstellt und Rapid Prototyping von Algorithmen auf Baumzerlegungen ermöglicht.
Schließlich wenden wir D-FLAT auf eine Auswahl verschiedener Probleme an, um die Vielseitigkeit des Ansatzes zu illustrieren.
Da Instanzen in praktischen Anwendungen oft kleine Baumweite aufweisen, besitzt unser Ansatz hohe praktische Relevanz. Für viele im Allgemeinen schwierige Probleme ist Decompose, Guess & Check daher ein vielversprechender Kandidat, um große Instanzen zu lösen, die für bestehende Systeme der Antwortmengenprogrammierung bisher außer Reichweite lagen.

Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen