German Title: Exakte und heuristische Lösungen des Bandwidth Minimization Problem

Preview

PDF, English Download (1MB) | Terms of use

Abstract

The bandwidth minimization problem is a classical combinatorial optimization problem studied since about 1960. It is formulated as follows. Given a connected graph G=(V,E) with n vertices, the task is to find a permutation l of the vertices (also called a labeling), i.e., a bijection between V and {1,2,...,n}, such that the maximum difference |l(u)-l(v)|, for uv in E, is minimized. This problem is NP-hard, even for binary trees. Applications of the bandwidth problem can be found in many areas: solving systems of linear equations, data storage, electronic circuit design, and recently in compression of topological information from digital road networks. In this dissertation we report our contributions of both heuristic and exact methods for the bandwidth problem. On the heuristic side, we start by modifying a heuristic method which exploits properties of the graph. Next we propose an approximate objective function for the bandwidth problem. It is very sensitive to alterations in a permutation and can thus be used efficiently in global optimization heuristic methods. A simulated annealing method using the approximate objective function is reported. We also present an application of the bandwidth problem to the compression of topological information of digital road networks. For exact methods, which are our main focus, we formulate the concept of a partial permutation. Based on this concept, we introduce new constraints for the bandwidth problem and apply them efficiently in a branch-and-bound algorithm. We analyze the relation between certain partial permutations and show that some partial permutations are dominated by others. Therefore, they can be eliminated in the branch-and-bound tree and this reduces the search space and running time. Furthermore, we enhance the use of partial permutations in branch-and-bound algorithms with a 2-labeling scheme, supported by the dominance rule. Instead of extending the partial permutation one-by-one, our scheme uses two vertices simultaneously. We evaluate our algorithms on a popular benchmark suite which comprises 113 instances with less than 1,000 vertices each. In many cases our work improves on the best known lower bound in the literature. Moreover, our exact algorithms are capable of computing lower bounds for much larger instances. We perform computational experiments on a second suite of 36 instances with more than 1,000 vertices each, whose best known lower bound so far is the generic theoretical one. We can improve this bound for some instances in this suite, the largest such instance having about 15,600 vertices. Finally, we parallelize our branch-and-bound algorithms and run the solver on a parallel cluster with 256 processors, improving the lower bound for some instances in the first benchmark suite even further.

Translation of abstract (German)

Das Bandwidth Minimization Problem ist ein klassisches kombinatorisches Optimierungsproblem, das bereits seit etwa 1960 untersucht wird: Zu einem gegebenen zusammenhängenden Graphen G=(V,E) der Ordnung n ist eine Permutation l der Knoten (auch Labeling genannt) gesucht, d.h. eine Bijektion von V auf die Menge {1,2,...,n}, für welche die maximale Differenz |l(u)-l(v)| über alle uv in E minimal ist. Das Problem ist bereits auf Binärbäumen NP-schwer. Anwendungen des Problems finden sich beispielsweise beim Lösen großer linearer Gleichungssysteme, in der Datenspeicherung, beim Entwurf von Schaltkreisen und jüngst auch bei der Komprimierung topologischer Daten von digitalen Straßennetzen. In der vorliegenden Arbeit stellen wir unsere Beiträge zur näherungsweisen sowie zur exakten Lösung des Problems vor. Zunächst verbessern wir durch geeignete Modifikationen eine bestehende Heuristik, die sich Eigenschaften des Graphen zunutze macht. Anschließend schlagen wir eine approximative Zielfunktion vor, welche sensibler auf Veränderungen in den Permutationen reagiert und sich dadurch vor allem für globale Heuristiken eignet. Wir beschreiben einen Simulated-Annealing Algorithmus, der diese Approximation verwendet. Wir präsentieren ferner eine Anwendung des Problems auf die Komprimierung topologischer Daten von digitalen Straßennetzen. Unser Hauptaugenmerk liegt jedoch auf exakten Lösungsverfahren. Für diese führen wir den Begriff der Teilpermutation ein. Darauf basierend entwickeln wir neue gültige Nebenbedingungen, welche wir effizient in einen Branch-and-Bound Algorithmus einbinden. Wir analysieren die Beziehung bestimmter Teilpermutationen zueinander und beweisen, dass einige Teilpermutationen durch andere dominiert werden. Dominierte Teilpermutationen können dabei im Branch-and-Bound-Suchbaum vernachlässigt werden, wodurch sich die Laufzeit reduzieren lässt. Des Weiteren präsentieren wir mit dem sogenannten 2-Labeling-Schema eine verbesserte Methode zur Verwendung von Teilpermutationen in Branch-and-Bound Algorithmen. Hierbei nutzen wir die obige Dominanzbeziehung und vergrößern die Teilpermutation in jedem Iterationsschritt um zwei statt nur um einen Knoten. Wir testen unsere Algorithmen mit einer gängigen Sammlung von 113 Benchmark-Instanzen mit jeweils weniger als 1000 Knoten. In vielen Fällen können wir hierbei die besten bekannten unteren Schranken aus der Literatur verbessern. Darüberhinaus können wir mit unseren Methoden untere Schranken für weitaus größere Instanzen bestimmen. Wir belegen dies anhand von Rechenexperimenten auf einer zweiten Benchmark-Sammlung. Diese umfasst 36 Instanzen mit jeweils mehr als 1000 Knoten. Die beste bekannte untere Schranke jeder dieser Instanzen ist durch eine allgemeine Abschätzungsformel gegeben. Die größte Instanz, für welche wir eine erstmalige Verbesserung dieser unteren Schranke erzielen können, besitzt 15600 Knoten. Schließlich parallelisieren wir unseren Branch-and-Bound Algorithmus und testen ihn auf einem Cluster mit 256 Prozessoren. Hierdurch können wir die unteren Schranken für einige Instanzen mit weniger als 1000 Knoten noch weiter verbessern.