Library

Description: Im Rahmen dieser Arbeit wurde ein individuell anpassungsfähiges Modell entwickelt und implementiert, das die Perfusion in menschlichen soliden Tumoren beschreibt und für verschiedene Zeitpunkte w¨ahrend regionaler Hyperthermie ein lokal abhängiges Temperaturprofil berechnet. Da vor jeder Simulation alle wichtigen Parameter anhand von Ultraschall-, MRT- oder Angiogrammbildern individuell bestimmt werden können, wird eine patientenspezifische Aussage ¨uber das intratumorale Antwortverhalten bereits vor der eigentlichen Behandlung möglich. In Abh¨angigkeit von der Qualität der zur Verfügung stehenden anatomischen Daten über das zu simulierende Gebiet kann das Modell beliebig verfeinert oder bei Mangel an detaillierten Informationen auch mit Minimaldaten und reduzierter räumlicher Genauigkeit benutzt werden. Die für eine Simulation benötigten 2- oder 3- dimensionalen Geometrien können leicht mit der am ZIB entwickelten Software Amira erstellt und zur Berechnung in KARDOS, einem ebenfalls am ZIB implementierten Löser für nichtlineare partielle Differentialgleichungen, eingelesen werden. Mit Hilfe dieses Modells wird eine einfache, aber realistische und aussagekräftige Simulation für die Therapieplanung einer klinischen Hyperthermieanwendung ermöglicht, die innerhalb kurzer Zeit vorbereitet und durchgeführt werden kann.

Description: In dieser Arbeit werden effiziente Co-Reservierungs-Algorithmen vorgestellt, mit denen Rechenressourcen mehrerer Cluster im Grid reserviert werden können. Es werden fünf Algorithmen vorgestellt, die flexible Co-Reservierungsanfragen ermöglichen. In einer Co-Reservierungsanfrage müssen die angeforderten CPUs der Teilreservierungen exakt festgelegt werden. Die Cluster und die Startzeiten, bei denen die Teilreservierungen durchgeführt werden, ermittelt ein Co-Reservierungs-Algorithmus erst bei der Anfragebearbeitung. Die Benutzer können die Startzeit in der Anfrage eingrenzen, in dem sie eine früheste Startzeit und eine Deadline angeben. In den bisher entwickelten Reservierungsverfahren können Benutzer nur starre Co-Reservierungsanfragen stellen, in denen sie für alle Attribute der Teilreservierungen exakte Werte angeben müssen. Eine flexible Co-Reservierungsanfrage erlaubt einem Grid-Reservierungsdienst optimierte Reservierungsvarianten durchzuführen, da er aus vielen Reservierungsvarianten auswählen kann. Die Anwendungen von lokalen Benutzern können durch die Grid-Reservierungen verzögert werden. Bei der Auswahl der Reservierungsvarianten kann ein Grid-Reservierungsdienst dies berücksichtigen und den negativen Einfluß der Grid-Reservierungen verringern. Bei zwei Co-Reservierungs-Algorithmen werden auch zusätzliche Sortiervorgaben des Klienten bei der Auswahl der Reservierungsvarianten beachtet. Die Algorithmen wurden durch Simulationen mit dem Workload eines realen großen Supercomputers ausgewertet. Die Untersuchungen zeigen, daß sowohl die lokalen als auch die Grid-Benutzer von den flexiblen Anfragen profitieren können. Den lokalen Benutzern wurden die Ressourcen weniger oft durch zu früh gestellte Reservierungsanfragen entzogen. Die Grid- Benutzer können ihrerseits komfortabel eine optimierte Reservierungsvariante durchführen lassen.

Description: In dieser Diplomarbeit werden grundlegende Probleme der kostenoptimalen Dimensionierung von Telekommunikationsnetzwerken untersucht. Diese werden als lineare gemischt ganzzahlige Programme formuliert, wobei sich in der Modellierung auf die Konzepte Routing und Kapazitätszuweisung beschränkt wird. Es werden parallel drei übliche, aus der Praxis motivierte Möglichkeiten behandelt, die auf gerichteten oder ungerichteten Kanten eines Netzwerkes installierte Kapazität zu nutzen. Diese unterscheiden wir als DIrected, BIdirected und UNdirected. Die studierten Probleme treten als Relaxierungen vieler realistischer Fragestellungen der Netzwerkoptimierung auf. Sie enthalten elementare Strukturen, deren Studium ausschlaggebend ist für das Verständnis komplexerer Modelle. Letztere können zusätzliche Erfordernisse berücksichtigen, wie zum Beispiel die Ausfallsicherheit von Netzwerken. Zur Lösung solcher NP-schweren Optimierungsprobleme werden erfolgreich Branch & Bound und Schnittebenenverfahren kombiniert (Branch & Cut). Für die Wirksamkeit dieser Algorithmen ist es sehr nützlich, möglichst genaue Kenntnisse der Struktur der Seitenflächen der zugrundeliegenden Polyeder zu haben, welche die konvexe Hülle der Lösungsmenge beschreiben. Es sind starke gültige Ungleichungen zu finden, welche hochdimensionale Seitenflächen oder sogar Facetten definieren. Diese sollten zudem schnell separiert werden können und die numerische Stabilität der Algorithmen möglichst nicht beeinflussen. Diese Arbeit beschäftigt sich im Wesentlichen mit der sehr allgemeinen Rundungstechnik Mixed- Integer Rounding (MIR) zur Verstärkung gültiger Ungleichungen unter Verwendung der Ganzzahligkeitsnebenbedingungen. Es wird eine MIR-Prozedur motiviert, bestehend aus den Schritten Aggregieren, Substituieren, Komplementieren und Skalieren, welche durch Ausnutzung der Struktur der gegebenen Parameter zu einer gültigen Basisungleichung führt, die dann durch MIR eine starke und oft facetten-induzierende Ungleichung gibt. Es werden verschieden Klassen solcher Ungleichungen untersucht und auf ihre Praxistauglichkeit beim Einsatz in Branch & Cut-Verfahren getestet. Nach einer kurzen Einführung werden in Kapitel 2 die für uns in dieser Diplomarbeit relevanten Probleme definiert. Kapitel 3 gibt eine ausführliche Übersicht über die Technik MIR.Wir beschäftigen uns vor allen Dingen mit den Begriffen Superadditivität und Lifting und behandeln Aspekte wie Numerik und beschränkte Variablen. Kapitel 4 und Kapitel 5 umfassen Untersuchungen zu so genannten cut sets. Diese Polyeder werden durch Schnitte in Netzwerken definiert und relaxieren die von uns behandelten Probleme. Hauptsächlich durch MIR entwickeln wir sowohl neue als auch bekannte Klassen von facetten-definierenden Ungleichungen für cut sets, wobei strukturelle Unterschiede herausgearbeitet werden, die durch die drei verschiedenen Typen der Kapzitätsbereitstellung und durch beschränkte Variablen entstehen. Als ein zentrales Resultat wird bewiesen unter welchen Bedingungen facetten-induzierende Ungleichungen für cut sets auch Facetten der zugehörigen relaxierten Polyeder sind. Im Kapitel 6 geben wir weitere Typen von MIR-Ungleichungen an, die auf anderen Netzwerkstrukturen basieren und weisen ferner auf offene Fragen sowie interessante Ideen hin. Das Kapitel 7 widmet sich schließlich der Entwicklung und Implementation von Separationsalgorithmen. Wir testen einige der entwickelten Ungleichungsklassen mit Hinblick auf Ihre Wirksamkeit zur Lösung von realistischen Problemen der Netzwerkdimensionierung aus der Telekommunikation und diskutieren die Ergebnisse.

Description: Diese Arbeit dokumentiert den Entwurf und die Implementierung einer NFS-Schnittstelle zum ZIBDMS. Das ZIBDMS, welches derzeit am Zuse-Institut Berlin entwickelt wird, ist ein Managementsystem für verteilte Daten in heterogenen Umgebungen [10]. Es soll die einfache Benutzung von Mechanismen zur Replikation sowie neue Möglichkeiten des Zugriffs und der Verwaltung von Metadaten und Datenobjekten ermöglichen. Dem Nutzer bietet das System verschiedene Sichten: Neben der klassischen, hierarchischen Sicht mit Verzeichnissen und Dateien wird auch eine attributbasierte Zugriffsmethode angeboten, in der Datenobjekte ausschließlich über Attribut/Wert-Paare referenziert werden. Für den Benutzer transparent, soll sich das System im Hinblick auf die Verfügbarkeit von Daten und Metadaten selbsttätig optimieren. Um Skalierbarkeit gew¨ahrleisten zu können, werden intern Peer-to-Peer- Techniken entwickelt und benutzt. Die NFS-Schnittstelle erhöht die Nutzbarkeit des Systems, da Client- Implementierungen für nahezu alle Betriebssysteme zur Verfügung stehen. Der Benutzer kann so über das gewohnte Dateisystem Daten und Metadaten pflegen, ohne spezifisches Vorwissen zu benötigen. In dieser Arbeit wird untersucht, inwiefern sich die Semantik des ZIBDMS auf jene des NFS-Protokolls übertragen läßt. Weiterhin wird das Konzept von Pseudodateien beschrieben und diskutiert, inwiefern es eine brauchbare Lösung darstellt, den im Vergleich zur NFS-Semantik wesentlich größeren Funktionsumfang des ZIBDMS für den Anwender nutzbar zu machen. Pseudodateien sind nicht-persistente Objekte, welche für den Benutzer als reguläre Datei sichtbar werden und die erweiterte Funktionalitäten wie die Bearbeitung von Metadaten oder die Platzierung von Replikaten über die Dateisystem-Sicht des NFS zur Verfügung stellen sollen. Schließlich werden Leistungsmessungen an den benutzten Komponenten des ZIBDMS vorgenommen und vergleichbaren Systemen gegen übergestellt. Die Aufmerksamkeit liegt hier auf der zugrundeliegenden Katalog-Technologie sowie dem durch das NFS-Protokoll verursachten Overhead.

Description: This diploma thesis deals with the restoration problem in telecommunication networks. The goal is to find a cost minimal capacity capacity assignment on the edges and nodes of a network such that given demands can be satisfied even in case of the failure of an edge or node in the network. Moreover, restrictions on the routing paths (like length restrictions) and hardware constraints have to be satisfied. A Mixed Integer Programming model is presented which takes into account restoration requirements as well as hardware constraints and which abstracts from a particular restoration protocol and failure situation. This abstraction provides new insight into the structure of the network restoration problem and shows that from a mathematical point of view, the commonly used restoration techniques Link Restoration, Path Restoration and Reservation are not as different as they seem to be from a practical point of view. In addition, our model allows (but is not limited to) optimizing working capacity, intended for normal use, and spare capacity, intended for rerouting purposes in case of a failure, in one step. Furthermore, our formulation of capacity cost allows taking into account the effects of discrete, non-linear cost structures which are common in practice. Up to our knowledge, no publication in the existing literature covers all these aspects, let alone in one model, although they are of major practical interest. The model has been implemented in a Branch and Cut framework. The theoretical background of the algorithmic procedure is presented in detail, including computational complexity investigations on the pricing problem. The abstraction from a particular restoration protocol turns out to be useful both from a theoretical and computational point of view. In fact, our investigations suggest a distinction into Local Restoration and Global Restoration rather than into Link Restoration,Path Restoration, Reservation and mixtures of these concepts. In addition to the theoretical aspects of the algorithmic procedure, some implementational details are briefly discussed. Our implementation has been tested on 14 real world instances, which is described in detail. One part of the computational results consists of a comparison of optimal network cost values using diffeent restoration mechanisms, applied to securing either all single node failures, all single edge failures or both. In addition, the effects of a discrete cost structure are investigated, which has rarely been considered yet in literature. Furthermore, the cost ifference between joint and successive working and spare capacity optimization is investigated. In the second part of the computational results, several heuristics for the network restoration problem are compared with respect to both solution quality and time. This diploma thesis deals with the restoration problem in telecommunication networks. The goal is to find a cost minimal capacity capacity assignment on the edges and nodes of a network such that given demands can be satisfied even in case of the failure of an edge or node in the network. Moreover, restrictions on the routing paths (like length restrictions) and hardware constraints have to be satisfied. A Mixed Integer Programming model is presented which takes into account restoration requirements as well as hardware constraints and which abstracts from a particular restoration protocol and failure situation. This abstraction provides new insight into the structure of the network restoration problem and shows that from a mathematical point of view, the commonly used restoration techniques Link Restoration, Path Restoration and Reservation are not as different as they seem to be from a practical point of view. In addition, our model allows (but is not limited to) optimizing working capacity, intended for normal use, and spare capacity, intended for rerouting purposes in case of a failure, in one step. Furthermore, our formulation of capacity cost allows taking into account the effects of discrete, non-linear cost structures which are common in practice. Up to our knowledge, no publication in the existing literature covers all these aspects, let alone in one model, although they are of major practical interest. The model has been implemented in a Branch and Cut framework. The theoretical background of the algorithmic procedure is presented in detail, including computational complexity investigations on the pricing problem. The abstraction from a particular restoration protocol turns out to be useful both from a theoretical and computational point of view. In fact, our investigations suggest a distinction into Local Restoration and Global Restoration rather than into Link Restoration, Path Restoration, Reservation and mixtures of these concepts. In addition to the theoretical aspects of the algorithmic procedure, some implementational details are briefly discussed. Our implementation has been tested on 14 real world instances, which is described in detail. One part of the computational results consists of a comparison of optimal network cost values using different restoration mechanisms, applied to securing either all single node failures, all single edge failures or both. In addition, the effects of a discrete cost structure are investigated, which has rarely been considered yet in literature. Furthermore, the cost difference between joint and successive working and spare capacity optimization is investigated. In the second part of the computational results, several heuristics for the network restoration problem are compared with respect to both solution quality and time.

Description: Mobile cellular communcication is a key technology in today's information age. Despite the continuing improvements in equipment design, interference is and will remain a limiting factor for the use of radio communication. This Ph. D. thesis investigates how to prevent interference to the largest possible extent when assigning the available frequencies to the base stations of a GSM cellular network. The topic is addressed from two directions: first, new algorithms are presented to compute "good" frequency assignments fast; second, a novel approach, based on semidef inite programming, is employed to provide lower bounds for the amount of unavoidable interference. The new methods proposed for automatic frequency planning are compared in terms of running times and effectiveness in computational experiments, where the planning instances are taken from practice. For most of the heuristics the running time behavior is adequate for inter active planning; at the same time, they provide reasonable assignments from a practical point of view (compared to the currently best known, but substantially slower planning methods). In fact, several of these methods are successfully applied by the German GSM network operator E-Plus. The currently best lower bounds on the amount of unavoidable (co-channel) interference are obtained from solving semidefinite programs These programs arise as nonpolyhedral relaxation of a minimum /c-parti tion problem on complete graphs. The success of this approach is made plausible by revealing structural relations between the feasible set of the semidefinite program and a polytope associated with an integer linear programming formulation of the minimum ^-partition problem. Comparable relations are not known to hold for any polynomial time solvable polyhedral relaxation of the minimum ^-partition problem. The appli cation described is one of the first of semidefinite programming for large industrial problems in combinatorial optimization.

Description: In der vorliegenden Dissertation untersuchen wir die Optimierung von ausfallsicheren Telekommunikationsnetzwerken. Wir präsentieren unterschiedliche gemischt-ganzzahlige Modelle für die diskrete Kapazitätsttruktu,, sowie für die Sicherung des Netzes gegen den Ausfall einzelner Komponenten. Die Modelle wurden in einer Kooperation mit der E-Plus Mobilfunk GmbH verwendet. Die theoretischen Resultate wurden in Algorithmen umgesetzt und in das von uns entiickllte Netzwerksoptimierungswerkzeug Discnet (Dimensioning Survivable Capaiitated NETworks) integriert, welches seit mehreren Jahren in der Planung bei E-Plus eingesetzt wird. Wir betrachten das Transportnetzllanungsproblem eines Telekommunikationsanbieters. Dieses Problem setzt auf logischen Kommunikattonsanforerrungen zwischen den Standorten (Knoten) des zu planenden Netzes und potentiell inslallirrbaren Verbindungen (Kanten) zwischen derselben Knotenmenge auf. Ein Kapazitätsmodell stellt die Information bereit, welche Kapazitäten auf den potentiellen Kanten verfügbar sind. Wir betrachten zwei Modelle. Entweder ist eine explizite Liste der verfügbaren Kapazittten gegeben oder eine Menge von sogenannten Basiskapazitäten, die auf jeder Kante indiviuelll kombiniert werden können. Die Basiskapazitäten müßen paarweise ganzzahlige Vielfache voneinander sein. Man beachte, daß diese Eigenschaft von den internationalen Standards PDH und SDH erfüllt wiid. Ein Ausfallsicherheitsmodell stellt die Information bereit, wie das zu planende Netz gegen den Ausfall einzelner Netzkomponenten geschützt werden soll. Wir betrachten sinnvolle Kombinationen der Modelle Diversification, Reservation und Path Restoration. Das erste Modell garantiert Ausfallsicherheit durch kommunikationsbedarfsabhängige Beschränkung des Prozentsatzes, der durch einzelne Netzkomponenten geroutet werden darf. Bei den beiden anderen Modelle können Kommunikationsbedarfe bei Ausfall einer Netzkomponente auf unterschiedliche Weise neu geroutet werden. Ziel der Planung ist eine ktstenminimlle Kapatitätsentscheidung, die eine Routenllanung aller Kommunikationsbedarfe gemäß den Ausfallsicherheitsanforderungen ermöglicht. Wir entwickeln ein Schnittebenenverfahren zur Lösung der betrachteten Optimiergngsrrobleme. Zu diesem Zweck untersuchen wir Polyeder, die mit den verschiedenen Problemen assoziiert sind. Wir präsentieren neue Klassen von Ungleichungen, entwickeln Separationsalgorithmen und Heuristiken. Mit dem Schnittebenenverfahren werden untere und obere Schranken für den Wert von Oitimallösungen berechnet, und daher ist es möglich, Qualitätsgarantien für die berechneten Löungen anzugeben. Parallel zur Beschreibung der implementierten Algorithmen präsentieren wir umfangreiche Tests mit praktisch relevanten Daten, die zu Problemen mit mehr als 2 Billionen Variablen führen.

Description: Die vorliegende Dissertation beschäftigt sich mit der Optimierung der Fahrzeugeinsatzplanung im öffentlichen Personennahverkehr. Dieses Problem ist für die meisten praxisrelevanten Fälle schwierig (Ar'P-schwer). In dieser Arbeit präsentieren wir Methoden der ganzzahligen linearen Programmierung zur Lösung dieses Planungsproblems. "Vernünftige" mathematische Formulierungen des Fahrzeugeinsatzplanungsproblems basieren auf Netzwerkfluß-Modellen und ent sprechenden ganzzahligen linearen Programmen (LP). Dies sind sogenannte bogenorientierte Mehrgüterfluß-Modelle bzw. pfadorientierte SetPartitioning-Modelle. Wir beschäftigen uns mit beiden Ansätzen, der Schwerpunkt liegt aber auf dem bogenorientierte Mehrgüterfluß-Modell Mathematisch bearbeiten wir diese Modelle mit Branch-und-Cut- bzw. Branch-und-Cutund-Price-Methoden. Reale Anwendungen führen zu riesigen LPs mit einigen Millionen ganzzahligen Variablen. Die Behandlung solcher LPs erfordert Spalten-Erzeugungs- Verfahren (auch Column-Generation-Verfahren genannt). Basierend auf Lagrange-Relaxationen entwickeln wir hierzu neue Verfahren zur Auswahl der zu erzeugenden Spalten, die wir Lagrange-Pricing nennen. Lagrange-Pricing-Techniken haben es erstmalig ermöglicht, LPs dieser Art mit rund 70 Millionen Variablen zu lösen. Für den bogenorientierten (Mehrgüter)Fluß-Zugang beschreiben wir ausführlich, wie Lagrange-Relaxationen sowie die LP-Relaxation effizient gelöst werden. Zusätzlich schlagen wir eine Heuristik vor, die schnell gute Lösungen erzeugt. Diese Heuristik beruht auf einem sog. Schedule-FirstClusterSecond-Ansatz. Eine zentrale Aufgabe bei der Lösung dieser primalen und dualen Probleme ist dabei die effiziente Behandlung von Problemen mit einem Depot. Wir zeigen, daß das bogenorientierte Mehrgüterfluß-Modell durch eine geeignete Anwendung der Dantzig-Wolfe-Dekomposition in ein pfadorientiertes SetPartitioning-Modell überführt werden kann. Der zweite Teil dieser Arbeit präsentiert die Rechenergebnisse zu den von uns entwickelten und implementierten Verfahren. Diese Untersuchungen basieren auf realen Testdaten von drei großen deutschen Nahverkehrsunternehmen. Die implementierten Codes arbeiten zuverlässig und stabil. Die mit diesen Verfahren durchgeführten Testläufe lieferten hervorragende Ergebnisse: Bis auf ein Problem können alle Beispiele optimal gelöst werden. Die Lösungen des Branch-and-Cut-Verfahrens wurden auch mit den Planungsergebnissen der in der Praxis gegenwärtig eingesetzten Verfahren verglichen: Wir konnten zusätzlich mehrere Fahrzeuge einsparen sowie eine Kostenreduktion von bis zu 10 % aufzeigen. Der mögliche Nutzen dieser Methoden ist enorm. Beispielsweise rechnet die BVG damit, den Planungsprozeß mit den von uns entwickelten Softwaretools deutlich straffen und jährlich Einsparungen in Höhe von rund 100 Millionen Mark erzielen zu können, siehe den Artikel Auf Sparkurs zum Ziel im Rheinischer Merkur, Nummer 39, von Schmidt [1997] Teile der vorgestellten Methoden wurden bereits in die Planungssysteme BERTA (der Berliner Verkehrsbetriebe (BVG)) und MICROBUS II (der IVU Gesellschaft für Informatik, Verkehrs und Umweltplanung mbH, Berlin) integriert. Darüber hinaus hat auch die Forschungsabteilung der SIEMENS AG in München dieses System erworben.

Description: In der vorliegenden Arbeit werden die grundlegenden Gedanken und die Implementierung eines Branch & Cut-Algorithmus zur Lösung des gewichteten Steinerbaumproblems in Graphen beschrieben. Der Algorithmus basiert auf der linearen Relaxierung einer bidirektionalen ganzzahligen Formulierung des Problems. Wir werden das Problem einführen, drei ganzzahlige Modellierungen vorstellen, auf Reduktionsverfahren und Heuristiken eingehen sowie das Verfahren und seine Implementierung darstellen. Am Ende werden wir die Implementierung an 191 bekannten Probleminstanzen testen und auch optimale Lösungen f� ur zwei nach Wissen des Autors bis zu diesem Zeitpunkt ungelöste Instanzen liefern.