Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.

Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Software tools and efficient algorithms for the feature detection, feature tracking, event localization, and visualization of large sets of atmospheric data

Data sets describing the state of the earth's atmosphere are of great importance in the atmospheric sciences. Over the last decades, the quality and sheer amount of the available data increased significantly, resulting in a rising demand for new tools capable of handling and analysing these large, multidimensional sets of atmospheric data. The interdisciplinary work presented in this thesis covers the development and the application of practical software tools and efficient algorithms from the field of computer science, aiming at the goal of enabling atmospheric scientists to analyse and to gain new insights from these large data sets. For this purpose, our tools combine novel techniques with well-established methods from different areas such as scientific visualization and data segmentation. In this thesis, three practical tools are presented. Two of these tools are software systems (Insight and IWAL) for different types of processing and interactive visualization of data, the third tool is an efficient algorithm for data segmentation implemented as part of Insight.Insight is a toolkit for the interactive, three-dimensional visualization and processing of large sets of atmospheric data, originally developed as a testing environment for the novel segmentation algorithm. It provides a dynamic system for combining at runtime data from different sources, a variety of different data processing algorithms, and several visualization techniques. Its modular architecture and flexible scripting support led to additional applications of the software, from which two examples are presented: the usage of Insight as a WMS (web map service) server, and the automatic production of a sequence of images for the visualization of cyclone simulations. The core application of Insight is the provision of the novel segmentation algorithm for the efficient detection and tracking of 3D features in large sets of atmospheric data, as well as for the precise localization of the occurring genesis, lysis, merging and splitting events. Data segmentation usually leads to a significant reduction of the size of the considered data. This enables a practical visualization of the data, statistical analyses of the features and their events, and the manual or automatic detection of interesting situations for subsequent detailed investigation. The concepts of the novel algorithm, its technical realization, and several extensions for avoiding under- and over-segmentation are discussed. As example applications, this thesis covers the setup and the results of the segmentation of upper-tropospheric jet streams and cyclones as full 3D objects. Finally, IWAL is presented, which is a web application for providing an easy interactive access to meteorological data visualizations, primarily aimed at students. As a web application, the needs to retrieve all input data sets and to install and handle complex visualization tools on a local machine are avoided. The main challenge in the provision of customizable visualizations to large numbers of simultaneous users was to find an acceptable trade-off between the available visualization options and the performance of the application. Besides the implementational details, benchmarks and the results of a user survey are presented.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

Topologically correct intersection curves of tori and natural quadrics

This thesis provides efficient and robust algorithms for the computation of the intersection curve between a torus and a simple surface (e.g. a plane, a natural quadric or another torus), based on algebraic and numeric methods. The algebraic part includes the classification of the topological type of the intersection curve and the detection of degenerate situations like embedded conic sections and singularities. Moreover, reference points for each connected intersection curve component are determined. The required computations are realised efficiently by solving quartic polynomials at most and exactly by using exact arithmetic. The numeric part includes algorithms for the tracing of each intersection curve component, starting from the previously computed reference points. Using interval arithmetic, accidental incorrectness like jumping between branches or the skipping of parts are prevented. Furthermore, the environments of singularities are correctly treated. Our algorithms are complete in the sense that any kind of input can be handled including degenerate and singular configurations. They are verified, since the results are topologically correct and approximate the real intersection curve up to any arbitrary given error bound. The algorithms are robust, since no human intervention is required and they are efficient in the way that the treatment of algebraic equations of high degree is avoided.

Microarray based real-time analysis of nucleic acid hybridization kinetics and thermodynamics

Ziel dieser Dissertation ist die experimentelle Charakterisierung und quantitative Beschreibung der Hybridisierung von komplementären Nukleinsäuresträngen mit oberflächengebundenen Fängermolekülen für die Entwicklung von integrierten Biosensoren. Im Gegensatz zu lösungsbasierten Verfahren ist mit Microarray Substraten die Untersuchung vieler Nukleinsäurekombinationen parallel möglich. Als biologisch relevantes Evaluierungssystem wurde das in Eukaryoten universell exprimierte Actin Gen aus unterschiedlichen Pflanzenspezies verwendet. Dieses Testsystem ermöglicht es, nahe verwandte Pflanzenarten auf Grund von geringen Unterschieden in der Gen-Sequenz (SNPs) zu charakterisieren. Aufbauend auf dieses gut studierte Modell eines House-Keeping Genes wurde ein umfassendes Microarray System, bestehend aus kurzen und langen Oligonukleotiden (mit eingebauten LNA-Molekülen), cDNAs sowie DNA und RNA Targets realisiert. Damit konnte ein für online Messung optimiertes Testsystem mit hohen Signalstärken entwickelt werden. Basierend auf den Ergebnissen wurde der gesamte Signalpfad von Nukleinsärekonzentration bis zum digitalen Wert modelliert. Die aus der Entwicklung und den Experimenten gewonnen Erkenntnisse über die Kinetik und Thermodynamik von Hybridisierung sind in drei Publikationen zusammengefasst die das Rückgrat dieser Dissertation bilden. Die erste Publikation beschreibt die Verbesserung der Reproduzierbarkeit und Spezifizität von Microarray Ergebnissen durch online Messung von Kinetik und Thermodynamik gegenüber endpunktbasierten Messungen mit Standard Microarrays. Für die Auswertung der riesigen Datenmengen wurden zwei Algorithmen entwickelt, eine reaktionskinetische Modellierung der Isothermen und ein auf der Fermi-Dirac Statistik beruhende Beschreibung des Schmelzüberganges. Diese Algorithmen werden in der zweiten Publikation beschrieben. Durch die Realisierung von gleichen Sequenzen in den chemisch unterschiedlichen Nukleinsäuren (DNA, RNA und LNA) ist es möglich, definierte Unterschiede in der Konformation des Riboserings und der C5-Methylgruppe der Pyrimidine zu untersuchen. Die kompetitive Wechselwirkung dieser unterschiedlichen Nukleinsäuren gleicher Sequenz und die Auswirkungen auf Kinetik und Thermodynamik ist das Thema der dritten Publikation. Neben der molekularbiologischen und technologischen Entwicklung im Bereich der Sensorik von Hybridisierungsreaktionen oberflächengebundener Nukleinsäuremolekülen, der automatisierten Auswertung und Modellierung der anfallenden Datenmengen und der damit verbundenen besseren quantitativen Beschreibung von Kinetik und Thermodynamik dieser Reaktionen tragen die Ergebnisse zum besseren Verständnis der physikalisch-chemischen Struktur des elementarsten biologischen Moleküls und seiner nach wie vor nicht vollständig verstandenen Spezifizität bei.

Aspekte der Modellbildung: Konzepte und Anwendung in der Atmungsphysiologie

Im ersten Teil 'Analyse der Grundlagen' der Dissertation 'Aspekte der Modellbildung: Konzepte und Anwendung in der Atmungsphysiologie' werden die Grundlagen zur Verfügung gestellt. Ausgehend von der Definition der modularer dynamischer Systeme im Kapitel 1 werden Grundbegriffe zu Modellen, Simulation und Modellentwicklung (Kapitel 2) dargelegt und schließlich folgt ein Kapitel über Netzmodelle. Im zweiten Teil wird 'der Prozess der Operationalisierung' untersucht. Im Kapitel 4 wird mit 'dem Koordinatensystem der Modellbildung' ein allgemeiner Lebenszyklus zur Modellbildung vorgestellt. Das Kapitel 5 zur 'Modellentwicklung' steht im Zentrum der Arbeit, wo eine generische Struktur für modulare Level-Raten-Modelle entwickelt wird. Das Kapitel endet mit einem Konzept zur Kalibrierung von Modellen, das auf Data Mining von Modelldaten basiert. Der Prozess der Operationalisierung endet mit der Validierung im sechsten Kapitel. 'Die Validierung am Beispiel der Atmungsphysiologie' im dritten Teil stellt die Anwendung der in beiden Teilen zuvor entwickelten Theorie dar. Zunächst wird das Projekt 'Evita-Weaning-System' vorgestellt, in dem die Arbeit entstanden ist. Ferner werden die notwendigen medizinischen Grundlagen der Atmungsphysiologie analysiert (Kapitel 7). Eine detaillierte Beschreibung des Modells der Atmungsphysiologie und der dabei entwickelten Algorithmen folgt im achten Kapitel. Die Arbeit schließt mit einem Kapitel zur Validierung des physiologischen Modells.

Synthese und Selbstorganisation von Perylendiimid-Oligonucleotid-Konjugaten

Im Rahmen dieser Arbeit wurde eine Methode entwickelt, Perylendiimidfarbstoffe mit Oligonucleotiden in der Lösung zu verknüpfen. Das Ziel der Arbeit war die nicht-kovalente Synthese von Perylendiimid-DNA- und Protein- supramolekularen Strukturen. Dabei werden die molekularen Erkennungseigenschaften von DNA und Proteinen zunutze gemacht. Insgesamt drei Themenbereiche wurden dabei betrachtet: 1. Synthese und Hybridisierung von symmetrischen und asymmetrischen Perylendiimid-bis(oligonucleotid)-konjugaten für die Bildung supramolekularer Strukturen, 2. Erzeugung von Oberflächenstrukturen auf der Basis von Streptavidin-Perylendiimid-Komplexen, 3. Synthese wasserlöslicher Rylenfarbstoffe für Anwendungen in biologischen Systemen. Zur Synthese und Hybridisierung von Perylendiimid-Oligonucleotid-Konjugaten wurde eine neue Idee verfolgt und erfolgreich realisiert. Dabei handelt es sich um die Synthese von Perylendiimid-DNA-Polymeren durch nicht-kovalente Bindungen. Die Basis des entwickelten Konzepts ist die Ausnutzung der Erkennungseigenschaften der DNA, um Perylendiimidmoleküle in eine lineare Makrostruktur zu organisieren, was sonst nur durch komplizierte chemische Polymersynthese zugänglich wäre. Die Selbstorganisation von zwei komplementären Perylendiimid-bis(oligonucleotid)-konjugaten (PODN1 und PODN2), die an der 5`-Position verknüpft sind, führte zu einem linearen Perylendiimid-DNA-Polymer in der Form von …ABABABAB…., das mit Hilfe von Gelelektrophorese charakterisiert wurde. Eindrucksvoll war auch die erfolgreiche Kopplung des hydrophoben Perylendiimids mit zwei unterschiedlichen Oligonucleotidsequenzen in der Lösung, um asymmetrische Perylendiimid-bis(oligonucleotid)-konjugate zu synthetisieren. Mit solchen asymmetrischen Konjugaten konnte die programmierbare Selbstorganisation der Perylendiimid-Oligonucleotide zu einer definierten Polymerstruktur realisiert werden. Die Synthese von PDI-(biotin)2 wurde vorgestellt. Durch die spezifische Erkennungseigenschaft zwischen Biotin und Streptavidin ist es möglich, eine Oberflächenstruktur zu bilden. Die Immobilisierungsexperimente zeigten, dass das PDI (biotin)2 Streptavidin erkennen und binden kann. Dabei konnte eine multischichtige Nanostruktur (5 Doppelschichten) auf einer Goldoberfläche.

Untersuchungen zum Austausch von Stickstoffdioxid (NO 2) zwischen Pflanzen und Atmosphäre

Der Austausch der NO2-Konzentration zwischen der Atmosphäre und verschiedenen Bäumen (Betula pendula, Fagus sylvatica, Quercus robur, Quercus ilex und Pinus sylvestris) wurde mit einer Dynamischen Küvette gemessen. Die NO2-Konzentrationen wurden mit einem CLD 780 TR Analysator in Verbindung mit einem PLC 762 gemessen. Die experimentellen Untersuchungen wurden im Dunkeln und unter zwei Lichtintensitäts-Niveaus (PAR, 450 und 900 µmol m-2 s-1) und sechs verschiedene NO2-Konzentrationen zwischen 0 - 5.0 ppb durchgeführt. Der stomatäre Einfluss wurde unter Einsatz des Hormons Abscisinsäure untersucht. Die Umgebungsparameter (Lufttemperatur und Luftfeuchtigkeit) wurden konstant gehalten. Die Daten zeigten klar und deutlich den dominanten Einfluss der jeweiligen Baumspezies auf die NO2-Konzentrationen innerhalb der Küvette. Die Ergebnisse dieser Arbeit belegen bei allen Spezies eine lineare Abhängigkeit der NO2-Austauschrate mit der NO2-Umgebungskozentration und mit der stomatären Leitfähigkeit. Das Vorhandensein eines Kompensationspunkt wird nicht bestätigt.

On arc-routing problems

Das Basisproblem von Arc-Routing Problemen mit mehreren Fahrzeugen ist das Capacitated Arc-Routing Problem (CARP). Praktische Anwendungen des CARP sind z.B. in den Bereichen Müllabfuhr und Briefzustellung zu finden. Das Ziel ist es, einen kostenminimalen Tourenplan zu berechnen, bei dem alle erforderlichen Kanten bedient werden und gleichzeitig die Fahrzeugkapazität eingehalten wird. In der vorliegenden Arbeit wird ein Cut-First Branch-and-Price Second Verfahren entwickelt. In der ersten Phase werden Schnittebenen generiert, die dem Master Problem in der zweiten Phase hinzugefügt werden. Das Subproblem ist ein kürzeste Wege Problem mit Ressourcen und wird gelöst um neue Spalten für das Master Problem zu liefern. Ganzzahlige CARP Lösungen werden durch ein neues hierarchisches Branching-Schema garantiert. Umfassende Rechenstudien zeigen die Effektivität dieses Algorithmus. Kombinierte Standort- und Arc-Routing Probleme ermöglichen eine realistischere Modellierung von Zustellvarianten bei der Briefzustellung. In dieser Arbeit werden jeweils zwei mathematische Modelle für Park and Loop und Park and Loop with Curbline vorgestellt. Die Modelle für das jeweilige Problem unterscheiden sich darin, wie zulässige Transfer Routen modelliert werden. Während der erste Modelltyp Subtour-Eliminationsbedingungen verwendet, werden bei dem zweiten Modelltyp Flussvariablen und Flusserhaltungsbedingungen eingesetzt. Die Rechenstudie zeigt, dass ein MIP-Solver den zweiten Modelltyp oft in kürzerer Rechenzeit lösen kann oder bei Erreichen des Zeitlimits bessere Zielfunktionswerte liefert.