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.

Entwicklung eines Verfahrens zur Ultraspurenbestimmung der Platingruppenelemente in Umwelt- und geologischen Proben mit einem ICP-QMS unter Verwendung der Isotopenverdünnungsanalyse sowie geeigneter Separationstechniken

ZusammenfassungSchwerpunkt dieser Arbeit war die Verfahrensentwicklung zur Ultraspurenbestimmung der Platingruppenelemente (PGE) in Umwelt- und geologischen Proben unter Verwendung der massenspektrometrischen Isotopenverdünnungsanalyse mit anschließender Bestimmung an einem Quadrupol ICP-MS (ICP-QMSIVA). Geeignete Separationstechniken in der Probenaufbereitung, um die PGE von der Matrix der untersuchten Proben zu trennen, stellten eine richtige und präzise Bestimmung der Ultraspuren an einem Quadrupol ICP-MS sicher.Das Verfahren konnte anhand von geologischen Referenzmaterialien aus Kanada sichergestellt werden. Gerade die Wiederholungsbestimmungen der verschiedenen Referenzmaterialien unter Verwendung des ICP-QMSIVA Verfahrens sind beispiellos und in dieser Form noch nicht in der Literatur beschrieben. Durch systematische Messungen konnten Richtigkeit und Präzision des Verfahrens bestätigt werden und die Inhomogenität des Referenzmaterials UMT-1 bezüglich Pt bewiesen werden. Das in dieser Arbeit entwickelte Verfahren zur Ultraspurenbestimmung der PGE mit ICP-QMSIVA wurde im Rahmen des Projektes 'Production and certification of a road dust reference material for platinum, palladium and rhodium (PGEs) in automative catalytic converters (PACEPAC)' der Europäischen Union zur Zertifizierung von zwei Referenzmaterialien für Umweltproben eingesetzt. Hierbei wurde bei der Zertifizierung ('intercomparison round') eine sehr gute Übereinstimmung der Ergebnisse mit dem gewichteten Mittelwert der Ergebnisse für Pd und Pt mit den übrigen teilnehmenden Laboratorien festgestellt. Die mit der hier entwickelten Methode erhaltenen Ergebnisse wurden ohne Ausnahme für alle gemessenen Elemente zur Zertifizierung herangezogen. Damit leistete die vorliegende Arbeit einen erheblichen Beitrag zum erfolgreichen Abschluß dieses Projekts. Den Erwartungen hinsichtlich Richtigkeit und Reproduzierbarkeit des entwickelten Verfahrens wurde somit voll entsprochen. Erneut konnte die große Bedeutung der Isotopenverdünnungstechnik für die Zertifizierung von Referenzmaterialien aufgezeigt werden, da mit dieser Technik bei sachgerechtem Einsatz Ergebnisse hoher Richtigkeit erzielt werden. Durch vergleichende Messungen mit der NiS-Dokimasie und NAA, die in einer Kooperation mit dem Kernchemischen Institut der Universität Mainz durchgeführt wurden, und dem hier verwendeten Verfahren, konnten übereinstimmende Daten, hinsichtlich der Abnahme der Konzentrationen von Pd und Pt in Abhängigkeit von der Entfernung zu einer Autobahn, erzielt werden. Diese Arbeit und die Forschungsergebnisse, die mit der anerkannten NAA erzielt wurden, zeigen, daß die PGE durch Katalysatoren von Automobilen überwiegend metallisch emittiert werden. Der anthropogene Eintrag der PGE in die Umwelt kann mit dem ICP-QMSIVA Verfahren weiterhin sehr gut verfolgt werden.

Entwicklung einer Methode mittels hochauflösender ICP-MS zur Bestimmung von Siliciumspuren in anorganischen und organischen Matrices sowie von Siloxanen in Geweben

Deutsch:Schwerpunkt dieser Arbeit war die Entwicklung einer Methode zur Spurenbestimmung von Silicium in organischen und anorganischen Matrices unter Verwendung der massenspektrometrischen Isotopenverdünnungsanalyse (MSIVA) an einem hochauflösenden induktiv gekoppelten Plasma-Massenspektrometer (HR-ICP-MS). Zusätzlich zur Elementspurenbestimmung wurde eine GC/HR-ICP-MS Kopplung entwickelt, die zur Analyse linearer und cyclischer Siloxane verwendet wurde.Die hier entwickelte Analysenmethode erlaubt Nachweisgrenzen für Silicium sowohl in organischen als auch in anorganischen Matrices im oberen ng/g-Bereich und ergab für die im Rahmen dieser Arbeit analysierten Proben Reproduzierbarkeiten von < 20%. Durch einfache Verdünnung nach der Probenvorbereitung in Verbindung mit dem sehr empfindlichen Detektionsverfahren sowie der internen Standardisierung mittels MSIVA erlaubt das Verfahren eine präzise Bestimmung von Silicium in jeglicher Matrix. Neben der Schnelligkeit und Einfachheit eignet sich die hier entwickelte Methode besonders für die Routineanalytik. Die gute Reproduzierbarkeit und der Vergleich mit Ergebnissen von zwei Interlaborstudien unterstreicht zusätzlich die Fähigkeit präzise und richtige Ergebnisse zur Zertifizierung an Standardreferenzmaterialien bezüglich des Siliciums im Spurenbereich zu liefern.Neben dem Gesamtgehalt von Silicium konnten medizinisch relevante Siliciumverbindungen analysiert und quantifiziert werden. Hierbei wurden niedermolekulare Polydimethlysiloxane (PDMS) untersucht, die als Nebenprodukte vor allem in Brustimplantaten auftreten. Grundlage für die Bestimmung dieser Siliciumspezies ist die Kopplung eines hochauflösenden ICP-MS an einen Gaschromatographen. Der hohe Ionisierungsgrad des ICP, gerade unter trockenen Plasmabedingungen, und der elementspezifische und sehr empfindliche massenspektrometrische Detektor erlauben in Verbindung mit dem GC die Bestimmung von Siloxanen bis in den pg/g-Bereich. Aus der Bestimmung des Gesamtgehalts an Silicium und der Bestimmung des Gehalts an den untersuchten Siliciumverbindungen können Vergleiche gemacht werden. Die Analyse beider Parameter ist mit Hilfe in dieser Arbeit entwickelten Methode möglich.Zusätzlich zur Siliciumbestimmung wurde der Gehalt an Platin in Humanproben analysiert, da bei der Herstellung der Füllung von Siliconimplantaten Platinkatalysatoren verwendet werden.

Massenspektrometrische Wasserdampfmessung in der oberen Troposphäre und unteren Stratosphäre

Diese Arbeit beschreibt die Entwicklung des flugzeuggetragenen Atmosphärischen Ionisations-Massenspektrometers AIMS-H2O zur Messung von Wasserdampf in der oberen Troposphäre und unteren Stratosphäre (UTLS) und erste Flugzeugmessungen mit dem Instrument. Wasserdampf beeinflusst das Klima in der UTLS aufgrund seiner Strahlungseigenschaften und agiert als wichtiger Parameter bei der Bildung von Zirruswolken und Kondensstreifen. Deshalb sind genaue Wasserdampfmessungen für das Verständnis vieler atmosphärischer Prozesse unerlässlich. Instrumentenvergleiche wie sie im SPARC Report No. 2 und dem Bericht der AUQAVIT Kampagne zusammengefasst sind, haben gezeigt, dass große Abweichungen zwischen einzelnen Methoden und Instrumenten bestehen. Diese Unsicherheiten limitieren das Verständnis des Einflusses von Wasserdampf auf die Dynamik und die Strahlungseigenschaften in der UTLS. Die in dieser Arbeit vorgestellte Entwicklung einer neuen Messmethode für Wasserdampf mit dem Massenspektrometer AIMS-H2O ist deshalb auf die genaue Messung niedriger Wasserdampfkonzentrationen in der UTLS fokussiert. Mit AIMS H2O wird Umgebungsluft in einer neu entwickelten Gasentladungsquelle ionisiert. Durch eine Reihe von Ionen-Molekül-Reaktionen entstehen H3O+(H2O) und H3O+(H2O)2 Ionen. Diese Ionen werden genutzt, um die Wasserdampfkonzentration in der Atmosphäre zu bestimmen. Um die erforderliche hohe Genauigkeit zu erzielen, wird AIMS H2O im Flug kalibriert. In dem zu diesem Zweck aufgebauten Kalibrationsmodul wird die katalytische Reaktion von Wasserstoff und Sauerstoff auf einer Platinoberfläche genutzt, um definierte Wasserdampfkonzentrationen für die Kalibration im Flug zu erzeugen. Bei ersten Messungen auf der Falcon während der Kampagne CONCERT 2011 konnte dabei eine Genauigkeit von 8 bis 15% für die Messung der Wasserdampfkonzentration in einem Messbereich von 0,5 bis 250 ppmv erreicht werden. Die Messfrequenz betrug 4 Hz, was einer räumlichen Auflösung von etwa 50 m entspricht. Der Vergleich der Messung des Massenspektrometers mit dem Laserhygrometer Waran zeigt eine sehr gute Übereinstimmung im Rahmen der Unsicherheiten. Anhand zweier Fallstudien werden die Messungen von AIMS H2O während CONCERT 2011 detailliert analysiert. In der ersten Studie werden zwei Flüge in eine stratosphärische Intrusion über Nordeuropa untersucht. In dieser Situation wurde stratosphärische Luft bis hinunter auf 6 km Höhe transportiert und war dadurch mit der Falcon erreichbar. Es konnte gezeigt werden, dass AIMS-H2O sehr gut für die genaue Messung niedriger Wasserdampfkonzentrationen, in diesem Fall bis etwa 3,5 ppmv, geeignet ist. Der Vergleich der Messung mit Analysen des ECMWF Integrated Forecast Systems zeigt eine gute Übereinstimmung der gemessenen Wasserdampfstrukturen mit der dynamischen Tropopause. Unterschiede tauchen dagegen beim Vergleich der Wasserdampfkonzentrationen in der unteren Stratosphäre auf. Hier prognostiziert das Modell deutlich höhere Feuchten. Die zweite Fallstudie beschäftigt sich mit der Verteilung der relativen Feuchte in jungen Kondensstreifen im Vergleich zu ihrer direkten Umgebung. Dabei wurde für drei Messsequenzen im Abgasstrahl von Flugzeugen beobachtet, dass die relative Feuchte innerhalb des Kondensstreifens im Vergleich zur Umgebung sowohl bei unter- als auch übersättigten Umgebungsbedingungen in Richtung Sättigung verschoben ist. Die hohe Anzahl an Eispartikeln und die damit verbundene große Eisoberfläche in jungen Kondensstreifen führt also zu einer schnellen Relaxation von Gasphase und Eis in Richtung Gleichgewicht. In der Zukunft soll AIMS-H2O auch auf HALO für die genaue Messung von Wasserdampf bei ML-CIRRUS und weiteren Kampagnen eingesetzt werden.

Sustainable development in Darjeeling Hills, India : ecological and socio-economic aspects for small-scale farmers with supportive observations from Kanagawa, Japan

Organic farming means a holistic application of agricultural land-use, hence, this study aimed to assess ecological and socio-economic aspects that show benefits of the strategy and achievements of organic farming in comparison to conventional farming in Darjeeling District, State of West Bengal, India and Kanagawa Prefecture/Kanto in Central Japan. The objective of this study has been empirically analysed on aspects of crop diversity, yield, income and sales prices in the two study regions, where 50 households each, i.e. in total 100 households were interviewed at farm-level. Therefore, the small sample size does not necessarily reflect the broad-scale of the use and benefit of organic farming in both regions. The problems faced in mountainous regions in terms of agriculture and livelihoods for small-scale farmers, which are most affected and dependant on their immediate environment, such as low yields, income and illegal felling leading to soil erosion and landslides, are analyzed. Furthermore, factors such as climate, soils, vegetation and relief equally play an important role for these farmers, in terms of land-use. To supplement and improve the income of farmers, local NGOs have introduced organic farming and high value organic cash crops such as ginger, tea, orange and cardamom and small income generating means (floriculture, apiary etc.). For non-certified and certified organic products the volume is given for India, while for Japan only certified organic production figures are given, as there are several definitions for organic in Japan. Hence, prior to the implementation of organic laws and standards, even reduced chemical input was sold as non-certified organic. Furthermore, the distribution and certification system of both countries are explained in detail, including interviews with distribution companies and cooperatives. Supportive observations from Kanagawa Prefecture and the Kanto region are helpful and practical suggestions for organic farmers in Darjeeling District. Most of these are simple and applicable soil management measures, natural insect repelling applications and describe the direct marketing system practiced in Japan. The former two include compost, intercropping, Effective Microorganisms (EM), clover, rice husk charcoal and wood vinegar. More supportive observations have been made at organic and biodynamic tea estates in Darjeeling District, which use citronella, neem, marigold, leguminous and soil binding plants for soil management and natural insect control. Due to the close ties between farmers and consumers in Japan, certification is often neither necessary nor wanted by the producers. They have built a confidence relationship with their customers; thus, such measures are simply not required. Another option is group certification, instead of the expensive individual certification. The former aims at lower costs for farmers who have formed a cooperative or a farmers' group. Consumer awareness for organic goods is another crucial aspect to help improve the situation of organic farmers. Awareness is slightly more advanced in Kanto than in Darjeeling District, as it is improved due to the close (sales) ties between farmers and consumers in Kanto. Interviews conducted with several such cooperatives and companies underline the positive system of TEIKEI. The introduction of organic farming in the study regions has shown positive effects for those involved, even though it still in its beginning stages in Darjeeling District. This study was only partly able to assess the benefits of organic agriculture at its present level for Darjeeling District, while more positively for the organic farmers of Kanto. The organic farming practice needs further improvement, encouragement and monitoring for the Darjeeling District farmers by locals, consumers, NGOs and politicians. The supportive observations from Kanagawa Prefecture and the Kanto region are a small step in this direction, showing how, simple soil improvements and thus, yield and income increases, as well as direct sales options can enhance the livelihood of organic farmers without destroying their environment and natural resources.