Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Risikomaße in der Finanzmathematik

„Risikomaße in der Finanzmathematik“ Der Value-at -Risk (VaR) ist ein Risikomaß, dessen Verwendung von der Bankenaufsicht gefordert wird. Der Vorteil des VaR liegt – als Quantil der Ertrags- oder Verlustverteilung - vor allem in seiner einfachen Interpretierbarkeit. Nachteilig ist, dass der linke Rand der Wahrscheinlichkeitsverteilung nicht beachtet wird. Darüber hinaus ist die Berechnung des VaR schwierig, da Quantile nicht additiv sind. Der größte Nachteil des VaR ist in der fehlenden Subadditivität zu sehen. Deswegen werden Alternativen wie Expected Shortfall untersucht. In dieser Arbeit werden zunächst finanzielle Risikomaße eingeführt und einige ihre grundlegenden Eigenschaften festgehalten. Wir beschäftigen uns mit verschiedenen parametrischen und nichtparametrischen Methoden zur Ermittlung des VaR, unter anderen mit ihren Vorteilen und Nachteilen. Des Weiteren beschäftigen wir uns mit parametrischen und nichtparametrischen Schätzern vom VaR in diskreter Zeit. Wir stellen Portfoliooptimierungsprobleme im Black Scholes Modell mit beschränktem VaR und mit beschränkter Varianz vor. Der Vorteil des erstens Ansatzes gegenüber dem zweiten wird hier erläutert. Wir lösen Nutzenoptimierungsprobleme in Bezug auf das Endvermögen mit beschränktem VaR und mit beschränkter Varianz. VaR sagt nichts über den darüber hinausgehenden Verlust aus, während dieser von Expected Shortfall berücksichtigt wird. Deswegen verwenden wir hier den Expected Shortfall anstelle des von Emmer, Korn und Klüppelberg (2001) betrachteten Risikomaßes VaR für die Optimierung des Portfolios im Black Scholes Modell.

Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Ektopische Expression schwer exprimierbarer nikotinischer Acetylcholinrezeptoren in Zellinien

Deutsch:In dieser Arbeit wurden Versuche zur funktionellen Expression von schwer ektopisch exprimierbaren nAChR in HEK-293/a1-Zellen durchgeführt: a7 nAChR und a6-enthaltenden nAChR. Die Probleme lagen dabei nicht auf dem Niveau der Transfektion, Transkription, Translation oder der Assemblierung, sondern beim Transport der Rezeptoren zur Zellmembran.Die Expression von a7 nAChR in der Plasmamembran von HEK-293/a1-Zellen konnte durch verbesserte Expressionsbedingungen (Koexpression des Faltungshelfers Calnexin oder weiterer nAChR-Untereinheiten, Erniedrigung der Expressionstemperatur, Expression in Gegenwart nikotinischer Antagonisten) nicht erreicht werden. Auch in anderen Zellinien mit neuronalem oder nicht-neuronalem Ursprung (QT6, GH4C1, S2 und PCC7-Mz1) war die EGFP-gekoppelte a7 nAChR-Untereinheit nur im Zellinneren lokalisiert.Eine intrazelluläre Lokalisation verhinderte auch eine funktionelle Expression homomerer a6 sowie heteromerer a6b2 und a6b3 nAChR in HEK-293/a1-Zellen. Im Gegensatz dazu führte eine Expression von stabil mit den nAChR-Untereinheiten a6 und b4 transfizierten HEK-293/a1-Zellen in Gegenwart von Calciumphosphat-Transfektionslösung und anschließend bei 30°C zu einem verbesserten Transport der Rezeptoren zur Zellmembran und damit zum erfolgreichen Expression funktioneller a6b4 nAChR. Die Wirkung der Transfektionslösung kann durch die erhöhte Calciumkonzentration erklärt werden, da in Ganzzellableitungen eine potenzierende Wirkung von Calciumionen auf den a6b4 nAChR bewiesen wurde. Somit konnte erstmalig der humane a6b4 nAChR in einer Säugerzellinie stabil und funktionell exprimiert werden.

Sozialarbeit in Polen im Spannungsfeld der Systemtransformationsprozesse nach 1989

In der vorliegenden Studie werden die wesentlichen Entwicklungen in der polnischen Sozialarbeit im Bedingungszusammenhang der Systemtransformationsprozesse nach 1989 analysiert. Die Transformation des gesamten Gesellschaftssystems hat einen umfassenden Wandel der Sozialstruktur und der Kultur ausgelöst. Sie bewirkte eine rasche Zunahme sozialer Probleme, solcher wie die Verarmung breiter Teile der polnischen Gesellschaft und Massenarbeitslosigkeit und stellte somit auch hohe Herausforderung an die Sozialpolitik und Sozialarbeit der Transformationszeit. In der Arbeit werden die Probleme und die Lösungsansätze der polnischen Sozialarbeit auf der Ebene der gesellschaftlichen Rahmenbedingungen, der Ebene der Institutionen und Organisationsformen sowie auf der Interaktions- und Handlungsebene der Akteure dargestellt und reflektiert.

Hypersurfaces with many singularities

1. Teil: Bekannte Konstruktionen. Die vorliegende Arbeit gibt zunächst einen ausführlichen Überblick über die bisherigen Entwicklungen auf dem klassischen Gebiet der Hyperflächen mit vielen Singularitäten. Die maximale Anzahl mu^n(d) von Singularitäten auf einer Hyperfläche vom Grad d im P^n(C) ist nur in sehr wenigen Fällen bekannt, im P^3(C) beispielsweise nur für d<=6. Abgesehen von solchen Ausnahmen existieren nur obere und untere Schranken. 2. Teil: Neue Konstruktionen. Für kleine Grade d ist es oft möglich, bessere Resultate zu erhalten als jene, die durch allgemeine Schranken gegeben sind. In dieser Arbeit beschreiben wir einige algorithmische Ansätze hierfür, von denen einer Computer Algebra in Charakteristik 0 benutzt. Unsere anderen algorithmischen Methoden basieren auf einer Suche über endlichen Körpern. Das Liften der so experimentell gefundenen Hyperflächen durch Ausnutzung ihrer Geometrie oder Arithmetik liefert beispielsweise eine Fläche vom Grad 7 mit $99$ reellen gewöhnlichen Doppelpunkten und eine Fläche vom Grad 9 mit 226 gewöhnlichen Doppelpunkten. Diese Konstruktionen liefern die ersten unteren Schranken für mu^3(d) für ungeraden Grad d>5, die die allgemeine Schranke übertreffen. Unser Algorithmus hat außerdem das Potential, auf viele weitere Probleme der algebraischen Geometrie angewendet zu werden. Neben diesen algorithmischen Methoden beschreiben wir eine Konstruktion von Hyperflächen vom Grad d im P^n mit vielen A_j-Singularitäten, j>=2. Diese Beispiele, deren Existenz wir mit Hilfe der Theorie der Dessins d'Enfants beweisen, übertreffen die bekannten unteren Schranken in den meisten Fällen und ergeben insbesondere neue asymptotische untere Schranken für j>=2, n>=3. 3. Teil: Visualisierung. Wir beschließen unsere Arbeit mit einer Anwendung unserer neuen Visualisierungs-Software surfex, die die Stärken mehrerer existierender Programme bündelt, auf die Konstruktion affiner Gleichungen aller 45 topologischen Typen reeller kubischer Flächen.

Symplectic Lagrangian fibrations

In this work we investigate the deformation theory of pairs of an irreducible symplectic manifold X together with a Lagrangian subvariety Y in X, where the focus is on singular Lagrangian subvarieties. Among other things, Voisin's results [Voi92] are generalized to the case of simple normal crossing subvarieties; partial results are also obtained for more complicated singularities.rnAs done in Voisin's article, we link the codimension of the subspace of the universal deformation space of X parametrizing those deformations where Y persists, to the rank of a certain map in cohomology. This enables us in some concrete cases to actually calculate or at least estimate the codimension of this particular subspace. In these cases the Lagrangian subvarieties in question occur as fibers or fiber components of a given Lagrangian fibration f : X --> B. We discuss examples and the question of how our results might help to understand some aspects of Lagrangian fibrations.

Packing a trunk : a physically based approach with full motional freedom

Geometric packing problems may be formulated mathematically as constrained optimization problems. But finding a good solution is a challenging task. The more complicated the geometry of the container or the objects to be packed, the more complex the non-penetration constraints become. In this work we propose the use of a physics engine that simulates a system of colliding rigid bodies. It is a tool to resolve interpenetration conflicts and to optimize configurations locally. We develop an efficient and easy-to-implement physics engine that is specialized for collision detection and contact handling. In succession of the development of this engine a number of novel algorithms for distance calculation and intersection volume were designed and imple- mented, which are presented in this work. They are highly specialized to pro- vide fast responses for cuboids and triangles as input geometry whereas the concepts they are based on can easily be extended to other convex shapes. Especially noteworthy in this context is our ε-distance algorithm - a novel application that is not only very robust and fast but also compact in its im- plementation. Several state-of-the-art third party implementations are being presented and we show that our implementations beat them in runtime and robustness. The packing algorithm that lies on top of the physics engine is a Monte Carlo based approach implemented for packing cuboids into a container described by a triangle soup. We give an implementation for the SAE J1100 variant of the trunk packing problem. We compare this implementation to several established approaches and we show that it gives better results in faster time than these existing implementations.