Rigorous Error Bounds for Finite Dimensional Linear Programming Problems | Keil, Christian

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 being well understood and having 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.