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.

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.

Thin nanostructured crystalline TiO 2 films and their applications in solar cells

Research on thin nanostructured crystalline TiO2 films has attracted considerable interests because of their intriguing physical properties and potential applications in photovoltaics. Nanostructured TiO2 film plays an important role in the TiO2 based dye-sensitized solar cells because they act as a substrate for the adsorption of dye molecules and a matrix for the transportation of electrons as well. Thus they can influence the solar cell performance significantly. Consequently, the control of the morphology including the shape, size and size distribution of the TiO2 nanostructures is critical to tune and optimize the performance of the solar cells. To control the TiO2 morphology, a strategy using amphiphilic block copolymer as templating agent coupled with sol-gel chemistry has been applied. Especially, a good-poor solvent pair induced phase separation process has been developed to guide the microphase separation behavior of the block copolymers. The amphiphilic block copolymers used include polystyrene-block-poly (ethylene oxide) (PS-b-PEO), poly (methyl methacrylate)-block-poly (ethylene oxide) (PMMA-b-PEO), and poly (ethylene oxide)-block-polystyrene-block-poly (ethylene oxide) (PEO-b-PS-b-PEO). The block copolymer undergoes a good-poor-solvent pair induced phase separation in a mixed solution of 1, 4-dioxane or N, N’-dimethyl formamide (DMF), concentrated hydrochloric acid (HCl) and Titanium tetraisopropoxide (TTIP). Specifically, in the system of PS-b-PEO, a morphology phase diagram of the inorganic-copolymer composite films was mapped by adjusting the weight fractions among 1, 4-dioxane, HCl, and TTIP in solution. The amorphous TiO2 within the titania-block copolymer composite films was crystallized by calcination at temperatures above 400C, where the organic block copolymer was simultaneously burned away. This strategy is further extended to other amphiphilic block copolymers of PMMA-b-PEO and PEO-b-PS-b-PEO, where the morphology of TiO2 films can also be controlled. The local and long range structures of the titania films were investigated by the combination of imaging techniques (AFM, SEM) and x-ray scattering techniques (x-ray reflectivity and grazing incidence small-angle x-ray scattering). Based on the knowledge of the morphology control, the crystalline TiO2 nanostructured films with different morphologies were introduced into solid state dye-sensitized solar cells. It has been found that all of the morphologies help to improve the performance of the solar cells. Especially, clustered nanoparticles, worm-like structures, foam-like structures, large collapsed nanovesicles show more pronounced performance improvement than other morphologies such as nanowires, flakes, and nanogranulars.

New biosensor applications of surface plasmon and hydrogel optical waveguide spectroscopy

Rapid and sensitive detection of chemical and biological analytes becomes increasingly important in areas such as medical diagnostics, food control and environmental monitoring. Optical biosensors based on surface plasmon resonance (SPR) and optical waveguide spectroscopy have been extensively pushed forward in these fields. In this study, we combine SPR, surface plasmon-enhanced fluorescence spectroscopy (SPFS) and optical waveguide spectroscopy with hydrogel thin film for highly sensitive detection of molecular analytes.rnrnA novel biosensor based on SPFS which was advanced through the excitation of long range surface plasmons (LRSPs) is reported in this study. LRSPs are special surface plasmon waves propagating along thin metal films with orders of magnitude higher electromagnetic field intensity and lower damping than conventional SPs. Therefore, their excitation on the sensor surface provides further increased fluorescence signal. An inhibition immunoassay based on LRSP-enhanced fluorescence spectroscopy (LRSP-FS) was developed for the detection of aflatoxin M1 (AFM1) in milk. The biosensor allowed for the detection of AFM1 in milk at concentrations as low as 0.6 pg mL-1, which is about two orders of magnitude lower than the maximum AFM1 residue level in milk stipulated by the European Commission legislation.rnrnIn addition, LRSPs probe the medium adjacent to the metallic surface with more extended evanescent field than regular SPs. Therefore, three-dimensional binding matrices with up to micrometer thickness have been proposed for the immobilization of biomolecular recognition elements with large surface density that allows to exploit the whole evanescent field of LRSP. A photocrosslinkable carboxymethyl dextran (PCDM) hydrogel thin film is used as a binding matrix, and it is applied for the detection of free prostate specific antigen (f-PSA) based on the LRSP-FS and sandwich immunoassay. We show that this approach allows for the detection of f-PSA at low femto-molar range, which is approximately four orders of magnitude lower than that for direct detection of f-PSA based on the monitoring of binding-induced refractive index changes.rnrnHowever, a three dimensional hydrogel binding matrix with micrometer thickness can also serve as an optical waveguide. Based on the measurement of binding-induced refractive index changes, a hydrogel optical waveguide spectroscopy (HOWS) is reported for a label-free biosensor. This biosensor is implemented by using a SPR optical setup in which a carboxylated poly(N-isoproprylacrylamide) (PNIPAAm) hydrogel film is attached on a metallic surface and modified by protein catcher molecules. Compared to regular SPR biosensor with thiol self-assembled monolayer (SAM), HOWS provides an order of magnitude improved resolution in the refractive index measurements and enlarged binding capacity owing to its low damping and large swelling ratio, respectively. A model immunoassay experiment revealed that HOWS allowed detection of IgG molecules with a 10 pM limit of detection (LOD) that was five-fold lower than that achieved for SPR with thiol SAM. For the high capacity hydrogel matrix, the affinity binding was mass transport limited.rnrnThe mass transport of target molecules to the sensor surface can play as critical a role as the chemical reaction itself. In order to overcome the diffusion-limited mass transfer, magnetic iron oxide nanoparticles were employed. The magnetic nanoparticles (MNPs) can serve both as labels providing enhancement of the refractive index changes, and “vehicles” for rapidly delivering the analytes from sample solution to an SPR sensor surface with a gradient magnetic field. A model sandwich assay for the detection of β human chorionic gonadotropin (βhCG) has been utilized on a gold sensor surface with metallic diffraction grating structure supporting the excitation of SPs. Various detection formats including a) direct detection, b) sandwich assay, c) MNPs immunoassay without and d) with applied magnetic field were compared. The results show that the highly-sensitive MNPs immunoassay improves the LOD on the detection of βhCG by a factor of 5 orders of magnitude with respect to the direct detection.rn

Characterisation of human co-culture systems for applications in bone tissue engineering

For the successful integration of bone tissue engineering constructs into patients, an adequate supply with oxygen and nutrients is critical. Therefore, prevascularisation of bone tissue engineering constructs is desirable for bone formation, remodelling and regeneration. Co-culture systems, consisting of human endothelial cells and primary osteoblasts (pOB) as well as osteosarcoma cell lines, represent a promising method for studying the mechanisms involved in the vascularisation of constructs in bone tissue en- gineering and could provide new insights into the molecular and cellular mechanisms that control essential processes during angiogenesis. The present study demonstrated the im- portant components of co-culture systems with a focus on bone tissue replacement and the angiogenic effects of pOB and osteosarcoma cell lines on human endothelial cells. Furthermore, the studies emphasised an overall approach for analysis of signal molecules that are involved in the angiogenic activation of human endothelial cells by the regulation of VEGF-related pathways at the transcriptional and translational levels. The osteosarcoma cell lines Cal-72, MG-63 and SaOS-2, as well as pOB from several donors, differed in their angiogenesis-inducing potential in 2-D and 3-D co-culture systems. SaOS-2 cells appeared to have a high osteogenic differentiation level with no detectable angiogenesis-inducing potential in co-culture with human endothelial cells. The angiogenic potential of the osteoblast-like cells is mainly correlated with the upregulation of essential angiogenic growth factors, such as VEGF, bFGF and HGF and the downregulation of the angiogenesis inhibitor, endostatin. However, other factors involved in angiogenic regulation were found to differ between SaOS-2 cells, compared to Cal-72 and MG-63. The present study focuses on VEGF pathway-effecting genes as key players in the regulation of angiogenesis. The levels of VEGF and VEGF-effecting genes, such as TGF-α and TIMP-2 are down-regulated in SaOS-2 cells. In contrast, direct regulators of VEGF, such as IL6, IL8 and TNF are strongly upregulated, which indicates disruptions in growth factor regulating pathways in SaOS-2 cells. Potential pathways, which could be involved include MEK, PI3K, MAPK, STAT3, AKT or ERK. Additional treatment of co-cultures with single growth factors did not accelerate or improve the angiogenesis-inducing potential of SaOS-2 cells. Knowledge of the detailed molecular mechanisms involved in angiogenesis control will hopefully allow improved approaches to be developed for prevascularisation of bone tissue engineering constructs.