Polyhedra and algorithms for the general routing problem [Elektronische Ressource] / vorgelegt von Dirk Oliver Theis

Sujets

• Mathematics

Informations

• Publié par: ruprecht-karls-universitat_heidelberg
• Publié le: 01 janvier 2006
• Nombre de lectures: 18
• Langue: Deutsch
• Poids de l'ouvrage: 3 Mo

Extrait

I N A U G U R A L { D I S S E R T A T I O N
zur
Erlangung der Doktorwurde
der
Naturwissenscha ic h-Mathematischen Gesamtfakult at
der
Ruprecht-Karls-Universit at
Heidelberg
vorgelegt von
Diplom Mathematiker Dirk Oliver Theis
aus Schwalmstadt
Tag der mundlic hen Prufung: 20.12.2005Thema
Polyhedra and algorithms for the General Routing Problem
Gutachter: Prof. Dr. Gerhard Reinelt
Prof. Dr. Dr. h. c. Hans Georg BockZusammenfassung
Das General Routing Problem ist ein auf ungerichteten Graphen de niertes NP-schweres kom-
binatorisches Optimierungsproblem. Es handelt sich um eine geringfugige Verallgemeinerung des
besser bekannten Rural Postman Problem (siehe z.B. Garey & Johnson 1979, [GJ79]), zu dem
es tats achlich sowohl theoretisch als auch was die praktische L osung betri t aquiv alent ist. Der
Unterschied in der Namensgebung ist nur historisch bedingt.
Ein erfolgreicher Ansatz, um kombinatorische Optimierungsprobleme dieser Art praktisch zu
l osen, d.h. unter der Menge der m oglichen L osungen die beste zu nden, ist der folgende. Die
Menge der L osungen einer konkreten Probleminstanz wird mit den Ecken eines konvexen Poly-
eders in einem euklidischen Vektorraum identi ziert. Ein konvexes Polyeder ist der Schnitt endliche
vieler Halbr aume. Ist eine Beschreibung des Polyeders durch lineare Ungleichungen gegeben, kann
dann mit Standardmethoden der linearen Optimierung schnell die beste L osung gefunden werden.
Um diesen Ansatz zu benutzen, mussen zwei Fragestellungen angegangen werden. Erstens
mussen polyedrische Untersuchungen der Struktur des kombinatorischen Optimierungsproblems
vorgenommen werden. Sowohl die Dimension des umgebenden euklidischen Raumes als auch
die Struktur des Polyeders selber h angen n amlich ab von den Daten, welche die Probleminstanz
de nieren. In unserem Fall ist das der Graph. Ziel der Untersuchungen ist es, Klassen von
Ungleichungen zu nden, die ben otigt werden, um die Polyeder zu beschreiben. Diesen Zweig der
diskreten Optimierung nennt man polyedrische Kombinatorik. Zweitens mussen die Klassen von
linearen Ungleichungen, die man identi ziert hat, algorithmisch nutzbar gemacht werden. Das
fuhrt 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 de niert 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. Fur den zweiten Punkt stellen wir Algorithmen vor,
die die oben beschriebenen Trennungsprobleme sowohl theoretisch als auch in der Praxis besser
l osen. Wir haben unsere Ergebnisse genutzt, um eine Software zu entwickeln, die das General
Routing Problem l ost, und wir stellen Rechenergebnisse vor.Abstract
The General Routing Problem is an NP-hard combinatorial optimization problem de ned on
undirected graphs. It is a minor generalization of the better-known Rural Postman Problem (see,
for example, Garey & Johnson 1979, [GJ79]), to which it is, both theoretically and practically,
actually equivalent, although the names are historically di eren t.
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 nite 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 nd 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 de ne the instance, in our case the graph.
The goal is to nd 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 de ned 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 rst 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 ndings in the development of a piece of software which solves the
General Routing Problem, we give computational results.vi
To SamuelPreface
The General Routing Problem is an NP-hard combinatorial optimization problem de ned on
undirected graphs. It is a minor generalization of the better-known Rural Postman Problem (see,
for example, Garey & Johnson [GJ79]), to which it is, both theoretically and practically, actually
equivalent, although the names are historically di eren t.
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
mthe extreme points of a convex polyhedron in . A convex polyhedron is the intersection of a
nite 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 nd 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
mproblem are required. Both the dimension of the ambient spaces and the structure of the
polyhedra themselves depend on the data which de ne the instance, in our case the graph. The
goal is to nd 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 de ned 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 concerned with both the polyhedral combinatorics of the General Routing Prob-
lem, and the algorithmic exploitation of p results. To the rst issue, our contributions
include
the solution of an open question about the structure of the polyhedra when there are only
two so-called R-sets in Chapter 2,
a structural result which allows extending known classes of inequalities in Chapter 3,
the solution of an open question about lifting of facet-de ning inequalities and the facet-
de ning property of known inequalities in Chapter 4, and
the solution of an open question about the relationship of GTSP polyhedra (a subset of
General Routing Problem polyhedra) with the polyhedra associated with the well-known
Symmetric Traveling Salesman Problem, and deep insights into the relationship of the two
kinds of polyhedra in Chapter 5.
An extended abstract of a subset of the results of Chapter 5, which was found in cooperation
with M. Oswald, appeared in the proceedings of the 11th conference on Integer Programming and
Combinatorial Optimization [ORT05]. Our contributions to the algorithmic issue include
1 a new algorithm for the so-called minimum odd cut problem, which, in practice, runs
considerably faster than the known one,
1We acknowledge that the basic core idea of the algorithm was developed independently by Rizzi [Riz03].
viiviii
a new algorithm for the so-called blossom separation problem which improves the theoretical
running time of the known algorithms for this problem in Chapter 7, and
a number of results on polynomial time separation algorithms for some classes of inequalities
in Chapter 8.
An extended abstract of an earlier version of the results on blossom separation, which were co-
operatively developed with A. Letchford, appeared in the proceedings of the 10th conference on
Integer Programming and Combinatorial Optimization [LRT04].
Finally, we also contribute to the practical solution of the General Routing Problem. We
developed a so-called Branch-and-Cut software, which solves General Routing Problem instances,
designed and implemented various heuristic separation algorithms described in Chapter 9, and we
present computationa