Library

Description: An adjustment scheme for the relaxation parameter of interior point approaches to the numerical solution of pointwise state constrained elliptic optimal control problems is introduced. The method is based on error estimates of an associated finite element discretization of the relaxed problems and optimally selects the relaxation parameter in dependence on the mesh size of discretization. The finite element analysis for the relaxed problems is carried out and a numerical example is presented which confirms our analytical findings.

Description: In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones.

Description: Diese Arbeit befasst sich mit Mehrgüterflussproblemen, in denen Güter mit einer bestimmten Rate durch ein gegebenes Netzwerk geleitet werden müssen. Mithilfe von Mehrgüterflussproblemen können zum Beispiel Verkehrsflüsse in Strassenverkehrsnetzen oder im Internet modelliert werden. In diesen Anwendungen wird die Effizienz von Routenzuweisungen für Güter durch lastabhängige Kostenfunktionen auf den Kanten eines gegebenen Netzwerks definiert. Die Gesamtkosten eines Mehrgüterflüsses sind durch die Summe der Kosten auf den Kanten definiert. Ein optimaler Mehrgüterfluss minimiert diese Gesamtkosten. Ein wesentlicher Bestandteil dieser Arbeit ist die Untersuchung sogenannter Online Algorithmen, die Routen für bekannte Güternachfragen berechnen, ohne vollständiges Wissen über zukünftige Güternachfragen zu haben. Es konnte ein Online Algorithmus gefunden werden, dessen Gesamtkosten für polynomielle Kostenfunktionen mit endlichem Grad nicht beliebig von denen einer optimalen Lösung abweichen. Für die Berechung einer optimalen Lösung müssen alle Güternachfragen a priori vorliegen. Dieses Gütekriterium gilt unabhängig von der gewählten Netzwerktopologie oder der Eingabesequenz von Gütern. Desweiteren befasst sich diese Arbeit mit der Effizienz egoistischer Routenwahl einzelner Nutzer verglichen zu einer optimalen Routenwahl. Egoistisches Verhalten von Nutzern kann mithilfe von nichtkooperativer Spieltheorie untersucht werden. Nutzer werden als strategisch agierende Spieler betrachtet, die ihren Profit maximieren. Als Standardwerkzeug zur Analyse solcher Spiele hat sich das Konzept des Nash Gleichgewichts bewährt. Das Nash Gleichweicht beschreibt eine stabile Strategieverteilung der Spieler, in der kein Spieler einen höheren Profit erzielen kann, wenn er einseitig seine Strategie ändert. Als Hauptergebnis dieser Arbeit konnte für polynomielle Kostenfunktionen mit endlichem Grad gezeigt werden, dass die Gesamtkosten eines Nash Gleichgewichts für sogennante atomare Spieler, die einen diskreten Anteil der gesamten Güternachfrage kontrollieren, nicht beliebig von den Gesamtkosten einer optimalen Lösung abweichen. In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones.

Description: The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.

Description: This thesis describes the algorithm IS-OPT that integrates scheduling of vehicles and duties in public bus transit. IS-OPT is the first algorithm which solves integrated vehicle and duty scheduling problems arising in medium sized carriers such that its solutions can be used in daily operations without further adaptions. This thesis is structured as follows: The first chapter highlights mathematical models of the planning process of public transit companies and examines their potential for integrating them with other planning steps. It also introduces descriptions of the vehicle and the duty scheduling problem. Chapter 2 motivates why it can be useful to integrate vehicle and duty scheduling, explains approaches of the literature, and gives an outline of our algorithm IS-OPT. The following chapters go into the details of the most important techniques and methods of IS-OPT: In Chapter 3 we describe how we use Lagrangean relaxation in a column generation framework. Next, in Chapter 4, we describe a variant of the proximal bundle method (PBM) that is used to approximate linear programs occurring in the solution process. We introduce here a new variant of the PBM which is able to utilize inexact function evaluation and the use of epsilon-subgradients. We also show the convergence of this method under certain assumptions. Chapter 5 treats the generation of duties for the duty scheduling problem. This problem is modeled as a resourceconstraint- shortest-path-problem with non-linear side constraints and nearly linear objective function. It is solved in a two-stage approach. At first we calculate lower bounds on the reduced costs of duties using certain nodes by a new inexact label-setting algorithm. Then we use these bounds to speed up a depth-first-search algorithm that finds feasible duties. In Chapter 6 we present the primal heuristic of IS-OPT that solves the integrated problem to integrality. We introduce a new branch-and-bound based heuristic which we call rapid branching. Rapid branching uses the proximal bundle method to compute lower bounds, it introduces a heuristic node selection scheme, and it utilizes a new branching rule that fixes sets of many variables at once. The common approach to solve the problems occurring in IS-OPT is to trade inexactness of the solutions for speed of the algorithms. This enables, as we show in Chapter 7, to solve large real world integrated problems by IS-OPT. The scheduled produced by IS-OPT save up to 5% of the vehicle and duty cost of existing schedules of regional and urban public transport companies.

Description: Diese Arbeit beschreibt den Algorithmus IS-OPT, welcher der erste Algorithmus ist, der integrierte Umlauf- und Dienstplanungsprobleme für mittelgroße Verkehrsunternehmen löst und dabei alle betrieblichen Einzelheiten berücksichtigt. Seine Lösungen können daher direkt in den täglichen Betrieb übernommen werden. Im ersten Kapitel werden mathematische Modelle für verschiedenen Probleme aus dem Planungsprozess von Nahverkehrsunternehmen beschrieben. Es werden Ansätze zur Integration der einzelnen Probleme untersucht. In diesem Kapitel werden außerdem das Umlauf- und das Dienstplanungsproblem eingeführt. Kapitel 2 motiviert, warum Integration von Umlauf- und Dienstplanung hilfreich ist oder in welchen Fällen sie sogar unabdingbar ist; es gibt einen Überblick über die vorhanden Literatur zur integrierten Umlauf- und Dienstplanung und umreißt unseren Algorithmus IS-OPT. Die weiteren Kapitel behandeln die in IS-OPT verwendeten Methoden: In Kapitel 3 beschreiben wir, wie Spaltenerzeugung für lineare Programme mit Lagrange-Relaxierung und Subgradienten-Verfahren kombiniert werden kann. In Kapitel 4 wird unsere Variante der proximalen Bündelmethode beschrieben. Diese wird benutzt um näherungsweise primale und duale Lösungen von lineare Programmen zu berechnen. Unsere Variante ist angepasst, um auch mit ungenauer Funktionsauswertung und Epsilon-Subgradienten arbeiten zu können. Wir zeigen die Konvergenz dieser Variante unter bestimmten Annahmen. Kapitel 5 behandelt das Erzeugen von Diensten für das Dienstplanungsproblem. Dieses Problem ist als ein Kürzeste-Wege-Problem mit nichtlinearen Nebenbedingungen und fast linearer Zielfunktion modelliert. Wir lösen es, indem zuerst Schranken für die reduzierten Kosten von Diensten, die bestimmte Knoten benutzen, berechnet werden. Diese Schranken werden benutzt, um in einem Tiefensuchalgorithmus den Suchbaum klein zu halten. Im Kapitel 6 präsentieren wir die neu entwickelte Heuristik "Rapid Branching", die eine ganzzahlige Lösung des integrierten Problems berechnet. Rapid Branching kann als eine spezielle Branch-and-Bound-Heuristik gesehen werden, welche die Bündelmethode benutzt. In den Knoten des Suchbaums können mehrere Variablen auf einmal fixiert werden, die mit Hilfe einer Perturbationsheuristik ausgewählt werden. In Kapitel 7 schließlich zeigen wir, daß wir mit IS-OPT auch große Probleminstanzen aus der Praxis lösen können und dabei bis zu 5% der Fahrzeug- und Dienstkosten sparen können.

Description: This paper reviews George Dantzig's contribution to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem

Description: Abstract The cost-efficient design of survivable optical telecommunication networks is the topic of this thesis. In cooperation with network operators, we have developed suitable concepts and mathematical optimization methods to solve this comprehensive planning task in practice. Optical technology is more and more employed in modern telecommunication networks. Digital information is thereby transmitted as short light pulses through glass fibers. Moreover, the optical medium allows for simultaneous transmissions on a single fiber by use of different wavelengths. Recent optical switches enable a direct forwarding of optical channels in the network nodes without the previously required signal retransformation to electronics. Their integration creates ongoing optical connections,which are called lightpaths. We study the problem of finding cost-efficient configurations of optical networks which meet specified communication requirements. A configuration comprises the determination of all lightpaths to establish as well as the detailed allocation of all required devices and systems. We use a flexible modeling framework for a realistic representation of the networks and their composition. For different network architectures, we formulate integer linear programs which model the design task in detail. Moreover, network survivability is an important issue due to the immense bandwidths offered by optical technology. Operators therefore request for designs which perpetuate protected connections and guarantee for a defined minimum throughput in case of malfunctions. In order to achieve an effective realization of scalable protection, we present a novel survivability concept tailored to optical networks and integrate several variants into the models. Our solution approach is based on a suitable model decomposition into two subtasks which separates two individually hard subproblems and enables this way to compute cost-efficient designs with approved quality guarantee. The first subtask consists of routing the connections with corresponding dimensioning of capacities and constitutes a common core task in the area of network planning. Sophisticated methods for such problems have already been developed and are deployed by appropriate integration. The second subtask is characteristic for optical networks and seeks for a conflict-free assignment of available wavelengths to the lightpaths using a minimum number of involved wavelength converters. For this coloring-like task, we derive particular models and study methods to estimate the number of unavoidable conversions. As constructive approach, we develop heuristics and an exact branch-and-price algorithm. Finally, we carry out an extensive computational study on realistic data, provided by our industrial partners. As twofold purpose, we demonstrate the potential of our approach for computing good solutions with quality guarantee, and we exemplify its flexibility for application to network design and analysis.

Description: Parabolic reaction-diffusion systems may develop sharp moving reaction fronts which pose a challenge even for adaptive finite element methods. We propose a method to transform the equation into an equivalent form that usually exhibits solutions which are easier to discretize, giving higher accuracy for a given number of degrees of freedom. The transformation is realized as an efficiently computable pointwise nonlinear scaling that is optimized for prototypical planar travelling wave solutions of the underlying reaction-diffusion equation. The gain in either performance or accuracy is demonstrated on different numerical examples.

Description: We propose and analyse an interior point path-following method in function space for state constrained optimal control. Our emphasis is on proving convergence in function space and on constructing a practical path-following algorithm. In particular, the introduction of a pointwise damping step leads to a very efficient method, as verified by numerical experiments.

Description: wird nachgereicht

Description: Multi-scale phenomena are abundant in many application fields. Representing and numerically simulating such processes is a challenging task since quite different scales have to be resolved, which often requires enormous amounts of storage and computational power. An important strategy in this context is adaptivity, i.e. local adjustment of the spatio-temporal resolution to the details to be resolved. A standard representation therefore are hierarchical, locally refined grids. A specific adaptive approach for solving partial differential equations, usually called AMR (Adaptive Mesh Refinement), was introduced in 1984. The basic idea is to combine the simplicity of structured grids and the advantages of local refinement. In this numerical scheme the computations are started on a set of coarse, potentially overlapping structured grids, that cover the computational domain. Local error criteria are applied to detect regions that require higher resolution. These are covered by subgrids with decreasing mesh spacing, which do not replace, but rather overlap the refined regions of the coarser patches. The equations are advanced on the finer subgrids and the refinement procedure recursively continues until all cells fulfill the considered error criteria, giving rise to a hierarchy of nested levels of refinement. In 1989 a variant of this scheme, called Structured Adaptive Mesh Refinement (SAMR), which reduces some of the complexity of the original approach, was proposed. While the separate subgrids in the AMR scheme could be rotated against each other, in SAMR they are aligned with the major axes of the coordinate system, which for example simplifies the computation of fluxes of (conserved) quantities through the cell faces. SAMR has become more and more popular in the last decade, and nowadays it is applied in many domains like hydrodynamics, meteorology and in particular in cosmology and relativistic astrophysics. Due to this growing popularity, an increasing number of scientists is in need of appropriate interactive visualization techniques to interpret and analyze AMR simulation data. Tools for both, 2D analysis to quantitatively convey the information within single slices and 3D representations to apprehend the overall structure are required. In this thesis we develop direct and indirect volume visualization algorithms for scalar fields that are defined on structured Adaptive Mesh Refinement (SAMR) grids. In particular algorithms for planar slicing and the display of height fields, C0-continuous isosurface extraction, software-, and hardware-based direct volume rendering and temporal interpolation for cell-, and vertex-centered data on unrestricted SAMR grids are proposed. Additionally we investigate the applicability of SAMR data structures for accelerated software-, and hardware-based volume rendering of large 3D scalar data.

Description: This thesis deals with a Dial-a-Ride problem on trees and considers both offline and online versions of this problem. We study the behavior of certain algorithms on random instances, i.e. we do probabilistic analysis. The focus is on results describing the typical behavior of the algorithms, i.e. results holding with (asymptotically) high probability. For the offline version, we present a simplified proof of a result of Coja-Oghlan, Krumke und Nierhoff. The results states that some heuristic using a minimum spanning tree to approximate a Steiner tree gives optimal results with high probability. This explains why this heuristic produces optimal solutions quite often. In the second part, probabilistic online versions of the problem are introduced. We study the online strategies REPLAN and IGNORE. Regarding the IGNORE strategy we can show that it works almost optimal under high load with high probability.

Description: All-optical telecommunication networks allow for switching connections by lightpaths which can pass several network links without any opto-electronic conversion. Upon arrival of a connection request, it must be decided online, i.e., without knowledge of future requests, if it is accepted and in that case on which lightpaths the connection is routed. This online problem with the goal of maximizing the total profit gained by accepted requests is called Dynamic Singleclass Call Admission Problem (DSCA). We present existing and new algorithms for the DSCA as well as their theoretical and practical evaluation.

Description: Als Cluster Analyse bezeichnet man den Prozess der Suche und Beschreibung von Gruppen (Clustern) von Objekten, so daß die Objekte innerhalb eines Clusters bezüglich eines gegebenen Maßes maximal homogen sind. Die Homogenität der Objekte hängt dabei direkt oder indirekt von den Ausprägungen ab, die sie für eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern läßt sich somit als Optimierungsproblem auffassen, wobei die Anzahl der Cluster vorher bekannt sein muß. Wenn die Anzahl der Objekte und der Attribute groß ist, spricht man von komplexen, hoch-dimensionalen Cluster Problemen. In diesem Fall ist eine direkte Optimierung zu aufwendig, und man benötigt entweder heuristische Optimierungsverfahren oder Methoden zur Reduktion der Komplexität. In der Vergangenheit wurden in der Forschung fast ausschließlich Verfahren für geometrisch basierte Clusterprobleme entwickelt. Bei diesen Problemen lassen sich die Objekte als Punkte in einem von den Attributen aufgespannten metrischen Raum modellieren; das verwendete Homogenitätsmaß basiert auf der geometrischen Distanz der den Objekten zugeordneten Punkte. Insbesondere zur Bestimmung sogenannter metastabiler Cluster sind solche Verfahren aber offensichtlich nicht geeignet, da metastabile Cluster, die z.B. in der Konformationsanalyse von Biomolekülen von zentraler Bedeutung sind, nicht auf einer geometrischen, sondern einer dynamischen Ähnlichkeit beruhen. In der vorliegenden Arbeit wird ein allgemeines Clustermodell vorgeschlagen, das zur Modellierung geometrischer, wie auch dynamischer Clusterprobleme geeignet ist. Es wird eine Methode zur Komplexitätsreduktion von Clusterproblemen vorgestellt, die auf einer zuvor generierten Komprimierung der Objekte innerhalb des Datenraumes basiert. Dabei wird bewiesen, daß eine solche Reduktion die Clusterstruktur nicht zerstört, wenn die Komprimierung fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich geeignete Komprimierungen berechnen. Um eine signifikante Komplexitätsreduktion ohne Zerstörung der Clusterstruktur zu erzielen, werden die genannten Methoden in ein mehrstufiges Verfahren eingebettet. Da neben der Identifizierung der Cluster auch deren effiziente Beschreibung notwendig ist, wird ferner eine spezielle Art der Komprimierung vorgestellt, der eine Boxdiskretisierung des Datenraumes zugrunde liegt. Diese ermöglicht die einfache Generierung von regelbasierten Clusterbeschreibungen. Für einen speziellen Typ von Homogenitätsfunktionen, die eine stochastische Eigenschaft besitzen, wird das mehrstufige Clusterverfahren um eine Perroncluster Analyse erweitert. Dadurch wird die Anzahl der Cluster, im Gegensatz zu herkömmlichen Verfahren, nicht mehr als Eingabeparameter benötigt. Mit dem entwickelten Clusterverfahren kann erstmalig eine computergestützte Konformationsanalyse großer, für die Praxis relevanter Biomoleküle durchgeführt werden. Am Beispiel des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben.

Description: The present dissertation deals with the structure of polyhedral subdivisions of point configurations. Of particular interest are the global properties of the set of all subdivisions of a given point configuration. An important open problem in this context is the following: can one always transform any triangulation of a given point configuration to any other triangulation of the same configuration by means of bistellar operations? In other words, is the set of all triangulations of a given point configuration always bistellarly connected? The results presented in this thesis contribute progress from two directions. \begin{itemize} \item The set of all subdivisions that are induced by a polytope projection is in general not bistellarly connected in a generalized sense. This result is obtained by constructing a counterexample to the so-called Generalized Baues Conjecture.'' \item The set of all triangulations of a cyclic polytope forms a bounded poset. The covering relations are given by increasing bistellar operations. Thus we get an affirmative answer to the above question in the case of cyclic polytopes. \end{itemize} In the introduction, the mathematical environment of the structures under consideration is illuminated. The "Generalized Baues Conjecture" has connections to various mathematical concepts, such as combinatorial models for loop spaces, discriminants of polynomials in several variables, etc. The triangulation posets of cyclic polytopes are natural generalizations of the well-studied Tamari lattices in order theory. Moreover, there is a connection to the higher Bruhat orders, which have similar structural properties. As a by-product, the investigations yield the shellability of all triangulations of cyclic polytopes without new vertices. This is in particular interesting because most triangulations of cyclic polytopes are non-regular.

Description: Die vorliegende Dissertation beschäftigt sich mit strukturellen Fragen in der Theorie der polyedrischen Unterteilungen von Punktkonfigurationen. Hierbei sind vor allem globale Eigenschaften der Menge aller Unterteilungen einer gegebenen Punktkonfiguration von Interesse. Eine wichtige ungelöste Frage in diesem Zusammenhang ist die folgende: Ist es immer möglich, von einer beliebigen Triangulierung einer gegebenen Punktkonfiguration zu jeder anderen Triangulierung derselben Konfiguration zu gelangen, indem man sogenannte bistellare Operationen durchführt? Mit anderen Worten, ist die Menge aller Triangulierungen einer gegebenen Punktkonfiguration stets bistellar zusammenhängend? Die Ergebnisse der vorliegenden Doktorarbeit liefern auf zwei Seiten dieser nach wie vor offenen Frage Fortschritte: \begin{itemize} \item Die Menge aller durch eine Polytopprojektion induzierten Unterteilungen ist nicht immer --- in einem verallgemeinerten Sinne --- bistellar zusammenhängend. Dieses Resultat wird durch ein Gegenbeispiel zur sogenannten "Verallgemeinerten Baues Vermutung"' erzielt. \item Die Menge aller Triangulierungen eines zyklischen Polytops bildet eine beschränkte Halbordnung. Die Ueberdeckungsrelationen sind gerichtete bistellare Operationen. Für zyklische Polytope ist die obige Frage nach bistellarem Zusammenhang also positiv beantwortet. \end{itemize} In der Einleitung wird das mathematische Umfeld der betrachteten Strukturen näher beleuchtet: Die "Verallgemeinerte Baues Vermutung" steht in Verbindung mit verschiedensten mathematischen Konzepten, angefangen von kombinatorischen Modellen von Schleifenräumen bis hin zu Diskriminanten von Polynomen in mehreren Variablen. Die Triangulierungs-Halbordnungen von zyklischen Polytopen sind zugleich natürliche Verallgemeinerungen der gut studierten Tamari-Verbände in der Ordnungstheorie. Ausserdem existiert ein Zusammenhang mit den höheren Bruhat-Ordnungen, die ähnliche Struktureigenschaften aufweisen. Ein Nebenprodukt der Untersuchungen ist die Schälbarkeit aller Triangulierungen von zyklischen Polytopen ohne neue Ecken. Das ist um so interessanter, da die meisten Triangulierungen von zyklischen Polytopen nicht-regulär sind.