Algorithms for network design and routing problems

In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.

Constraints on mantle melting from major and trace element systematics in residual abyssal peridotites

ZusammenfassungDie Bildung von mittelozeanischen Rückenbasalten (MORB) ist einer der wichtigsten Stoffflüsse der Erde. Jährlich wird entlang der 75.000 km langen mittelozeanischen Rücken mehr als 20 km3 neue magmatische Kruste gebildet, das sind etwa 90 Prozent der globalen Magmenproduktion. Obwohl ozeanische Rücken und MORB zu den am meisten untersuchten geologischen Themenbereichen gehören, existieren weiterhin einige Streit-fragen. Zu den wichtigsten zählt die Rolle von geodynamischen Rahmenbedingungen, wie etwa Divergenzrate oder die Nähe zu Hotspots oder Transformstörungen, sowie der absolute Aufschmelzgrad, oder die Tiefe, in der die Aufschmelzung unter den Rücken beginnt. Diese Dissertation widmet sich diesen Themen auf der Basis von Haupt- und Spurenelementzusammensetzungen in Mineralen ozeanischer Mantelgesteine.Geochemische Charakteristika von MORB deuten darauf hin, dass der ozeanische Mantel im Stabilitätsfeld von Granatperidotit zu schmelzen beginnt. Neuere Experimente zeigen jedoch, dass die schweren Seltenerdelemente (SEE) kompatibel im Klinopyroxen (Cpx) sind. Aufgrund dieser granatähnlichen Eigenschaft von Cpx wird Granat nicht mehr zur Erklärung der MORB Daten benötigt, wodurch sich der Beginn der Aufschmelzung zu geringeren Drucken verschiebt. Aus diesem Grund ist es wichtig zu überprüfen, ob diese Hypothese mit Daten von abyssalen Peridotiten in Einklang zu bringen ist. Diese am Ozeanboden aufgeschlossenen Mantelfragmente stellen die Residuen des Aufschmelz-prozesses dar, und ihr Mineralchemismus enthält Information über die Bildungs-bedingungen der Magmen. Haupt- und Spurenelementzusammensetzungen von Peridotit-proben des Zentralindischen Rückens (CIR) wurden mit Mikrosonde und Ionensonde bestimmt, und mit veröffentlichten Daten verglichen. Cpx der CIR Peridotite weisen niedrige Verhältnisse von mittleren zu schweren SEE und hohe absolute Konzentrationen der schweren SEE auf. Aufschmelzmodelle eines Spinellperidotits unter Anwendung von üblichen, inkompatiblen Verteilungskoeffizienten (Kd's) können die gemessenen Fraktionierungen von mittleren zu schweren SEE nicht reproduzieren. Die Anwendung der neuen Kd's, die kompatibles Verhalten der schweren SEE im Cpx vorhersagen, ergibt zwar bessere Resultate, kann jedoch nicht die am stärksten fraktionierten Proben erklären. Darüber hinaus werden sehr hohe Aufschmelzgrade benötigt, was nicht mit Hauptelementdaten in Einklang zu bringen ist. Niedrige (~3-5%) Aufschmelzgrade im Stabilitätsfeld von Granatperidotit, gefolgt von weiterer Aufschmelzung von Spinellperidotit kann jedoch die Beobachtungen weitgehend erklären. Aus diesem Grund muss Granat weiterhin als wichtige Phase bei der Genese von MORB betrachtet werden (Kapitel 1).Eine weitere Hürde zum quantitativen Verständnis von Aufschmelzprozessen unter mittelozeanischen Rücken ist die fehlende Korrelation zwischen Haupt- und Spuren-elementen in residuellen abyssalen Peridotiten. Das Cr/(Cr+Al) Verhältnis (Cr#) in Spinell wird im Allgemeinen als guter qualitativer Indikator für den Aufschmelzgrad betrachtet. Die Mineralchemie der CIR Peridotite und publizierte Daten von anderen abyssalen Peridotiten zeigen, dass die schweren SEE sehr gut (r2 ~ 0.9) mit Cr# der koexistierenden Spinelle korreliert. Die Auswertung dieser Korrelation ergibt einen quantitativen Aufschmelz-indikator für Residuen, welcher auf dem Spinellchemismus basiert. Damit kann der Schmelzgrad als Funktion von Cr# in Spinell ausgedrückt werden: F = 0.10×ln(Cr#) + 0.24 (Hellebrand et al., Nature, in review; Kapitel 2). Die Anwendung dieses Indikators auf Mantelproben, für die keine Ionensondendaten verfügbar sind, ermöglicht es, geochemische und geophysikalischen Daten zu verbinden. Aus geodynamischer Perspektive ist der Gakkel Rücken im Arktischen Ozean von großer Bedeutung für das Verständnis von Aufschmelzprozessen, da er weltweit die niedrigste Divergenzrate aufweist und große Transformstörungen fehlen. Publizierte Basaltdaten deuten auf einen extrem niedrigen Aufschmelzgrad hin, was mit globalen Korrelationen im Einklang steht. Stark alterierte Mantelperidotite einer Lokalität entlang des kaum beprobten Gakkel Rückens wurden deshalb auf Primärminerale untersucht. Nur in einer Probe sind oxidierte Spinellpseudomorphosen mit Spuren primärer Spinelle erhalten geblieben. Ihre Cr# ist signifikant höher als die einiger Peridotite von schneller divergierenden Rücken und ihr Schmelzgrad ist damit höher als aufgrund der Basaltzusammensetzungen vermutet. Der unter Anwendung des oben erwähnten Indikators ermittelte Schmelzgrad ermöglicht die Berechnung der Krustenmächtigkeit am Gakkel Rücken. Diese ist wesentlich größer als die aus Schweredaten ermittelte Mächtigkeit, oder die aus der globalen Korrelation zwischen Divergenzrate und mittels Seismik erhaltene Krustendicke. Dieses unerwartete Ergebnis kann möglicherweise auf kompositionelle Heterogenitäten bei niedrigen Schmelzgraden, oder auf eine insgesamt größere Verarmung des Mantels unter dem Gakkel Rücken zurückgeführt werden (Hellebrand et al., Chem.Geol., in review; Kapitel 3).Zusätzliche Informationen zur Modellierung und Analytik sind im Anhang A-C aufgeführt

Modeling surface-atmosphere exchange of trace gases and energy within and above the Amazon rain forest

Die vorliegende Dissertation untersucht die biogeochemischen Vorgänge in der Vegetationsschicht (Bestand) und die Rückkopplungen zwischen physiologischen und physikalischen Umweltprozessen, die das Klima und die Chemie der unteren Atmosphäre beeinflussen. Ein besondere Schwerpunkt ist die Verwendung theoretischer Ansätze zur Quantifizierung des vertikalen Austauschs von Energie und Spurengasen (Vertikalfluss) unter besonderer Berücksichtigung der Wechselwirkungen der beteiligten Prozesse. Es wird ein differenziertes Mehrschicht-Modell der Vegetation hergeleitet, implementiert, für den amazonischen Regenwald parametrisiert und auf einen Standort in Rondonia (Südwest Amazonien) angewendet, welches die gekoppelten Gleichungen zur Energiebilanz der Oberfläche und CO2-Assimilation auf der Blattskala mit einer Lagrange-Beschreibung des Vertikaltransports auf der Bestandesskala kombiniert. Die hergeleiteten Parametrisierungen beinhalten die vertikale Dichteverteilung der Blattfläche, ein normalisiertes Profil der horizontalen Windgeschwindigkeit, die Lichtakklimatisierung der Photosynthesekapazität und den Austausch von CO2 und Wärme an der Bodenoberfläche. Desweiteren werden die Berechnungen zur Photosynthese, stomatären Leitfähigkeit und der Strahlungsabschwächung im Bestand mithilfe von Feldmessungen evaluiert. Das Teilmodell zum Vertikaltransport wird im Detail unter Verwendung von 222-Radon-Messungen evaluiert. Die ``Vorwärtslösung'' und der ``inverse Ansatz'' des Lagrangeschen Dispersionsmodells werden durch den Vergleich von beobachteten und vorhergesagten Konzentrationsprofilen bzw. Bodenflüssen bewertet. Ein neuer Ansatz wird hergeleitet, um die Unsicherheiten des inversen Ansatzes aus denjenigen des Eingabekonzentrationsprofils zu quantifizieren. Für nächtliche Bedingungen wird eine modifizierte Parametrisierung der Turbulenz vorgeschlagen, welche die freie Konvektion während der Nacht im unteren Bestand berücksichtigt und im Vergleich zu früheren Abschätzungen zu deutlich kürzeren Aufenthaltszeiten im Bestand führt. Die vorhergesagte Stratifizierung des Bestandes am Tage und in der Nacht steht im Einklang mit Beobachtungen in dichter Vegetation. Die Tagesgänge der vorhergesagten Flüsse und skalaren Profile von Temperatur, H2O, CO2, Isopren und O3 während der späten Regen- und Trockenzeit am Rondonia-Standort stimmen gut mit Beobachtungen überein. Die Ergebnisse weisen auf saisonale physiologische Änderungen hin, die sich durch höhere stomatäre Leitfähigkeiten bzw. niedrigere Photosyntheseraten während der Regen- und Trockenzeit manifestieren. Die beobachteten Depositionsgeschwindigkeiten für Ozon während der Regenzeit überschreiten diejenigen der Trockenzeit um 150-250%. Dies kann nicht durch realistische physiologische Änderungen erklärt werden, jedoch durch einen zusätzlichen cuticulären Aufnahmemechanismus, möglicherweise an feuchten Oberflächen. Der Vergleich von beobachteten und vorhergesagten Isoprenkonzentrationen im Bestand weist auf eine reduzierte Isoprenemissionskapazität schattenadaptierter Blätter und zusätzlich auf eine Isoprenaufnahme des Bodens hin, wodurch sich die globale Schätzung für den tropischen Regenwald um 30% reduzieren würde. In einer detaillierten Sensitivitätsstudie wird die VOC Emission von amazonischen Baumarten unter Verwendung eines neuronalen Ansatzes in Beziehung zu physiologischen und abiotischen Faktoren gesetzt. Die Güte einzelner Parameterkombinationen bezüglich der Vorhersage der VOC Emission wird mit den Vorhersagen eines Modells verglichen, das quasi als Standardemissionsalgorithmus für Isopren dient und Licht sowie Temperatur als Eingabeparameter verwendet. Der Standardalgorithmus und das neuronale Netz unter Verwendung von Licht und Temperatur als Eingabeparameter schneiden sehr gut bei einzelnen Datensätzen ab, scheitern jedoch bei der Vorhersage beobachteter VOC Emissionen, wenn Datensätze von verschiedenen Perioden (Regen/Trockenzeit), Blattentwicklungsstadien, oder gar unterschiedlichen Spezies zusammengeführt werden. Wenn dem Netzwerk Informationen über die Temperatur-Historie hinzugefügt werden, reduziert sich die nicht erklärte Varianz teilweise. Eine noch bessere Leistung wird jedoch mit physiologischen Parameterkombinationen erzielt. Dies verdeutlicht die starke Kopplung zwischen VOC Emission und Blattphysiologie.

A molecular phylogeny of bivalve mollusks: ancient radiations and divergences as revealed by mitochondrial genes

The main scope of my PhD is the reconstruction of the large-scale bivalve phylogeny on the basis of four mitochondrial genes, with samples taken from all major groups of the class. To my knowledge, it is the first attempt of such a breadth in Bivalvia. I decided to focus on both ribosomal and protein coding DNA sequences (two ribosomal encoding genes -12s and 16s -, and two protein coding ones - cytochrome c oxidase I and cytochrome b), since either bibliography and my preliminary results confirmed the importance of combined gene signals in improving evolutionary pathways of the group. Moreover, I wanted to propose a methodological pipeline that proved to be useful to obtain robust results in bivalves phylogeny. Actually, best-performing taxon sampling and alignment strategies were tested, and several data partitioning and molecular evolution models were analyzed, thus demonstrating the importance of molding and implementing non-trivial evolutionary models. In the line of a more rigorous approach to data analysis, I also proposed a new method to assess taxon sampling, by developing Clarke and Warwick statistics: taxon sampling is a major concern in phylogenetic studies, and incomplete, biased, or improper taxon assemblies can lead to misleading results in reconstructing evolutionary trees. Theoretical methods are already available to optimize taxon choice in phylogenetic analyses, but most involve some knowledge about genetic relationships of the group of interest, or even a well-established phylogeny itself; these data are not always available in general phylogenetic applications. The method I proposed measures the "phylogenetic representativeness" of a given sample or set of samples and it is based entirely on the pre-existing available taxonomy of the ingroup, which is commonly known to investigators. Moreover, it also accounts for instability and discordance in taxonomies. A Python-based script suite, called PhyRe, has been developed to implement all analyses.

Organic fertilization of peach trees: implication on nitrogen availability, root growth and carbon distribution within plant

In the last years, sustainable horticulture has been increasing; however, to be successful this practice needs an efficient soil fertility management to maintain a high productivity and fruit quality standards. For this purpose composted organic materials from agri-food industry and municipal solid waste has been used as a source to replace chemical fertilizers and increase soil organic matter. To better understand the influence of compost application on soil fertility and plant growth, we carried out a study comparing organic and mineral nitrogen (N) fertilization in micro propagated plants, potted trees and commercial peach orchard with these aims: 1. evaluation of tree development, CO2 fixation and carbon partition to the different organs of two-years-old potted peach trees. 2. Determination of soil N concentration and nitrate-N effect on plant growth and root oxidative stress of micro propagated plant after increasing rates of N applications. 3. Assessment of soil chemical and biological fertility, tree growth and yield and fruit quality in a commercial orchard. The addition of compost at high rate was effective in increasing CO2 fixation, promoting root growth, shoot and fruit biomass. Furthermore, organic fertilizers influenced C partitioning, favoring C accumulation in roots, wood and fruits. The higher CO2 fixation was the result of a larger tree leaf area, rather than an increase in leaf photosynthetic efficiency, showing a stimulation of plant growth by application of compost. High concentrations of compost increased total soil N concentration, but were not effective in increasing nitrate-N soil concentration; in contrast mineral-N applications increased linearly soil nitrate-N, even at the lowest rate tested. Soil nitrate-N concentration influenced positively plant growth at low rate (60- 80 mg kg-1), whereas at high concentrations showed negative effects. In this trial, the decrease of root growth, as a response to excessive nitrate-N soil concentration, was not anticipated by root oxidative stress. Continuous annual applications of compost for 10 years enhanced soil organic matter content and total soil N concentration. Additionally, high rate of compost application (10 t ha-1 year-1) enhanced microbial biomass. On the other hand, different fertilizers management did not modify tree yield, but influenced fruit size and precocity index. The present data support the idea that organic fertilizers can be used successfully as a substitute of mineral fertilizers in fruit tree nutrient management, since they promote an increase of soil chemical and biological fertility, prevent excessive nitrate-N soil concentration, promote plant growth and potentially C sequestration into the soil.

Novel techniques for the remote sensing of photosynthetic processes

Remote sensing (RS) techniques have evolved into an important instrument to investigate forest function. New methods based on the remote detection of leaf biochemistry and photosynthesis are being developed and applied in pilot studies from airborne and satellite platforms (PRI, solar-induced fluorescence; N and chlorophyll content). Non-destructive monitoring methods, a direct application of RS studies, are also proving increasingly attractive for the determination of stress conditions or nutrient deficiencies not only in research but also in agronomy, horticulture and urban forestry (proximal RS). In this work I will focus on some novel techniques recently developed for the estimation of photochemistry and photosynthetic rates based (i) on the proximal measurement of steady-state chlorophyll fluorescence yield, or (ii) the remote sensing of changes in hyperspectral leaf reflectance, associated to xanthophyll de-epoxydation and energy partitioning, which is closely coupled to leaf photochemistry and photosynthesis. I will also present and describe a mathematical model of leaf steady-state fluorescence and photosynthesis recently developed in our group. Two different species were used in the experiments: Arbutus unedo, a schlerophyllous Mediterranean species, and Populus euroamericana, a broad leaf deciduous tree widely used in plantation forestry. Results show that ambient fluorescence could provide a useful tool for testing photosynthetic processes from a distance. These results confirm also the photosynthetic reflectance index (PRI) as an efficient remote sensing reflectance index estimating short-term changes in photochemical efficiency as well as long-term changes in leaf biochemistry. The study also demonstrated that RS techniques could provide a fast and reliable method to estimate photosynthetic pigment content and total nitrogen, beside assessing the state of photochemical process in our plants’ leaves in the field. This could have important practical applications for the management of plant cultivation systems, for the estimation of the nutrient requirements of our plants for optimal growth.

Exact Algorithms for Different Classes of Vehicle Routing Problems

We deal with five problems arising in the field of logistics: the Asymmetric TSP (ATSP), the TSP with Time Windows (TSPTW), the VRP with Time Windows (VRPTW), the Multi-Trip VRP (MTVRP), and the Two-Echelon Capacitated VRP (2E-CVRP). The ATSP requires finding a lest-cost Hamiltonian tour in a digraph. We survey models and classical relaxations, and describe the most effective exact algorithms from the literature. A survey and analysis of the polynomial formulations is provided. The considered algorithms and formulations are experimentally compared on benchmark instances. The TSPTW requires finding, in a weighted digraph, a least-cost Hamiltonian tour visiting each vertex within a given time window. We propose a new exact method, based on new tour relaxations and dynamic programming. Computational results on benchmark instances show that the proposed algorithm outperforms the state-of-the-art exact methods. In the VRPTW, a fleet of identical capacitated vehicles located at a depot must be optimally routed to supply customers with known demands and time window constraints. Different column generation bounding procedures and an exact algorithm are developed. The new exact method closed four of the five open Solomon instances. The MTVRP is the problem of optimally routing capacitated vehicles located at a depot to supply customers without exceeding maximum driving time constraints. Two set-partitioning-like formulations of the problem are introduced. Lower bounds are derived and embedded into an exact solution method, that can solve benchmark instances with up to 120 customers. The 2E-CVRP requires designing the optimal routing plan to deliver goods from a depot to customers by using intermediate depots. The objective is to minimize the sum of routing and handling costs. A new mathematical formulation is introduced. Valid lower bounds and an exact method are derived. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.

Mineral chemistry and structural relationships of inclusions in diamond samples

Diamant ist das härteste Mineral – und dazu ein Edelstein -, das unter höchstem Druck und hohen Temperaturen in tiefen kontinentalen Regionen der Erde kristallisiert. Die Mineraleinschlüsse in Diamanten werden durch die physikalische Stabilität und chemische Beständigkeit der umgebenden – eigentlich metastabilen -Diamant-Phase geschützt. Aufgrund der koexistierenden Phasenkombination ermöglichen sie, die Mineral-Entwicklung zu studieren, während deren der Einschlüssen und die Diamanten kristallisierten. rnDie Phasenkombinationen von Diamant und Chrom-Pyrop, Chrom-Diopsid, Chromit, Olivin, Graphit und Enstatit nebeneinander (teilweise in Berührungsexistenz) mit Chrom-Pyrop Einschlüssen wurden von neunundzwanzig Diamant-Proben von sechs Standorten in Südafrika (Premier, Koffiefontein, De Beers Pool, Finsch, Venetia und Koingnaas Minen) und Udachnaya (Sibirien/Russland) identifiziert und charakterisiert. Die Mineraleinschlüsse weisen z.T. kubo-oktaedrische Form auf, die unabhängig von ihren eigenen Kristallsystemen ausgebildet werden können. Das bedeutet, dass sie syngenetische Einschlüsse sind, die durch die sehr hohe Formenergie des umgebenden Diamanten morphologisch unter Zwang stehen. Aus zweidiemnsionalen Messungen der ersten Ordnung von charakteristischen Raman-Banden lassen sich relative Restdrucke in Diamanten zwischen Diamant und Einschlussmineral gewinnen; sie haben charakteristische Werte von ca. 0,4 bis 0,9 GPa um Chrom-Pyrop-Einschlüsse, 0,6 bis 2,0 GPa um Chrom-Diopsid-Einschlüsse, 0,3 bis 1,2 GPa um Olivin-Einschlüsse, 0,2 bis 1,0 GPa um Chromit-Einschlüsse, beziehungsweise 0,5 GPa um Graphit Einschlüsse.rnDie kristallstrukturellen Beziehung von Diamanten und ihren monomineralischen Einschlüssen wurden mit Hilfe der Quantifizierung der Winkelkorrelationen zwischen der [111] Richtung von Diamanten und spezifisch ausgewählten Richtungen ihrer mineralischen Einschlüsse untersucht. Die Winkelkorrelationen zwischen Diamant [111] und Chrom-Pyrop [111] oder Chromit [111] zeigen die kleinsten Verzerrungen von 2,2 bis zu 3,4. Die Chrom-Diopsid- und Olivin-Einschlüsse zeigen die Missorientierungswerte mit Diamant [111] bis zu 10,2 und 12,9 von Chrom-Diopsid [010] beziehungsweise Olivin [100].rnDie chemische Zusammensetzung von neun herausgearbeiteten (orientiertes Anschleifen) Einschlüssen (drei Chrom-Pyrop-Einschlüsse von Koffiefontein-, Finsch- und Venetia-Mine (zwei von drei koexistieren nebeneinander mit Enstatit), ein Chromit von Udachnaya (Sibirien/Russland), drei Chrom-Diopside von Koffiefontein, Koingnaas und Udachnaya (Sibirien/Russland) und zwei Olivin Einschlüsse von De Beers Pool und Koingnaas) wurden mit Hilfe EPMA und LA-ICP-MS analysiert. Auf der Grundlage der chemischen Zusammensetzung können die Mineraleinschlüsse in Diamanten in dieser Arbeit der peridotitischen Suite zugeordnet werden.rnDie Geothermobarometrie-Untersuchungen waren aufgrund der berührenden Koexistenz von Chrom-Pyrop- und Enstatit in einzelnen Diamanten möglich. Durchschnittliche Temperaturen und Drücke der Bildung sind mit ca. 1087 (± 15) C, 5,2 (± 0,1) GPa für Diamant DHK6.2 von der Koffiefontein Mine beziehungsweise ca. 1041 (± 5) C, 5,0 (± 0,1) GPa für Diamant DHF10.2 von der Finsch Mine zu interpretieren.rn

Water-soluble organic compounds in air particulate matter analyzed by HPLC-DAD-MS and HPLC-MS/MS: abundance, sources and transformation of carboxylic acids, nitrophenols and nitrated proteins

Wasserlösliche organische Verbindungen (WSOCs) sind Hauptbestandteile atmosphärischer Aerosole, die bis zu ~ 50% und mehr der organischen Aerosolfraktion ausmachen. Sie können die optischen Eigenschaften sowie die Hygroskopizität von Aerosolpartikeln und damit deren Auswirkungen auf das Klima beeinflussen. Darüber hinaus können sie zur Toxizität und Allergenität atmosphärischer Aerosole beitragen.In dieser Studie wurde Hochleistungsflüssigchromatographie gekoppelt mit optischen Diodenarraydetektion und Massenspektrometrie (HPLC-DAD-MS und HPLC-MS/MS) angewandt, um WSOCs zu analysieren, die für verschiedene Aerosolquellen und -prozesse charakteristisch sind. Niedermolekulare Carbonsäuren und Nitrophenole wurden als Indikatoren für die Verbrennung fossiler Brennstoffe und die Entstehung sowie Alterung sekundärer organischer Aerosole (SOA) aus biogenen Vorläufern untersucht. Protein-Makromoleküle wurden mit Blick auf den Einfluss von Luftverschmutzung und Nitrierungsreaktionen auf die Allergenität primärer biologischer Aerosolpartikel – wie Pollen und Pilzsporen – untersucht.rnFilterproben von Grob- und Feinstaubwurden über ein Jahr hinweg gesammelt und auf folgende WSOCs untersucht: die Pinen-Oxidationsprodukte Pinsäure, Pinonsäure und 3-Methyl-1,2,3-Butantricarbonsäure (3-MBTCA) sowie eine Vielzahl anderer Dicarbonsäuren und Nitrophenole. Saisonale Schwankungen und andere charakteristische Merkmale werden mit Blick auf Aerosolquellen und -senken im Vergleich zu Daten anderen Studien und Regionen diskutiert. Die Verhätlnisse von Adipinsäure und Phthalsäure zu Azelainsäure deuten darauf hin, dass die untersuchten Aerosolproben hauptsächlich durch biogene Quellen beeinflusst werden. Eine ausgeprägte Arrhenius-artige Korrelation wurde zwischen der 3-MBTCA-¬Konzentration und der inversen Temperatur beobachtet (R2 = 0.79, Ea = 126±10 kJ mol-1, Temperaturbereich 275–300 K). Modellrechnungen zeigen, dass die Temperaturabhängigkeit auf eine Steigerung der photochemischen Produktionsraten von 3-MBTCA durch erhöhte OH-Radikal-Konzentrationen bei erhöhten Temperaturen zurückgeführt werden kann. Im Vergleich zur chemischen Reaktionskinetik scheint der Einfluss von Gas-Partikel-Partitionierungseffekten nur eine untergeordnete Rolle zu spielen. Die Ergebnisse zeigen, dass die OH-initiierte Oxidation von Pinosäure der geschwindigkeitsbestimmende Schritt der Bildung von 3-MBTCA ist. 3-MBTCA erscheint somit als Indikator für die chemische Alterung von biogener sekundärer organischer Aerosole (SOA) durch OH-Radikale geeignet. Eine Arrhenius-artige Temperaturabhängigkeit wurde auch für Pinäure beobachtet und kann durch die Temperaturabhängigkeit der biogenen Pinen-Emissionen als geschwindigkeitsbestimmender Schritt der Pinsäure-Bildung erklärt werden (R2 = 0.60, Ea = 84±9 kJ mol-1).rn rnFür die Untersuchung von Proteinnitrierungreaktionen wurde nitrierte Protein¬standards durch Flüssigphasenreaktion von Rinderserumalbumin (BSA) und Ovalbumin (OVA) mit Tetranitromethan (TNM) synthetisiert.Proteinnitrierung erfolgt vorrangig an den Resten der aromatischen Aminosäure Tyrosin auf, und mittels UV-Vis-Photometrie wurde der Proteinnnitrierungsgrad (ND) bestimmt. Dieser ist definiert als Verhältnis der mittleren Anzahl von Nitrotyrosinresten zur Tyrosinrest-Gesamtzahl in den Proteinmolekülen. BSA und OVA zeigten verschiedene Relationen zwischen ND und TNM/Tyrosin-Verhältnis im Reaktionsgemisch, was vermutlich auf Unterschiede in den Löslichkeiten und den molekularen Strukturen der beiden Proteine zurück zu führen ist.rnDie Nitrierung von BSA und OVA durch Exposition mit einem Gasgemisch aus Stickstoffdioxid (NO2) und Ozon (O3) wurde mit einer neu entwickelten HPLC-DAD-¬Analysemethode untersucht. Diese einfache und robuste Methode erlaubt die Bestimmung des ND ohne Hydrolyse oder Verdau der untersuchten Proteine und ernöglicht somit eine effiziente Untersuchung der Kinetik von Protein¬nitrierungs-Reaktionen. Für eine detaillierte Produktstudien wurden die nitrierten Proteine enzymatisch verdaut, und die erhaltenen Oligopeptide wurden mittels HPLC-MS/MS und Datenbankabgleich mit hoher Sequenzübereinstimmung analysiert. Die Nitrierungsgrade individueller Nitrotyrosin-Reste (NDY) korrelierten gut mit dem Gesamt-Proteinnitrierungsgrad (ND), und unterschiedliche Verhältnisse von NDY zu ND geben Aufschluss über die Regioselektivität der Reaktion. Die Nitrierungmuster von BSA und OVA nach Beahndlung mit TNM deuten darauf hin, dass die Nachbarschaft eines negativ geladenen Aminosäurerestes die Tyrosinnitrierung fördert. Die Behandlung von BSA durch NO2 und O3 führte zu anderend Nitrierungemustern als die Behandlung mit TNM, was darauf hindeutet, dass die Regioselektivität der Nitrierung vom Nitrierungsmittel abhängt. Es zeigt sich jedoch, dass Tyrosinreste in Loop-Strukturen bevorzugt und unabhängig vom Reagens nitriert werden.Die Methoden und Ergebnisse dieser Studie bilden eine Grundlage für weitere, detaillierte Untersuchungen der Reaktionskinetik sowie der Produkte und Mechanismen von Proteinnitrierungreaktionen. Sie sollen helfen, die Zusammenhänge zwischen verkehrsbedingten Luftschadstoffen wie Stickoxiden und Ozon und der Allergenität von Luftstaub aufzuklären.rn

Lernen mit einer Hybride aus Lernendem Klassifizierendem System und Selbstorganisierender Karte

Im Forschungsgebiet der Künstlichen Intelligenz, insbesondere im Bereich des maschinellen Lernens, hat sich eine ganze Reihe von Verfahren etabliert, die von biologischen Vorbildern inspiriert sind. Die prominentesten Vertreter derartiger Verfahren sind zum einen Evolutionäre Algorithmen, zum anderen Künstliche Neuronale Netze. Die vorliegende Arbeit befasst sich mit der Entwicklung eines Systems zum maschinellen Lernen, das Charakteristika beider Paradigmen in sich vereint: Das Hybride Lernende Klassifizierende System (HCS) wird basierend auf dem reellwertig kodierten eXtended Learning Classifier System (XCS), das als Lernmechanismus einen Genetischen Algorithmus enthält, und dem Wachsenden Neuralen Gas (GNG) entwickelt. Wie das XCS evolviert auch das HCS mit Hilfe eines Genetischen Algorithmus eine Population von Klassifizierern - das sind Regeln der Form [WENN Bedingung DANN Aktion], wobei die Bedingung angibt, in welchem Bereich des Zustandsraumes eines Lernproblems ein Klassifizierer anwendbar ist. Beim XCS spezifiziert die Bedingung in der Regel einen achsenparallelen Hyperquader, was oftmals keine angemessene Unterteilung des Zustandsraumes erlaubt. Beim HCS hingegen werden die Bedingungen der Klassifizierer durch Gewichtsvektoren beschrieben, wie die Neuronen des GNG sie besitzen. Jeder Klassifizierer ist anwendbar in seiner Zelle der durch die Population des HCS induzierten Voronoizerlegung des Zustandsraumes, dieser kann also flexibler unterteilt werden als beim XCS. Die Verwendung von Gewichtsvektoren ermöglicht ferner, einen vom Neuronenadaptationsverfahren des GNG abgeleiteten Mechanismus als zweites Lernverfahren neben dem Genetischen Algorithmus einzusetzen. Während das Lernen beim XCS rein evolutionär erfolgt, also nur durch Erzeugen neuer Klassifizierer, ermöglicht dies dem HCS, bereits vorhandene Klassifizierer anzupassen und zu verbessern. Zur Evaluation des HCS werden mit diesem verschiedene Lern-Experimente durchgeführt. Die Leistungsfähigkeit des Ansatzes wird in einer Reihe von Lernproblemen aus den Bereichen der Klassifikation, der Funktionsapproximation und des Lernens von Aktionen in einer interaktiven Lernumgebung unter Beweis gestellt.

Use of shared memory in the context of embedded multi-core processors: exploration of the technology and its limits

Modern embedded systems embrace many-core shared-memory designs. Due to constrained power and area budgets, most of them feature software-managed scratchpad memories instead of data caches to increase the data locality. It is therefore programmers’ responsibility to explicitly manage the memory transfers, and this make programming these platform cumbersome. Moreover, complex modern applications must be adequately parallelized before they can the parallel potential of the platform into actual performance. To support this, programming languages were proposed, which work at a high level of abstraction, and rely on a runtime whose cost hinders performance, especially in embedded systems, where resources and power budget are constrained. This dissertation explores the applicability of the shared-memory paradigm on modern many-core systems, focusing on the ease-of-programming. It focuses on OpenMP, the de-facto standard for shared memory programming. In a first part, the cost of algorithms for synchronization and data partitioning are analyzed, and they are adapted to modern embedded many-cores. Then, the original design of an OpenMP runtime library is presented, which supports complex forms of parallelism such as multi-level and irregular parallelism. In the second part of the thesis, the focus is on heterogeneous systems, where hardware accelerators are coupled to (many-)cores to implement key functional kernels with orders-of-magnitude of speedup and energy efficiency compared to the “pure software” version. However, three main issues rise, namely i) platform design complexity, ii) architectural scalability and iii) programmability. To tackle them, a template for a generic hardware processing unit (HWPU) is proposed, which share the memory banks with cores, and the template for a scalable architecture is shown, which integrates them through the shared-memory system. Then, a full software stack and toolchain are developed to support platform design and to let programmers exploiting the accelerators of the platform. The OpenMP frontend is extended to interact with it.

Stable isotope fractionation of selenium by biomethylation in soil

Selen ist in geringen Mengen ein essentielles Nährelement, das aber in höheren Gehalten toxisch wird. Der Se-Kreislauf in der Umwelt ist eng mit Redoxreaktionen wie der Reduktion von Se-Oxyanionen zu Methylselenid verknüpft. Flüchtige Methylselenide sind weit verbreitet und stellen einen wichtigen Se-Fluss in der Umwelt dar. Das übergeordnete Ziel meiner Dissertation war, die Stabilisotopenfraktionierung von Se durch Biomethylierung verschiedener oxidierter Se-Spezies (Se[IV] und Se[VI]) im Boden aufzuklären. Zunächst wurde eine Methode entwickelt, die es erlaubte flüchte Methylselenide quantitativ zurückzuhalten. Es zeigte sich, dass alkalische Peroxid-Lösung dafür geeignet war. Mit alkalischer Peroxid-Lösung wurde eine Wiederfindung von 95,6 ± Standardabweichung 5,4% in Verflüchtigungsexperimenten mit Methylselenid-Standards erreicht. Bei Einsatz von alkalischer Peroxid-Lösung in geschlossenen Mikrokosmos-Experimenten kam es zu keinen Se-Verlusten und ausgeglichenen Se-Isotopenbilanzen. Die massengewichteten δ82/76Se-Werte lagen für Se(IV) und Se(VI) am Ende der Mikrokosmos-Inkubationen bei -0,31 ± 0,05‰ (n = 3) und -0,76 ± 0,07‰ (n = 3) verglichen mit -0,20 ± 0,05‰ und -0,69 ± 0,07‰ im jeweils zugegebenen Se. Im zweiten Teil meiner Dissertation wurde die Pilzart Alternaria alternata mit Se(VI) und Se(IV) in geschlossenen Mikrokosmen für 11-15 und Se(IV) zusätzlich für 3-5 Tage bei 30°C inkubiert. In 11-15 Tagen wurden 2,9-11% des Se(VI) und 21-29% des Se(IV) und in 3-5 Tagen, 3-5% des Se(IV) methyliert. Die anfänglichen δ82/76Se-Werte von Se(VI) und Se(IV) lagen bei -0,69 ± 0,07‰, und -0,20 ± 0,05‰. Die δ82/76Se-Werte der Methylselenide unterschieden sich nach 11-15 Tagen Inkubation signifikant zwischen Se(VI) (-3,97 bis -3,25 ‰) und Se(IV) (-1,44 bis -0,16‰) als Quellen. Die δ82/76Se-Werte der Methylselenide zeigen also die Quellen der Biomethylierung von Se an. Die kürzere Inkubation von Se(IV) für 3-5 Tage führte zu einer ausgeprägten Se-Isotopenfraktonierung von mindestens -6‰, bevor ein Fließgleichgewicht erreicht wurde. Im dritten Teil bestimmte ich die Bindungsformen von Se mit drei operativ definierten sequentiellen Extraktionen und die δ82/76S-Werte des gesamten Selens in zehn urbanen Oberböden mit 0,09-0,52 mg/kg Se, die fünf verschiedene Landnutzungstypen repräsentierten (Überschwemmungsgrünland, Garten, Park, Straßenrand und Wald). Nur ein kleiner Teil des Seleniums lag in austauschbarer und damit direkt bioverfügbarer und in residualer, wenig reaktiver Form vor. Das meiste Se war an die organische Substanz und Fe-(Hydr-)Oxide gebunden (42-77% des gesamten Selens). Der mittlere δ82/76Se-Wert des gesamten Selens in den Oberböden lag mit -0,03 ± 0,38‰ nahe beim Mittelwert der gesamten Erde. Geringfügig niedrigere Se-Isotopensignale von -0,59 bis -0,35‰ v.a. in Waldböden und geringfügig höhere von 0,26 to 0,45‰ in Überschwemmungsgrünland wurden vermutlich durch Boden-Pflanze-Recycling und Se-Kontaminationen durch das Flusswasser verursacht. Der vierte Teil umfasste ein “Natural Attenuation”-Experiment und Mikrokosmos-Inkubationen von Bodenproben mit A. alternata. Die Equilibrierung von zum Boden gegebenem Se(IV) und Se(VI) für drei Tage führte zu abnehmenden wasserlöslichen Se-Gehalten um 32-44% bzw. 8-14, die mit kleinen Isotopenfraktionierung (ε = -0,045 bis -0,12 ‰ and -0,05 to -0,07‰ verbunden waren. In zwei der inkubierten Böden mit mäßig sauren pH-Werten wurden zwischen 9,1 und 30% des zugefügten Se(IV) und 1,7% des zugefügten Se(VI) methyliert während in einem stark sauren Boden keine Methylierung auftrat. Das aus Se(IV) entstandene Methylselenid war deutlich gegenüber dem zugegebenen Se-Standard (0,20‰) an 82Se verarmt (δ82/76Se = -3,3 bis -4,5‰). Meine Ergebnisse zeigen, dass die stabilen Isotopenverhältnisse von Se neue Einblicke in Se-Transformationsprozesse erlauben.rn

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.

Intra- and interspecific competition in western barbastelle bats (Barbastella barbastellus, SCHREBER 1774)

In the present thesis I examined individual and sex-specific habitat use and site fidelity in the western barbastelle bat, Barbastella barbastellus, using data from a four-year monitoring in a Special Area of Conservation in Rhineland-Palatinate, Germany. The western barbastelle occurs in central and southern Europe from Portugal to the Caucasus, but is considered to be rare in large parts of its range. Up to now, long-term field studies to assess interannual site fidelity and the possible effects of intra- and interspecific competition have not been studied in this species. Nevertheless, such data provide important details to estimate the specific spatial requirements of its populations, which in turn can be incorporated in extended conservation actions. I used radio-telemetry, home range analyses und automated ultrasound detection to assess the relation between landscape elements and western barbastelle bats and their roosts. In addition, I estimated the degree of interspecific niche overlap with two selected forest-dwelling bat species, Bechstein's bat (Myotis bechsteinii) and the brown long-eared bat (Plecotus auritus). Intra- and interannual home range overlap analyses of female B. barbastellus revealed that fidelity to individual foraging grounds, i.e. a traditional use of particular sites, seems to effect the spatial distribution of home ranges more than intraspecific competition among communally roosting females. The results of a joint analysis of annual maternity roost selection and flight activities along commuting corridors highlight the necessity to protect roost complexes in conjunction with commuting corridors. Using radio-tracking data and an Euclidean distance approach I quantified the sex-specific and individual habitat use by female and male western barbastelle bats within their home ranges. My data indicated a partial sexual segregation in summer habitats. Females were found in deciduous forest patches and preferably foraged along linear elements within the forest. Males foraged closer to forest edges and in open habitats. Finally, I examined the resource partitioning between the western barbastelle bat and two syntopic bat species with a potential for interspecific competition due to similarities in foraging strategies, prey selection and roost preferences. Simultaneous radio-tracking of mixed-species pairs revealed a partial spatial separation of the three syntopic bat species along a gradient from the forest to edge habitats and open landscape. Long-eared bats were found close to open habitats which were avoided by the other two species. B. barbastellus preferred linear landscape elements (edge habitats) and forests, M. bechsteinii also preferred forest habitats. Only little overlap in terms of roost structure and tree species selection was found.

Massenspektrometrische Untersuchungen des Komplexierungsverhaltens von Actinid-Ionen in Lösung

Da die Langzeit-Radiotoxizität von abgebrannten Kernbrennstoffen von Plutonium und den minoren Actiniden dominiert wird, sind diese Elemente im Fokus der Untersuchungen bezüglich der Entsorgung der radioaktiven Abfälle.rnUm ein besseres Verständnis der Selektivität der Partitioning-Liganden BTP und BTBP bezüglich der Extraktion von trivalenten Actiniden zu erlangen, wurden die Komplexe, die diese mit Lanthaniden in octanolischer Lösung bilden charakterisiert. Das unterschiedliche Extraktionsverhalten der Lanthaniden untereinander konnte dabei auf unterschiedliche Präferenz zur Bildung von Ln(BTP)3-Komplexen abhängig vom Ionenradius der Lanthaniden zurückgeführt werden. Darüber hinaus konnte gezeigt werden, dass abhängig vom sterischen Anspruch der BTBP-Liganden in Eu(BTBP)2-Komplexen Nitratliganden in der ersten Koordinationssphäre gebunden werden. rnDa das Verhalten von Plutonium unter geochemischen Bedingungen von besonderem Interesse für die Risikoabschätzung von nuklearen Endlagern ist, widmet sich der zweite Teil der Arbeit dem Hydrolyse- und Kolloidbildungsverhalten von wässrigen Plutoniumlösungen in den Oxidationsstufen IV bis VI. Daher wurden die Lösungsspezies von sowohl Zirconium(IV) als Analogon für Plutonium(IV), als auch die von Uran(VI) und Plutonium(VI) direkt mittels massenspektrometrischer Methoden charakterisiert und quantifiziert. Darüber hinaus wurde die kinetische Hemmung der Reduktion von Pu(V) zu Pu(IV) und nachfolgender Kolloidbildung untersucht, welche sich durch oberflächeninduzierte Reduktion an kolloidalen Kristallisationskeimen deutlich beschleunigen lässt.rn