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

I N A U G U R A L { D I S S E R T A T I O NzurErlangung der DoktorwurdederNaturwissenscha ic h-Mathematischen Gesamtfakult atderRuprecht-Karls-Universit atHeidelbergvorgelegt vonDiplom Mathematiker Dirk Oliver Theisaus SchwalmstadtTag der mundlic hen Prufung: 20.12.2005ThemaPolyhedra and algorithms for the General Routing ProblemGutachter: Prof. Dr. Gerhard ReineltProf. Dr. Dr. h. c. Hans Georg BockZusammenfassungDas General Routing Problem ist ein auf ungerichteten Graphen de niertes NP-schweres kom-binatorisches Optimierungsproblem. Es handelt sich um eine geringfugige Verallgemeinerung desbesser bekannten Rural Postman Problem (siehe z.B. Garey & Johnson 1979, [GJ79]), zu demes tats achlich sowohl theoretisch als auch was die praktische L osung betri t aquiv alent ist. DerUnterschied in der Namensgebung ist nur historisch bedingt.Ein erfolgreicher Ansatz, um kombinatorische Optimierungsprobleme dieser Art praktisch zul osen, d.h. unter der Menge der m oglichen L osungen die beste zu nden, ist der folgende. DieMenge 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 endlichevieler Halbr aume. Ist eine Beschreibung des Polyeders durch lineare Ungleichungen gegeben, kanndann mit Standardmethoden der linearen Optimierung schnell die beste L osung gefunden werden.
Publié le : dimanche 1 janvier 2006
Lecture(s) : 20
Tags :
Source : ARCHIV.UB.UNI-HEIDELBERG.DE/VOLLTEXTSERVER/VOLLTEXTE/2006/6179/PDF/MAIN.PDF
Nombre de pages : 212
Voir plus Voir moins

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 computational results for General Routing Problem instances on graphs with up to and
exceeding 2000 nodes in Chapters 11 and 12. The vast majority of the instances with up to more
than 1000 nodes can be solved quickly by our software program.
For some obscure reason, theses are written in \we"-form, and this paragraph is the only
exception to this rule in this thesis. I would like to thank my PhD supervisor Professor Gerhard
Reinelt for nancing my position and for his support. Adam Letchford and Marcus Oswald deserve
particular thanks for their contributions to the results of Chapters 7 and 5, respectively. Thanks
also to the physicist Tania Robens, who wrote code for the transformation of data les of problem
instances and the extraction of statistical data. John Beasley, Angel Corber an, Richard Eglese,
and Gerhard Reinelt contributed data les containing problem instances. Last but not least,
thanks to my colleagues Dino Ahr, Cara Cocking (thanks for proof reading!), Marcus Oswald,
Hanna Seitz (thanks for proofreading!), Chotiros Surapholchai (thanks for all the cookies!), and
Klaus Wenger at the Discrete Optimization Group of the University of Heidelberg, and to the
secretaries Catherine Proux-Wieland and Karin Tenschert. I dedicate this thesis, particularly my
favourite Chapter 5, to my son, Samuel.Contents
0 Preliminaries and notation 1
0.1 A ne geometry and polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.3 Algorithms and complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.4 Combinatorial optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1 Rural Postman Problem and General Routing Problem 9
1.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 A short summary of known results . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I Polyhedra 13
2 P associated with the GRP 15
2.1 The unbounded polyhedron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 The Ghiani-Laporte tree and bounded polyhedra . . . . . . . . . . . . . . . . . . . 19
2.3 Results on polyhedra for few R-sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 An even smaller polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Transformation and symmetry 25
3.1 Symmetry and isomorphism of GRP polyhedra . . . . . . . . . . . . . . . . . . . . 25
3.2 Relaxation of valid inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Dimension and lifting 33
4.1 Join structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Dimension and complete system of equations . . . . . . . . . . . . . . . . . . . . . 38
4.3 Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.4 Facet-de ning property for the polyhedra with bounds . . . . . . . . . . . . . . . . 44
5 The GTSP polyhedron 49
5.1 How GRP is a face of GTSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Notation, terminology, and known facts for GTSP polyhedra . . . . . . . . . . . . 50
5.3 Vertices, shortcuts, and faces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.4 Existence of non-NR facets with codimension 2 in STSP . . . . . . . . . . . . . . . 59
5.5 Tilting complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.6 An algorithmic perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.7 Application to complete descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.8 Intermediate polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.9 0-Node lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
ixx CONTENTS
6 Understanding LP-solutions 79
6.1 Blocks and connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.2 Flipping variables and merging R-sets . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3 Shrinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
II Separation and related algorithms 85
7 Odd cuts and related concepts 87
7.1 Terminology, notation, and known facts . . . . . . . . . . . . . . . . . . . . . . . . 88
7.2 The Minimum T-odd cut problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.3 Blossom minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8 Exact separation algorithms 103
8.1 Known results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.2 Switched PBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.3 Some results about KC- and PB-separation . . . . . . . . . . . . . . . . . . . . . . 107
9 Separation heuristics 113
9.1 KC-heuristic based on circular partitions . . . . . . . . . . . . . . . . . . . . . . . . 113
9.2 Path-bridge heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.3 A note on HC-separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
III Branch & Cut 119
10 Strategies inside Branch-and-Cut 121
10.1 Core iteration, feasibility test, and rst separation routines . . . . . . . . . . . . . 121
10.2 Heuristics for feasible solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
10.3 Minimum odd cuts and blossoms in practice . . . . . . . . . . . . . . . . . . . . . . 123
10.4 Selecting inequalities and variable bounds . . . . . . . . . . . . . . . . . . . . . . . 126
10.5 Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11 Performance of separation algorithms 129
11.1 The core minimum odd-cut algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 129
11.2 The blossom minimization core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
11.3 Cactus based heuristic for KCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
11.4 \Path- nder" for path-bridges . . . . . . . . . . . . . . . . . . . . . . . . 132
11.5 Cactus cycles based heuristic for PBs . . . . . . . . . . . . . . . . . . . . . . . . . . 132
11.6 cut-nodes based heuristic for PBs . . . . . . . . . . . . . . . . . . . . . . . 132
12 Solution of the GRP 133
12.1 Instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
12.2 A direct comparison to previous work . . . . . . . . . . . . . . . . . . . . . . . . . 134
12.3 Comparison of lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
12.4 Solution by Branch-and-Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
A Figures for Chapter 11 139
A.1 The core minimum odd-cut algorithm and the blossom-minimization core . . . . . 139
A.2 Cactus based heuristic for KCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
A.3 \Path- nder" for path-bridges . . . . . . . . . . . . . . . . . . . . . . . . 147
A.4 Cactus cycles based heuristic for PBs . . . . . . . . . . . . . . . . . . . . . . . . . . 153
A.5 cut-nodes based heuristic for PBs . . . . . . . . . . . . . . . . . . . . . . . 156
B Data of the instances 161

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.