Deutsche Übersetzung des Titels: Polyeder und Algorithmen für das General Routing Problem

Vorschau

PDF, Englisch Download (3MB) | Nutzungsbedingungen

Abstract

Das General Routing Problem ist ein auf ungerichteten Graphen definiertes NP-schweres kombinatorisches Optimierungsproblem. Es handelt sich um eine geringfügige Verallgemeinerung des besser bekannten Rural Postman Problem (siehe z.B. Garey & Johnson 1979), zu dem es tatsächlich sowohl theoretisch als auch was die praktische Lösung betrifft äquivalent ist. Der Unterschied in der Namensgebung ist nur historisch bedingt. Ein erfolgreicher Ansatz, um kombinatorische Optimierungsprobleme dieser Art praktisch zu lösen, d.h. unter der Menge der möglichen Lösungen die beste zu finden, ist der folgende. Die Menge der Lösungen einer konkreten Probleminstanz wird mit den Ecken eines konvexen Polyeders in einem euklidischen Vektorraum identifiziert. Ein konvexes Polyeder ist der Schnitt endliche vieler Halbräume. Ist eine Beschreibung des Polyeders durch lineare Ungleichungen gegeben, kann dann mit Standardmethoden der linearen Optimierung schnell die beste Lösung gefunden werden. Um diesen Ansatz zu benutzen, müssen zwei Fragestellungen angegangen werden. Erstens müssen polyedrische Untersuchungen der Struktur des kombinatorischen Optimierungsproblems vorgenommen werden. Sowohl die Dimension des umgebenden euklidischen Raumes als auch die Struktur des Polyeders selber hängen nämlich ab von den Daten, welche die Probleminstanz definieren. In unserem Fall ist das der Graph. Ziel der Untersuchungen ist es, Klassen von Ungleichungen zu finden, die benötigt werden, um die Polyeder zu beschreiben. Diesen Zweig der diskreten Optimierung nennt man polyedrische Kombinatorik. Zweitens müssen die Klassen von linearen Ungleichungen, die man identifiziert hat, algorithmisch nutzbar gemacht werden. Das führt zur Entwicklung von Algorithmen, die das folgende Problem bearbeiten: Gegeben einen Punkt des umgebenden Raumes, stelle fest, ob er in dem Polyeder liegt, das durch die vorliegende Probleminstanz definiert wird, und falls das nicht der Fall ist, erzeuge eine Hyperebene in Form einer linearen Ungleichung, die den Punkt vom Polyeder trennt. Diese Arbeit widmet sich sowohl der polyedrischen Kombinatorik als auch der algorithmischen Nutzbarmachung von Ungleichungen im Zusammenhang mit dem General Routing Problem. Zum ersten Punkt tragen wir strukturelle Eigenschaften der Polyeder sowie eine Reihe von bisher nicht bekannten Klassen von Ungleichungen bei. Für den zweiten Punkt stellen wir Algorithmen vor, die die oben beschriebenen Trennungsprobleme sowohl theoretisch als auch in der Praxis besser lösen. Wir haben unsere Ergebnisse genutzt, um eine Software zu entwickeln, die das General Routing Problem löst, und wir stellen Rechenergebnisse vor.

Übersetzung des Abstracts (Englisch)

The General Routing Problem is an NP-hard combinatorial optimization problem defined on undirected graphs. It is a minor generalization of the better-known Rural Postman Problem (see, for example, Garey & Johnson 1979), to which it is, both theoretically and practically, actually equivalent, although the names are historically different. A widely successful approach to the practical solution of combinatorial optimization problems of this kind is to identify the set of feasible solutions for a particular instance of the problem with the extreme points of a convex polyhedron in an Euclidean vector space. A convex polyhedron is the intersection of a finite number of half spaces. Given a description of the polyhedron in terms of linear inequalities, standard methods of linear optimization can then be used to find the best solution quickly. Using this approach, two main problems, one theoretical and one algorithmic, have to be attacked. Firstly, polyhedral investigations of the structure of the combinatorial optimization problem are required. Both the dimension of the ambient Euclidean spaces and the structure of the polyhedra themselves depend on the data which define the instance, in our case the graph. The goal is to find classes of linear inequalities which are necessary to describe the polyhedra. This branch of discrete optimization is commonly called polyhedral combinatorics. Secondly, the classes of linear inequalities have to be made usable algorithmically, which leads to the development of algorithms to solve the following problem: given a point in the ambient space, decide if it lies outside of the polyhedron defined by the instance, and if so, produce a hyperplane in the form of a linear inequality which separates the point from the polyhedron. This thesis is dedicated to both the polyhedral combinatorics of the General Routing Problem and the algorithmic exploitation of polyhedral results. To the first issue, we contribute structural properties of the polyhedra and a number of formerly unknown classes of inequalities. To the algorithmic issue, we contribute both theoretically and practically improved separation algorithms. Finally, having applied our findings in the development of a piece of software which solves the General Routing Problem, we give computational results.