Rigorose Fehlerschranken für endlich-dimensionale lineare Programme

Die Dissertation behandelt die Theorie, Implementierung und Anwendung rigoroser Fehlerschranken für endlich-dimensionale lineare Programme. Trotz der gut verstandenen Theorie und zahlreicher Anwendungen liefern kommerzielle Softwarepakete häufig falsche Resultate für diese Probleme. Im Gegensatz dazu liefern Verifikationsmethoden nachweislich korrekte Ergebnisse. Die Arbeit präsentiert Theoreme, die solche Schranken liefern, begleitet von einer Konvergenzanalyse und Verallgemeinerungen. Das Softwarepaket Lurupa wird beschrieben, welches die rigorosen Schranken als eigenständiges Paket, als Bibliothek und von MATLAB aus zur Verfügung stellt. Ausführliche numerische Experimente und ein Vergleich mit anderen Softwarepaketen werden präsentiert. Diese demonstrieren die Notwendigkeit die spezielle Struktur eines Problems auszunutzen, um schnelle und zuverlässige Ergebnisse zu erhalten.This dissertation treats the theory, implementation, and application of rigorous error bounds in the context of finite dimensional linear programming problems. Despite the theory of linear programming that is well understood and its numerous applications, commercial solvers frequently produce erroneous results for these problems. In contrast, verification methods yield solutions proved to be correct. The thesis presents theorems that yield rigorous error bounds, a convergence analysis, and generalizations. The software package Lurupa is described, which offers the rigorous error bounds as a standalone software, a library, and from MATLAB. Extensive numerical experiments and a comparison with other software packages are presented. They demonstrate that exploiting the special structure of a problem is necessary when aiming for fast and reliable results