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.

Laboratory study on the optical properties of absorbing atmospheric aerosols and field applications

The interaction between aerosols and sun light plays an important role in the radiative balance of Earth’s atmosphere. This interaction is obtained by measuring the removal (extinction), redistribution (scattering), and transformation into heat (absorption) of light by the aerosols; i.e. their optical properties. Knowledge of these properties is crucial for our understanding of the atmospheric system. rn Light absorption by aerosols is a major contributor to the direct and indirect effects on our climate system, and an accurate and sensitive measurement method is crucial to further our understanding. A homebuilt photoacoustic sensor (PAS), measuring at a 532nm wavelength, was fully characterized and its functionality validated for measurements of absorbing aerosols. The optical absorption cross-sections of absorbing polystyrene latex spheres, to be used as a standard for aerosol absorption measurements, were measured and compared to literature values. Additionally, a calibration method using absorbing aerosol of known complex refractive index was presented.rn A new approach to retrieve the effective broadband refractive indices (mbroad,eff) of aerosol particles by a white light aerosol spectrometer (WELAS) optical particle counter (OPC) was achieved. Using a tandem differential mobility analyzer (DMA)-OPC system, the nbroad,eff are obtained for both laboratory and field applications. This method was tested in the laboratory using substances with a wide range of optical properties and it was used in ambient measurements to retrieve the nbroad,eff of biomass burning aerosols in a nationwide burning event in Israel. The retrieved effective broadband refractive indices for laboratory generated scattering aerosols were: ammonium sulfate (AS), glutaric acid (GA), and sodium chloride, all within 4% of literature values. For absorbing substances, nigrosine and various mixtures of nigrosine with AS and GA were measured, as well as a lightly absorbing substance, Suwannee river fulvic acid (SRFA). For the ambient measurements, the calibration curves generated from this method were to follow the optical evolution of biomass burning (BB) aerosols. A decrease in the overall aerosol absorption and scattering for aged aerosols during the day after the fires compared to the smoldering phase of the fires was found. rn The connection between light extinction of aerosols, their chemical composition and hygroscopicity for particles with different degrees of absorption was studied. The extinction cross-section (σext) at 532nm for different mobility diameters was measured at 80% and 90% relative humidity (RH), and at an RH<10%. The ratio of the humidified aerosols to the dry ones, fRHext(%RH,Dry), is presented. For purely scattering aerosols, fRHext(%RH,Dry) is inversely proportional with size; this dependence was suppressed for lightly absorbing ones. In addition, the validity of the mixing rules for water soluble absorbing aerosols is explored. The difference between the derived and calculated real parts of the complex RIs were less than 5.3% for all substances, wavelengths, and RHs. The obtained imaginary parts for the retrieved and calculated RIs were in good agreement with each other, and well within the measurement errors of retrieval from pulsed CRD spectroscopy measurements. Finally, a core-shell structure model is also used to explore the differences between the models, for substances with low growth factors, under these hydration conditions. It was found that at 80% RH and for size parameters less than 2.5, there is less than a 5 % difference between the extinction efficiencies calculated with both models. This difference is within measurement errors; hence, there is no significant difference between the models in this case. However, for greater size parameters the difference can be up to 10%. For 90% RH the differences below a size parameter of 2.5 were up to 7%.rn Finally, the fully characterized PAS together with a cavity ring down spectrometer (CRD), were used to study the optical properties of soot and secondary organic aerosol (SOA) during the SOOT-11 project in the AIDA chamber in Karlsruhe, Germany. The fresh fractal-like soot particles were allowed to coagulate for 28 hours before stepwise coating them with SOA. The single scattering albedo for fresh fractal-like soot was measured to be 0.2 (±0.03), and after allowing the soot to coagulate for 28 hours and coating it with SOA, it increased to 0.71(±0.01). An absorption enhancement of the coated soot of up to 1.71 (±0.03) times from the non-coated coagulated soot was directly measured with the PAS. Monodisperse measurements of SOA and soot coated with SOA were performed to derive the complex refractive index (m) of both aerosols. A complex refractive index of m = 1.471(±0.008) + i0.0(±0.002) for the SOA-αO3 was retrieved. For the compact coagulated soot a preliminary complex refractive index of m = 2.04(+0.21/-0.14) + i0.34(+0.18/-0.06) with 10nm(+4/-6) coating thickness was retrieved.rn These detail properties can be use by modelers to decrease uncertainties in assessing climatic impacts of the different species and to improve weather forecasting.rn

A new class of bragg stacks and its principle application

This work is focused on the development of high quality nanoporous 1D photonic crystals –so called Bragg stacks – made by spin-coating of approximately 25 nm large SiO2 and TiO2 nanoparticles bearing interparticle voids large enough to infiltrate reactive species. Therefore, the first part of this work describes the synthesis of well-dispersed TiO2 nanoparticles in this size range (the corresponding SiO2 nanoparticles are commercially available). In the second part, a protocol was developed to prepare nanoporous Bragg stacks of up to 12 bilayers with high quality and precision. Tailor-made Bragg stacks were prepared for different applications such as (i) a surface emitting feedback laser with a FWHM of only 6 nm and (ii) an electrochromic device with absorption reversibly switchable by an external electrical bias independently of the Bragg reflection. In the last chapter, the approach to 1D photonic crystals is transferred to 1D phononic crystals. Contrast in the modulus is achieved by spin-coating SiO2 and PMMA as high and low moduli material. This system showed a band gap of fg = 12.6 GHz with a width of Dfg/fg = 4.5 GHz.

Chemical exfoliation of graphene and its application in organic electronics and energy storage devices

Graphene, the thinnest two-dimensional material possible, is considered as a realistic candidate for the numerous applications in electronic, energy storage and conversion devices due to its unique properties, such as high optical transmittance, high conductivity, excellent chemical and thermal stability. However, the electronic and chemical properties of graphene are highly dependent on their preparation methods. Therefore, the development of novel chemical exfoliation process which aims at high yield synthesis of high quality graphene while maintaining good solution processability is of great concern. This thesis focuses on the solution production of high-quality graphene by wet-chemical exfoliation methods and addresses the applications of the chemically exfoliated graphene in organic electronics and energy storage devices.rnPlatinum is the most commonly used catalysts for fuel cells but they suffered from sluggish electron transfer kinetics. On the other hand, heteroatom doped graphene is known to enhance not only electrical conductivity but also long term operation stability. In this regard, a simple synthetic method is developed for the nitrogen doped graphene (NG) preparation. Moreover, iron (Fe) can be incorporated into the synthetic process. As-prepared NG with and without Fe shows excellent catalytic activity and stability compared to that of Pt based catalysts.rnHigh electrical conductivity is one of the most important requirements for the application of graphene in electronic devices. Therefore, for the fabrication of electrically conductive graphene films, a novel methane plasma assisted reduction of GO is developed. The high electrical conductivity of plasma reduced GO films revealed an excellent electrochemical performance in terms of high power and energy densities when used as an electrode in the micro-supercapacitors.rnAlthough, GO can be prepared in bulk scale, large amount of defect density and low electrical conductivity are major drawbacks. To overcome the intrinsic limitation of poor quality of GO and/or reduced GO, a novel protocol is extablished for mass production of high-quality graphene by means of electrochemical exfoliation of graphite. The prepared graphene shows high electrical conductivity, low defect density and good solution processability. Furthermore, when used as electrodes in organic field-effect transistors and/or in supercapacitors, the electrochemically exfoliated graphene shows excellent device performances. The low cost and environment friendly production of such high-quality graphene is of great importance for future generation electronics and energy storage devices. rn