Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Gleichmäßig dünne Basen zweiter Ordnung

Eine Menge B nicht negativer ganzer Zahlen heißt Basis h-ter Ordnung, wenn jede nicht negative ganze Zahl Summe von höchstens h Elementen von B ist. Eine der großen Fragen der additiven Zahlentheorie ist die nach der effektivsten Basis h-ter Ordnung für ein gegebenes h>=2. Im Fokus des Interesses steht dabei der immer noch offene Fall h=2. Bezeichnet B(x) die Anzahl der Elemente b aus B mit 0= af(x), wobei f die Wurzelfunktion bezeichne. Andererseits gibt es Basen B zweiter Ordnung mit B(x) <= cf(x). Daher kann man den Limes superior S(B), den Limes inferior s(B) sowie im Falle der Existenz den Limes d(B) des Quotienten B(x) / f(x) als Dichtefunktionen von Basen zweiter Ordnung betrachten. J. W. S. Cassels konstruierte 1957 eine Basis C zweiter Ordnung mit d(C)=5,196…. G. Hofmeister gab 2001 eine Basis H zweiter Ordnung mit asymptotischer Wurzeldichte d(H)=4,638… an. In der vorliegenden Arbeit wird eine Basis S zweiter Ordnung mit asymptotischer Wurzeldichte d(S)=3,464… konstruiert. Darüber hinaus wird für die von J. W. S. Cassels, für die von G. Hofmeister und für die in dieser Arbeit verwendete Klasse von Basen zweiter Ordnung gezeigt, dass die asymptotische Wurzeldichte innerhalb der jeweiligen Klasse nicht mehr zu verbessern ist. Bisher war die Frage nach möglichen Verbesserungen innerhalb der jeweiligen Konstruktionsprinzipien offen geblieben.

Hydrogels for DNA isolation from blood

This dissertation describes the synthesis of surface attached hydrogel biomaterials, characterization of their properties, evaluation of structuring concepts and the investigation of these materials in the isolation of DNA from human whole blood. Photosensitive hydrogel precursor materials on the basis of hydroxyethylmethacrylate (HEMA) were synthesized by free radical polymerization. In order to obtain surface bound hydrogel films, the precursors were deposited on a suitable substrate and subsequently irradatiated with UV - light to accomplish the formation of crosslinks in the film and create surface attachment. The composition of the polymerization precursor materials was determined by comprehensive NMR and GPC studies, revealing the copolymerizationrnbehaviour of the used monomers - HEMA derivatives and the photocrosslinkerrnMABP - and their respective distribution in the hydrogel precursors. The degree of crosslinking of the hydrogels was characterized with UV/vis spectroscopy. Stress-strain measurements were conducted in order to investigate the mechanical properties of the biomaterials. Moreover, the swelling process and biomolecule adsorption properties of the hydrogels were investigated with SPR/OW spectroscopy. For this, the deposition and binding of the hydrogels on gold or SiO2 surfaces was facilitated with photocrosslinkable adhesion promotors. The produced hydrogels were mechanically rigid and stablernunder the conditions of PCR and blood lysis. Furthermore, strategies towards the increase of hydrogel surface structure and porosity with porosigens, 2D laser interference lithography and photocleavable blockcopolymers were investigated. At last, a combinatorial strategy was used for the determination of the usefulness of hydrogels for the isolation from DNA from blood. A series of functionalized hydrogel precursors were synthesized, transferred to the surface inside a PCR tube and subsequently screened in regard to DNA adsorption properties with Taqman quantitative PCR. This approach yielded a promising candidate for a functional PCR tube coating that would allow the entire DNA isolation procedure being carried out in a single reaction container.rnThereforce, the practical application of such macromolecular architectures can be envisioned to improve industrial DNA diagnostic processes.