TY  - GEN
UR  - https://archiv.ub.uni-heidelberg.de/volltextserver/6179/
Y1  - 2005///
N2  - 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.
ID  - heidok6179
AV  - public
TI  - Polyhedra and algorithms for the General Routing Problem
KW  - Combinatorial optimization 
KW  -  polyhedral combinatorics
A1  - Theis, Dirk Oliver
ER  -