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.

"Weil eine Fremd’ ich bin, aus fernem Land ...“ – Fremdheit und Fremde im dramatischen Werk Franz Grillparzers und Friedrich Hebbels

Große Dramendichtung kann nur in historischen Umbruchszeiten wie der Antike, der Reformationszeit und im 19. Jahrhundert, also zu Lebzeiten Friedrich Hebbels, entstehen. Das schreibt Hebbel im Vorwort zu seinem bürgerlichen Trauerspiel „Maria Magdalena“. Die großen Zeiten der Tragödien sind Zeiten umwälzender Veränderungen. Im langen 19. Jahrhundert, zwischen Revolution und Restauration, zwischen Reformen und Reaktion, zwischen Hoffnungen auf Demokratie, Nationalstaatlichkeit, zwischen Josephinismus und Ära Metternich, waren die Voraussetzungen für ein Jahrhundert der Tragödie gegeben. Zwei der bedeutendsten Dramatiker des 19. Jahrhunderts, Franz Grillparzer und Friedrich Hebbel, sind Thema der Dissertation. Dabei hat die Arbeit mit der Diskursivierung von Fremdheit und Fremde eine Neuperspektivierung ausgewählter Dramen geleistet, die so in der Forschung noch nicht existiert, wobei diese Perspektive in der Forschung bereits angelegt war. Die hier vorliegende Arbeit hat das „Phänomen der Fremde“, wie Günther Häntzschel es in einem Aufsatz nennt, in den Dramen „Judith“, „Gyges und sein Ring“ und „Die Nibelungen“ von Hebbel und in den Dramen „Das goldene Vließ“, „Die Jüdin von Toledo“ und „Libussa“ von Grillparzer untersucht. Die zentralen Begriffe „Fremde“ und „Fremdheit“ wurden dabei als literarische Topoi, um methodisch besser mit ihnen operieren zu können, in verschiedene Dimensionen der Fremdheit unterteilt: Dabei wurde neben der „Fremdheit der Kulturen“ und der „Fremdheit zwischen den Geschlechtern“ auch die Fremdheit zwischen dem „mythischen Rand der Welt“ und dem „Horizont der Vernunft“ untersucht. Ferner widmete sich ein Kapitel dem Thema Entfremdung und Selbstentfremdung, eine Dimension der Fremdheit, die ebenfalls für die Dramenanalyse relevant ist.

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.