Ant colony optimization for tree and hypertree decompositions

Abstract

Viele Instanzen von Costraint Satisfaction Problemen sind effizient lösbar wenn sie als Tree oder als Generalized Hypertree Decomposition kleiner Breite dargestellt werden können. Das Auffinden der Decomposition geringster Breite ist jedoch selbst NP-complete und kann daher nur mit Heuristiken und Metaheuristiken in annehmbarer Zeit gelöst werden.<br />Ant Colony Optimization (ACO) ist eine metaheuristische Methode die bisher noch nicht auf dieses Problem angewandt wurde. In dieser Diplomarbeit untersuchen wir fünf verschiedene Varianten von ACO Algorithmen für die Generierung von Tree und Hypertree Decompositions.<br />Außerdem erweitern wir diese Implementierungen mit zwei lokalen Suchmethoden und vergleichen zwei Heuristiken, die den ACO Algorithmus lenken. Weiters experimentieren wir mit zwei unterschiedlichen Pheromone Update Strategien und stellen unsere C++ Bibliothek libaco vor mit deren Hilfe auch andere kombinatorische Optimierungsproblemen mit den in dieser Diplomarbeit beschriebenen ACO Algorithmen gelöst werden können.<br />Um das zu demonstrieren beschreiben wir eine libaco-Implementierung für das Travelling Salesman Problem.<br />Unsere Testergebnisse für ausgewählte Beispiele der DIMACS Graph Coloring Library und der CSP Hypergraph Library zeigen, dass die ACO Metaheuristik für viele Probleminstanzen Ergebnisse liefert welche mit Ergebnissen anderer Verfahren wie beispielsweise Tabu Search und Branch & Bound vergleichbar sind. Einer der vorstellten Algorithmen konnte sogar die bisher besten bekannten Ergebnisse für eine Probleminstanz verbessern. Dessen ungeachtet liefern die ACO Algorithmen insbesondere für komplexere Probleminstanzen schlechtere Ergebnisse als andere bekannte Methoden.<br />

Many instances of constraint satisfaction problems can be solved efficiently if they are representable as a tree respectively generalized hypertree decomposition of small width. Unfortunately, the task of finding a decomposition of minimum width is NP-complete itself.<br />Therefore, many heuristic and metaheuristic methods have been developed for this problem.<br />One metaheuristic which has not been applied yet is ant colony optimization (ACO). In this thesis we investigate five different variants of these ACO algorithms for the generation of tree and generalized hypertree decompositions. Furthermore, we extend these implementations with two local search methods and we compare two heuristics that guide the ACO algorithms. Moreover, we experiment with two different pheromone update strategies and we present a library called libaco that can be used to solve other combinatorial optimization problems as well. In order to demonstrate this we present an ACO implementation for the travelling salesman problem based on this library.<br />Our computational results for selected instances of the DIMACS graph coloring library and the CSP hypergraph library show that the ACO metaheuristic gives results comparable to those of other decomposition methods such as branch and bound and tabu search for many problem instances. One of the proposed algorithms was even able to improve the best known upper bound for one problem instance. Nonetheless, as the problem complexity increases other methods outperform our algorithms.