Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Study of the effect of minor compounds on the oxidative stability and physical properties of bulk oil, oil-in-water emulsion, and food emulsions

Minor components are of particular interest due to their antioxidant and biological properties. Various classes of lipophilic minor components (plant sterols (PS) and α-tocopherol) were selected as they are widely used in the food industry. A Fast GC-MS method for PS analysis in functional dairy products was set up. The analytical performance and significant reduction of the analysis time and consumables, demonstrated that Fast GC-MS could be suitable for the PS analysis in functional dairy products. Due to their chemical structure, PS can undergo oxidation, which could be greatly impacted by matrix nature/composition and thermal treatments. The oxidative stability of PS during microwave heating was evaluated. Two different model systems (PS alone and in combination) were heated up to 30 min at 1000 W. PS degraded faster when they were alone than in presence of TAG. The extent of PS degradation depends on both heating time and the surrounding medium, which can impact the quality and safety of the food product destined to microwave heating/cooking. Many minor lipid components are included in emulsion systems and can affect the rate of lipid oxidation. The oxidative stability of oil-in-water (O/W) emulsions containing PS esters, ω-3 FA and phenolic compounds, were evaluated after a 14-day storage at room temperature. Due to their surface active character, PS could be particularly prone to oxidation when they are incorporated in emulsions, as they are more exposed to water-soluble prooxidants. Finally, some minor lipophilic components may increase oxidative stability of food systems due to their antioxidant activity. á-tocopherol partitioning and antioxidant activity was determined in the presence of excess SDS in stripped soybean O/W emulsions. Results showed that surfactant micelles could play a key role as an antioxidant carrier, by potentially increasing the accessibility of hydrophobic antioxidant to the interface.

A new snowfall detection algorithm for high latitude regions based on a combination of active and passive sensors

Precipitation retrieval over high latitudes, particularly snowfall retrieval over ice and snow, using satellite-based passive microwave spectrometers, is currently an unsolved problem. The challenge results from the large variability of microwave emissivity spectra for snow and ice surfaces, which can mimic, to some degree, the spectral characteristics of snowfall. This work focuses on the investigation of a new snowfall detection algorithm specific for high latitude regions, based on a combination of active and passive sensors able to discriminate between snowing and non snowing areas. The space-borne Cloud Profiling Radar (on CloudSat), the Advanced Microwave Sensor units A and B (on NOAA-16) and the infrared spectrometer MODIS (on AQUA) have been co-located for 365 days, from October 1st 2006 to September 30th, 2007. CloudSat products have been used as truth to calibrate and validate all the proposed algorithms. The methodological approach followed can be summarised into two different steps. In a first step, an empirical search for a threshold, aimed at discriminating the case of no snow, was performed, following Kongoli et al. [2003]. This single-channel approach has not produced appropriate results, a more statistically sound approach was attempted. Two different techniques, which allow to compute the probability above and below a Brightness Temperature (BT) threshold, have been used on the available data. The first technique is based upon a Logistic Distribution to represent the probability of Snow given the predictors. The second technique, defined Bayesian Multivariate Binary Predictor (BMBP), is a fully Bayesian technique not requiring any hypothesis on the shape of the probabilistic model (such as for instance the Logistic), which only requires the estimation of the BT thresholds. The results obtained show that both methods proposed are able to discriminate snowing and non snowing condition over the Polar regions with a probability of correct detection larger than 0.5, highlighting the importance of a multispectral approach.

Development of glass-ceramics from combination of industrial wastes together with boron mining waste

The utilization of borate mineral wastes with glass-ceramic technology was first time studied and primarily not investigated combinations of wastes were incorporated into the research. These wastes consist of; soda lime silica glass, meat bone and meal ash and fly ash. In order to investigate possible and relevant application areas in ceramics, kaolin clay, an essential raw material for ceramic industry was also employed in some studied compositions. As a result, three different glass-ceramic articles obtained by using powder sintering method via individual sintering processes. Light weight micro porous glass-ceramic from borate mining waste, meat bone and meal ash and kaolin clay was developed. In some compositions in related study, soda lime silica glass waste was used as an additive providing lightweight structure with a density below 0.45 g/cm3 and a crushing strength of 1.8±0.1 MPa. In another study within the research, compositions respecting the B2O3–P2O5–SiO2 glass-ceramic ternary system were prepared from; borate wastes, meat bone and meal ash and soda lime silica glass waste and sintered up to 950ºC. Low porous, highly crystallized glass-ceramic structures with density ranging between 1.8 ± 0,7 to 2.0 ± 0,3 g/cm3 and tensile strength ranging between 8,0 ± 2 to 15,0 ± 0,5 MPa were achieved. Lastly, diopside - wollastonite (SiO2-Al2O3-CaO )glass-ceramics from borate wastes, fly ash and soda lime silica glass waste were successfully obtained with controlled rapid sintering between 950 and 1050ºC. The wollastonite and diopside crystal sizes were improved by adopting varied combinations of formulations and heating rates. The properties of the obtained materials show; the articles with a uniform pore structure could be useful for thermal and acoustic insulations and can be embedded in lightweight concrete where low porous glass-ceramics can be employed as building blocks or additive in cement and ceramic industries.

Ab initio quantum mechanical investigation of structural and chemical-physical properties of selected minerals for minero-petrological, structural ceramic and biomaterial applications

The purpose of this thesis is the atomic-scale simulation of the crystal-chemical and physical (phonon, energetic) properties of some strategically important minerals for structural ceramics, biomedical and petrological applications. These properties affect the thermodynamic stability and rule the mineral-environment interface phenomena, with important economical, (bio)technological, petrological and environmental implications. The minerals of interest belong to the family of phyllosilicates (talc, pyrophyllite and muscovite) and apatite (OHAp), chosen for their importance in industrial and biomedical applications (structural ceramics) and petrophysics. In this thesis work we have applicated quantum mechanics methods, formulas and knowledge to the resolution of mineralogical problems ("Quantum Mineralogy”). The chosen theoretical approach is the Density Functional Theory (DFT), along with periodic boundary conditions to limit the portion of the mineral in analysis to the crystallographic cell and the hybrid functional B3LYP. The crystalline orbitals were simulated by linear combination of Gaussian functions (GTO). The dispersive forces, which are important for the structural determination of phyllosilicates and not properly con-sidered in pure DFT method, have been included by means of a semi-empirical correction. The phonon and the mechanical properties were also calculated. The equation of state, both in athermal conditions and in a wide temperature range, has been obtained by means of variations in the volume of the cell and quasi-harmonic approximation. Some thermo-chemical properties of the minerals (isochoric and isobaric thermal capacity) were calculated, because of their considerable applicative importance. For the first time three-dimensional charts related to these properties at different pressures and temperatures were provided. The hydroxylapatite has been studied from the standpoint of structural and phonon properties for its biotechnological role. In fact, biological apatite represents the inorganic phase of vertebrate hard tissues. Numerous carbonated (hydroxyl)apatite structures were modelled by QM to cover the broadest spectrum of possible biological structural variations to fulfil bioceramics applications.

The reconstruction of skeletal movement: the soft tissue artefact issue

In 3D human movement analysis performed using stereophotogrammetric systems and skin markers, bone pose can only be estimated in an indirect fashion. During a movement, soft tissue deformations make the markers move with respect to the underlying bone generating soft tissue artefact (STA). STA has devastating effects on bone pose estimation and its compensation remains an open question. The aim of this PhD thesis was to contribute to the solution of this crucial issue. Modelling STA using measurable trial-specific variables is a fundamental prerequisite for its removal from marker trajectories. Two STA model architectures are proposed. Initially, a thigh marker-level artefact model is presented. STA was modelled as a linear combination of joint angles involved in the movement. This model was calibrated using ex-vivo and in-vivo STA invasive measures. The considerable number of model parameters led to defining STA approximations. Three definitions were proposed to represent STA as a series of modes: individual marker displacements, marker-cluster geometrical transformations (MCGT), and skin envelope shape variations. Modes were selected using two criteria: one based on modal energy and another on the selection of modes chosen a priori. The MCGT allows to select either rigid or non-rigid STA components. It was also empirically demonstrated that only the rigid component affects joint kinematics, regardless of the non-rigid amplitude. Therefore, a model of thigh and shank STA rigid component at cluster-level was then defined. An acceptable trade-off between STA compensation effectiveness and number of parameters can be obtained, improving joint kinematics accuracy. The obtained results lead to two main potential applications: the proposed models can generate realistic STAs for simulation purposes to compare different skeletal kinematics estimators; and, more importantly, focusing only on the STA rigid component, the model attains a satisfactory STA reconstruction with less parameters, facilitating its incorporation in an pose estimator.