Title: Implementing variations of the Traveling Salesperson Problem in a declarative dynamic programming environment
Other Titles: Lösen von TSP Problemen in einer deklarativen Dynamic-Programming Umgebung
Language: English
Authors: Moldovan, Marius 
Qualification level: Diploma
Advisor: Woltran, Stefan 
Assisting Advisor: Abseher, Michael 
Issue Date: 2015
Number of Pages: 95
Qualification level: Diploma
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.
Keywords: Dynamische Programmierung; Answer-Set Programming; Traveling Salesperson
Dynamic Programming; Answer-Set Programming; Traveling Salesperson
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-79192
http://hdl.handle.net/20.500.12708/4680
Library ID: AC12270210
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

10
checked on Jul 13, 2021

Download(s)

57
checked on Jul 13, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.