Library

Description: A solution generating technique is developed for $D=5$ minimal supergravity with two commuting Killing vectors based on the $G_2$ U-duality arising in the reduction of the theory to three dimensions. The target space of the corresponding 3-dimensional sigma-model is the coset $G_{2(2)}/(SL(2,R)\times SL(2,R))$. Its isometries constitute the set of solution generating symmetries. These include two electric and two magnetic Harrison transformations with the corresponding two pairs of gauge transformations, three $SL(2,R) \; S$-duality transformations, and the three gravitational scale, gauge and Ehlers transformations (altogether 14). We construct a representation of the coset in terms of $7\times 7$ matrices realizing the automorphisms of split octonions. Generating a new solution amounts to transforming the coset matrices by one-parametric subgroups of $G_{2(2)}$ and subsequently solving the dualization equations. Using this formalism we derive a new charged black ring solution with two independent parameters of rotation.

Description: Asymptotic analyses of the three dimensional compressible flow equations coupled with transport equations for the mixing ratios of water vapour, cloud water and rain water are described. We obtain reduced systems of equations for two particular regimes of length and time scales: Models for the long time evolution of deep convective columns and for the short time evolution of shallow convective layers. The asymptotic deep convective column model is anelastic, yet the vertical motion is pressure free, i.e., it evolves freely in interaction with buoyancy while the horizontal divergence adjusts to fullfil the anelastic constraint. The perturbation pressure guaranteeing compliance with the horizontal divergence constraint obeys a Poisson-type equation. Surprisingly, the vertical velocity plays an important role in the horizontal dynamics through the Coriolis term. The vertical acceleration in a saturated column is directly determined by the buoyancy induced by potential temperature differences relative to the background stratification. This potential temperature deviation is a conserved quantity. Evaporation is the only important microphysical process in the undersaturated regime. The evaporation rate depends on the saturation deficit and the amount of rain water present and determines the (downward) vertical velocity and the distribution of water vapour. To connect the deep convective column solutions to top and bottom boundary conditions, a different flow regime needs to be accounted for. Within shallow layers whose depth is comparable to the column diameters, adjustment to physical boundary conditions can take place. This is the second regime considered in this report. The shallow convective layer regime is shown to be asymptotically described by Boussinesq-type equations. These equations are closed by evolution equations which show that, in the saturated regime, the distributions of potential temperature and cloud water are determined by a condensation rate that is directly proportional to the vertical velocity. In the undersaturated regime, the potential temperature distribution is determined by the amount of rain present, since the water vapour in this case is shown to be a conserved quantity. In both regimes the distribution of rain water depends on the rain water flux.

Description: By use of asymptotic analysis Carqué et al. [ZIB-Report 08-03] derived an asymptotic column model for deep convective clouds based on the three dimensional compressible flow equations and a bulk microphysics parameterization. In the present study we check the plausibility of the reduced model equations by comparing implications of the model for the scaling of various terms in the governing equations with those extracted from large eddy simulation data based on the computational model UCLA-LES1.1. This code solves an anelastic system of equations with complete droplet based microphysics and LES closures. We observe that the simulation data corroborate the basic assumptions of the asymptotic analysis and the main conclusions implied by the asymptotically reduced model. The code output reflects the scales of space and time: The deep convective clouds show an anisotropic structure where the horizontal scale is considerably narrower than the vertical scale; with a period of about 20 min, from emergence to breakup, the life cycle of one particular deep convective cloud corresponds exactly to the reference time of the reduced model. The characteristic properties of dynamics as predicted by the reduced model are also reflected in the simulation data: The horizontal flow is controlled by the pressure field; the vertical velocity develops freely independent of pressure over the depth of the convective column; the vertical velocity is directly determined by the buoyancy induced by the potential temperature deviation relative to the background stratification. With respect to grid resolution we observe that refining the spatial step size of the equidistant computational grid from 125 m to 62.5 m does not influence the results: Even with the coarser grid the relevant physical phenomena are sufficiently resolved. Somewhat surprisingly, the Coriolis term involving vertical velocity and acting on the horizontal (east-west) velocity component appears at leading order in the asymptotics. Accordingly, we expected to find a nontrivial impact of this Coriolis effect on the horizontal flow velocity components within columns of updrafts. However, switching the term on and off in subsequent simulations did not sizeably affect the results.

Description: A theoretical and numerical small-scale study of the evaporative cooling phenomenon that might appear in the stratocumulus-topped boundary layers is presented. An ideal configuration of a cloud-top mixing layer is considered as defined by two nonturbulent horizontal layers, stably stratified and with buoyancy reversal within a certain range of mixture fractions due to the evaporative cooling. Linear stability analysis of the shear-free configuration is employed to provide a new interpretation of the buoyancy reversal parameter, namely, in terms of a time-scale ratio between the unstable and the stable modes of the system. An incompressible high-order numerical algorithm to perform direct numerical simulation of the configuration is described and two-dimensional simulations of single-mode perturbations are discussed. These simulations confirm the role of the different parameters identified in the linear stability analysis and show that convoluted flow patterns can be generated by the evaporative cooling even for the low levels of buoyancy reversal found in stratocumulus clouds. They also show that there is no enhancement of entrainment of upper layer fluid in the shear-free configuration, and mixing enhancement by the evaporative cooling is restricted to the lower layer.

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.