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.

Paleoclimate reconstruction using LA-ICP-MS analyses of ostracods and stalagmite

Als paläoklimatische Archive können unter anderem Stalagmiten und Klappen von Ostrakoden herangezogen werden. Bisher gab es noch keine veröffentlichten Ergebnisse räumlich hochaufgelöster Spurenelementverteilungen in einzelnen Ostrakodenklappen. Das gleiche gilt für die Bestimmung radiogener Blei-Isotope in Stalagmiten. Um klimatische Prozesse vergangener Zeiten zu untersuchen, wurde eine neue LA-ICP-MS (Laserablations – Massenspektrometrie mit induktiv gekoppeltem Plasma) Technik für hochaufgelöste in-situ Messungen von Spurenelementen und Bleiisotopen entwickelt. rnrnZunächst wurden geeignete Materialien für die Kalibrierung der Technik untersucht; als Proben dienten die Silikatreferenzgläser BAM-S005-A und BAM-S005B der Bundesanstalt für Materialforschung und –prüfung (BAM). Die Homogenität dieser Referenzgläser wurde mit LA-ICP-MS und den anderen mikroanalytischen Methoden EPMA (Elektronenmikrosonde) und SIMS (Ionensonde) überprüft. Die Ergebnisse zeigten, dass alle Haupt- und die meisten Spurenelemente in beiden Gläsern selbst im Mikrometerbereich homogen verteilt sind. Ausnahmen sind einige Spurenelemente, wie Cs, Cl, Cr, Mo und Ni, die heterogen in den Gläsern verteilt sind. Die Hauptelementzusammensetzung von BAM-S005-A und BAM-S005-B wurde mit Hilfe der EPMA bestimmt, wobei die Ergebnisse die Referenzwerte des BAM-Zertifikats bestätigten. Mit Ausnahme von Sr, Ba, Ce und Pb, stimmten die LA-ICP-MS-Spurenelementwerte mit den zertifizierten Werten innerhalb der angegebenen Fehlergrenzen überein. Gründe für die Diskrepanz der vier oben erwähnten Elemente sind noch unklar, aber sind möglicherweise durch fehlerhafte Referenzwerte zu erklären. Zusätzlich wurden 22 Spurenelemente gemessen, deren Gehalte von BAM nicht zertifiziert wurden. Aufgrund dieser Untersuchungen konnte festgestellt werden, dass beide BAM-Gläser für mikroanalytische Anwendungen geeignet sind.rnrnUm neuartige paläoklimatische Proxies im Calcit von Ostrakoden aus tibetanischen Seesedimenten zu untersuchen, wurde die Spurenelementvariabilität in einzelnen Ostrakodenklappen durch eine neue LA-ICP-MS-Technik bestimmt. Klappen von Ostrakoden der drei Arten (Leucocytherella sinensis Huang, 1982, ?Leucocythere dorsotuberosa Huang, 1982 und ?L. dorsotuberosa f. postilirata sensu Pang, 1985) wurden aus zwei Sedimentkernen des Nam Co Sees auf dem Hochplateau von Tibet gewonnen. Zwei LA-ICP-MS-Varianten, Spot- bzw. Linienanalyse, wurden verwendet, um die Elementkonzentrationen der Spurenelemente Mg, Sr, Ba, U und die der Seltenen Erdelemente (SEE) in den Klappen einzelner Ostrakoden zu bestimmen. Die Ergebnisse zeigten, dass die Linienanalyse präzisere Daten als die Spotanalyse liefert und sie wurde daher vorgezogen. Signifikante Unterschiede in der Spurenelementzusammensetzung zwischen den verschiedenen Arten der Ostrakoden wurden nicht gefunden. Variationen der Elementverhältnisse Mg/Ca und Sr/Ca in den Klappen stimmen mit veröffentlichten Seenspiegelschwankungen während des Holozäns überein, was zeigt, dass Mg- und Sr-Messungen in den Ostrakoden zur Untersuchung paläohydrochemischer Prozesse in diesem Gebiet herangezogen werden kann. Die gute Korrelation, die in dieser Arbeit zwischen Ba/Ca und Sr/Ca gefunden wurde, ist ein Hinweis darauf, dass der Einbau von Ba und Sr in die Klappen durch den gleichen Mechanismus erfolgte. Eine mögliche Beziehung zwischen dem U/Ca-Verhältnis in den Ostrakoden und den Redoxbedingungen auf dem Boden des Sees in der Vergangenheit wird diskutiert. Relativ geringe und konstante La/Ca-Verhältnisse wurden festgestellt, deren Ursache möglicherweise entweder auf der SEE-Charakteristik des Seewassers, auf biologischen Prozessen in den Ostrakoden oder auf Kontamination von Fe-Mn und/oder organischen Substanzen beruhen. Weitere Untersuchungen an Proben aus diesem Gebiet, speziell Klappen von lebenden Ostrakoden, sind notwendig, um den Gehalt von Ba, U und den SEE in Ostrakoden als paläoklimatische Proxies von Umweltbedingungen zu verwenden.