Implementing variations of the Traveling Salesperson Problem in a declarative dynamic programming environment

Abstract

Das D-FLAT System ist ein Framework das die Vorteile von dynamischer Programmierung (DP) und Answer Set Programming (ASP) vereint. Hierbei wird die Eingabeinstanz zuerst in einen Baum zerlegt und anschließend wird ASP für das Befüllen der DP-Tabellen, basierend auf der deklarativen Spezifikation, verwendet. Dies wird entlang der Baumzerlegung von unten nach oben durchgeführt. Für einfache Graphenprobleme hat sich D-FLAT als durchaus effizient erwiesen, solange die Instanzen niedrige Baumweite aufweisen. Komplexere Probleme, wie zum Beispiel das NP-schwierige Optimierungsproblem des Handlungsreisenden, stellen weiterhin eine Herausforderung dar. Obwohl zahlreiche exakte sowie auch heuristische Ansätze für dieses Problem bekannt sind, gibt es bis dato noch keine Methode die sowohl durch praktische Effizienz, als auch durch eine einfache Handhabe und Adaptierbarkeit besticht. In dieser Diplomarbeit verwenden wir D-FLAT um eine vielseitige Lösung für das Handlungsreisendenproblem vorzuschlagen, welche in einem deklarativen, flexiblen Umfeld implementiert ist und eine kompetitive Alternative zu monolythischen ASP-Implementierungen auf Instanzen mit niedriger Baumweite darstellt.Wir stellen ein Konzept nach den Prinzipien der dynamischen Programmierung für das Handlungsreisendenproblem vor und implementieren zwei konkrete Versionen dieses Problems in D-FLAT. Unsere Aussagen untermauern wir mit den Ergebnissen unserer Experimente, die wir sowohl auf generierten Graphen, als auch auf Instanzen die auf dem öffentlichenWiener Verkehrsnetz basieren, durchgeführt haben. Neben den vielversprechenden Resultaten für Probleminstanzen mit niedriger Baumweite bekommt unsere Arbeit zusätzliche Bedeutung durch die Tatsache, dass das neu entwickelte, deklarative Konzept auch für zahlreiche weitere Probleme, die mit dem Handlungsreisendenproblem verwandt sind, angewandt werden kann.

The D-FLAT System is a free framework that combines the advantages of dynamic programming with those of answer set programming (ASP). Hereby, the input instance is first decomposed into a so-called tree decomposition, then ASP is used to declaratively specify the materialization of the tables for the dynamic programming, which is done along the tree decomposition in a bottom-up manner. D-FLAT proved to perform well for simple graph problems when applied on instances with small treewidth. A more complex and prominent combinatorial problem is the traveling salesperson problem (TSP), which is an NP-hard optimization problem. Solving the TSP on large instances still represents a big challenge. There exist both exact algorithms and heuristics which deal with the TSP, but to the best of our knowledge neither of the two methods is at the same time practically efficient and allows for rapid prototyping. In this master's thesis we use the D-FLAT System to propose a versatile solution for the TSP, which is implemented in a declarative, flexible environment and offers a competitive alternative to monolithic ASP implementations on instances with small treewidth. We present the dynamic programming concept we developed for the TSP and introduce the implementations of two variations of the TSP for D-FLAT. To prove the aforementioned claim, we conduct a series of experiments on generated graphs, as well as on real world instances based on the Viennese public transportation system. The significance of our work derives not only from the results of these experiments but also from the fact that the concept we proposed can be adapted for other NP-hard combinatorial optimization problems that are related to the TSP.