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.

Sphärische Bürsten in polymeren Schmelzen

Colloidal nanoparticles are additives to improve or modify several properties of thermoplastic or elastic polymers. Usually colloid-polymer mixtures show phase separation due to the depletion effect. The strategy to overcome this depletion demixing was to prepare surface-modified colloidal particles, which can be blended with linear polymer chains homogeneous. A successful synthesis strategy for the preparation of hairy nanospheres was developed by grafting polystyrene macromonomer chains onto polyorganosiloxane microgels. The number of hairs per particle with a core radius of approximately 10nm exceeded 150 hairs in all cases. The molecular weight of the hairs variied between 4000-18000g/mol.The compatibility of these hairy spheres mixed with linear polymer chains was investigated by AFM, TEM and SAXS. Homogeneous mixtures were found if the molecular weight of the polymer hairs on the particle surface is at least as large as the molecular weight of the matrix chains. If the chains are much shorter than the hairs, the colloidal hair corona is strongly swollen by the matrix polymer, leading to a long-range soft interparticle repulsion ('wet brush'). If hairs and chains are comparable in length, the corona shows much less volume swelling, leading to a short-range repulsive potential similar to hard sphere systems ('dry brush'). Polymerketten und Kolloidpartikel entmischen aufgrund von Depletion-Wechselwirkungen. Diese entropisch bedingte Entmischung konnte durch das Ankoppeln von Polymerhaaren verschiedenen Molekulargewichts auf die Kugeloberflächen der Kolloide bis zu hohen Konzentrationen vermieden werden. Zur Darstellung sphärischer Bürsten und haariger Tracerpartikel wurde eine neue Synthesestrategie ausgearbeitet und erfolgreich umgesetzt.Das Kompatibilitätsverhalten dieser sphärischen Bürsten in der Schmelze von Polymerketten als Matrix wurde mittels Elektronenmikroskopie und Kleinwinkelröntgenstreuung untersucht. Die Mischungen setzten sich aus sphärischen Bürsten und Matrixketten mit unterschiedlichen Molekulargewichten zusammen.Es zeigte sich, daß die Mischbarkeit entschieden durch das Verhältnis von Haarlänge zu Länge der Matrixketten beeinflußt wird.Aus den Untersuchungen des Relaxationsverhaltens mittels Rheologie und SAXS ergibt sich, daß das Konzept der 'dry brush'- und 'wet brush'-Systeme auf diese Mischungen übertragbar ist. Die Volumenquellung der Haarcorona durch die Matrixketten ist, wie die Experimente gezeigt haben, bereits im Fall von Polymeren mit relativ niedrigen Molekulargewichten zu beobachten. Sie ist umso stärker ausgeprägt, je größer das Längenverhältnis zwischen Polymerhaaren und Matrixketten ist. Die Quellung bedeutet eine Vergrößerung des effektiven Radius der Partikel und entspricht somit einer Erhöhung des effektiven Volumenbruchs. Dies führt zur Ausbildung einer höheren Ordnung und zu einem Einfrieren der Relaxation dieser strukturellen Ordnung führt.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

Mixed finite-element methods for elliptic convection-dominated problems arising in semiconductor physics

In this work we develop and analyze an adaptive numerical scheme for simulating a class of macroscopic semiconductor models. At first the numerical modelling of semiconductors is reviewed in order to classify the Energy-Transport models for semiconductors that are later simulated in 2D. In this class of models the flow of charged particles, that are negatively charged electrons and so-called holes, which are quasi-particles of positive charge, as well as their energy distributions are described by a coupled system of nonlinear partial differential equations. A considerable difficulty in simulating these convection-dominated equations is posed by the nonlinear coupling as well as due to the fact that the local phenomena such as "hot electron effects" are only partially assessable through the given data. The primary variables that are used in the simulations are the particle density and the particle energy density. The user of these simulations is mostly interested in the current flow through parts of the domain boundary - the contacts. The numerical method considered here utilizes mixed finite-elements as trial functions for the discrete solution. The continuous discretization of the normal fluxes is the most important property of this discretization from the users perspective. It will be proven that under certain assumptions on the triangulation the particle density remains positive in the iterative solution algorithm. Connected to this result an a priori error estimate for the discrete solution of linear convection-diffusion equations is derived. The local charge transport phenomena will be resolved by an adaptive algorithm, which is based on a posteriori error estimators. At that stage a comparison of different estimations is performed. Additionally a method to effectively estimate the error in local quantities derived from the solution, so-called "functional outputs", is developed by transferring the dual weighted residual method to mixed finite elements. For a model problem we present how this method can deliver promising results even when standard error estimator fail completely to reduce the error in an iterative mesh refinement process.