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.

Quantum gravity effects in rotating black hole spacetimes

The aim of this work is to explore, within the framework of the presumably asymptotically safe Quantum Einstein Gravity, quantum corrections to black hole spacetimes, in particular in the case of rotating black holes. We have analysed this problem by exploiting the scale dependent Newton s constant implied by the renormalization group equation for the effective average action, and introducing an appropriate "cutoff identification" which relates the renormalization scale to the geometry of the spacetime manifold. We used these two ingredients in order to "renormalization group improve" the classical Kerr metric that describes the spacetime generated by a rotating black hole. We have focused our investigation on four basic subjects of black hole physics. The main results related to these topics can be summarized as follows. Concerning the critical surfaces, i.e. horizons and static limit surfaces, the improvement leads to a smooth deformation of the classical critical surfaces. Their number remains unchanged. In relation to the Penrose process for energy extraction from black holes, we have found that there exists a non-trivial correlation between regions of negative energy states in the phase space of rotating test particles and configurations of critical surfaces of the black hole. As for the vacuum energy-momentum tensor and the energy conditions we have shown that no model with "normal" matter, in the sense of matter fulfilling the usual energy conditions, can simulate the quantum fluctuations described by the improved Kerr spacetime that we have derived. Finally, in the context of black hole thermodynamics, we have performed calculations of the mass and angular momentum of the improved Kerr black hole, applying the standard Komar integrals. The results reflect the antiscreening character of the quantum fluctuations of the gravitational field. Furthermore we calculated approximations to the entropy and the temperature of the improved Kerr black hole to leading order in the angular momentum. More generally we have proven that the temperature can no longer be proportional to the surface gravity if an entropy-like state function is to exist.

The electron antineutrino angular correlation coefficient a in free neutron decay: Testing the standard model with the aSPECT-spectrometer

The beta-decay of free neutrons is a strongly over-determined process in the Standard Model (SM) of Particle Physics and is described by a multitude of observables. Some of those observables are sensitive to physics beyond the SM. For example, the correlation coefficients of the involved particles belong to them. The spectrometer aSPECT was designed to measure precisely the shape of the proton energy spectrum and to extract from it the electron anti-neutrino angular correlation coefficient "a". A first test period (2005/ 2006) showed the “proof-of-principles”. The limiting influence of uncontrollable background conditions in the spectrometer made it impossible to extract a reliable value for the coefficient "a" (publication: Baessler et al., 2008, Europhys. Journ. A, 38, p.17-26). A second measurement cycle (2007/ 2008) aimed to under-run the relative accuracy of previous experiments (Stratowa et al. (1978), Byrne et al. (2002)) da/a =5%. I performed the analysis of the data taken there which is the emphasis of this doctoral thesis. A central point are background studies. The systematic impact of background on a was reduced to da/a(syst.)=0.61 %. The statistical accuracy of the analyzed measurements is da/a(stat.)=1.4 %. Besides, saturation effects of the detector electronics were investigated which were initially observed. These turned out not to be correctable on a sufficient level. An applicable idea how to avoid the saturation effects will be discussed in the last chapter.