Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Dynamics of the halo gas in disc galaxies

This Thesis studies the dynamics of hot and cold gas outside the plane in galaxies like the Milky-Way (extra-planar gas) and focuses on the interaction between disc and halo material. Stationary models for the cold phase of the extra-planar gas are presented. They show that the kinematics of this phase must be influenced by the interaction with an ambient medium that we identify as the hot cosmological corona that surrounds disc galaxies. To study this interaction a novel hydrodynamical code has been implemented and a series of hydrodynamical simulations has been run to investigate the mass and momentum exchange between the cold extra-planar gas clouds and the hot corona. These simulations show that the coronal gas can condense efficiently in the turbulent wakes that form behind the cold clouds and it can be accreted by the disc to sustain star formation. They also predict that the corona cannot be a static structure but it must rotate and lag by approximately 80-120 km/s with respect to the disc. Implications of the results of this Thesis for the evolution of star-forming galaxies and for the large-scale dynamics of galactic coronae are also briefly discussed.

Marine biodiversity survey in the Northern Red Sea: a large-scale monitoring carried out in collaboration with volunteer divers

Concerns over global change and its effect on coral reef survivorship have highlighted the need for long-term datasets and proxy records, to interpret environmental trends and inform policymakers. Citizen science programs have showed to be a valid method for collecting data, reducing financial and time costs for institutions. This study is based on the elaboration of data collected by recreational divers and its main purpose is to evaluate changes in the state of coral reef biodiversity in the Red Sea over a long term period and validate the volunteer-based monitoring method. Volunteers recreational divers completed a questionnaire after each dive, recording the presence of 72 animal taxa and negative reef conditions. Comparisons were made between records from volunteers and independent records from a marine biologist who performed the same dive at the same time. A total of 500 volunteers were tested in 78 validation trials. Relative values of accuracy, reliability and similarity seem to be comparable to those performed by volunteer divers on precise transects in other projects, or in community-based terrestrial monitoring. 9301 recreational divers participated in the monitoring program, completing 23,059 survey questionnaires in a 5-year period. The volunteer-sightings-based index showed significant differences between the geographical areas. The area of Hurghada is distinguished by a medium-low biodiversity index, heavily damaged by a not controlled anthropic exploitation. Coral reefs along the Ras Mohammed National Park at Sharm el Sheikh, conversely showed high biodiversity index. The detected pattern seems to be correlated with the conservation measures adopted. In our experience and that of other research institutes, citizen science can integrate conventional methods and significantly reduce costs and time. Involving recreational divers we were able to build a large data set, covering a wide geographic area. The main limitation remains the difficulty of obtaining an homogeneous spatial sampling distribution.

Early Warning For Large Earthquakes: Observations, Models and Real-Time Data Analysis

This thesis is a collection of works focused on the topic of Earthquake Early Warning, with a special attention to large magnitude events. The topic is addressed from different points of view and the structure of the thesis reflects the variety of the aspects which have been analyzed. The first part is dedicated to the giant, 2011 Tohoku-Oki earthquake. The main features of the rupture process are first discussed. The earthquake is then used as a case study to test the feasibility Early Warning methodologies for very large events. Limitations of the standard approaches for large events arise in this chapter. The difficulties are related to the real-time magnitude estimate from the first few seconds of recorded signal. An evolutionary strategy for the real-time magnitude estimate is proposed and applied to the single Tohoku-Oki earthquake. In the second part of the thesis a larger number of earthquakes is analyzed, including small, moderate and large events. Starting from the measurement of two Early Warning parameters, the behavior of small and large earthquakes in the initial portion of recorded signals is investigated. The aim is to understand whether small and large earthquakes can be distinguished from the initial stage of their rupture process. A physical model and a plausible interpretation to justify the observations are proposed. The third part of the thesis is focused on practical, real-time approaches for the rapid identification of the potentially damaged zone during a seismic event. Two different approaches for the rapid prediction of the damage area are proposed and tested. The first one is a threshold-based method which uses traditional seismic data. Then an innovative approach using continuous, GPS data is explored. Both strategies improve the prediction of large scale effects of strong earthquakes.

Stress & structure of thin polymer brush films

Polymer brushes have unique properties with a large variety of possible applications ranging from responsive coatings and drug delivery to lubrication and sensing. For further development a detailed understanding of the properties is needed. Established characterization methods, however, only supply information of the surface. Experimental data about the inner “bulk” structure of polymer brushes is still missing.rnScattering methods under grazing incidence supply structural information of surfaces as well as structures beneath it. Nanomechanical cantilevers supply stress data, which is giving information about the forces acting inside the polymer brush film. In this thesis these two techniques are further developed and used to deepen the understanding of polymer brushes. rnThe experimental work is divided into four chapters. Chapter 2 deals with the preparation of polymer brushes on top of nanomechanical cantilever sensors as well as large area sample by using a “grafting-to” technique. The further development of nanomechanical cantilever readout is subject of chapter 3. In order to simplify cantilever sensing, a method is investigated which allows one to perform multiple bending experiments on top of a single cantilever. To do so, a way to correlate different curvatures is introduced as well as a way to conveniently locate differently coated segments. In chapter 4 the change in structure upon solvent treatment of mixed polymer brushes is investigated by using scattering methods and nanomechanical cantilevers amongst others. This allows one to explain the domain memory effect, which is typically found in such systems. Chapter 5 describes the implementation of a phase shifting interferometer - used for readout of nanomechanical cantilevers - into the µ-focused scattering beamline BW4, allowing simultaneous measurements of stress and structure information. The last experimental chapter 6 deals with the roughness correlation in polymer brushes and its dependence on the chain tethered density.rnIn summary, the thesis deals with utilization of new experimental techniques for the investigation of polymer brushes and further development of the techniques themselves.rn

Exploring host-pathogen interactions through protein microarray. Large-scale protein microarray analysis revealed novel human receptors for the staphylococcal immune evasion protein FLIPr and for the neisserial adhesin NadA

Adhesion, immune evasion and invasion are key determinants during bacterial pathogenesis. Pathogenic bacteria possess a wide variety of surface exposed and secreted proteins which allow them to adhere to tissues, escape the immune system and spread throughout the human body. Therefore, extensive contacts between the human and the bacterial extracellular proteomes take place at the host-pathogen interface at the protein level. Recent researches emphasized the importance of a global and deeper understanding of the molecular mechanisms which underlie bacterial immune evasion and pathogenesis. Through the use of a large-scale, unbiased, protein microarray-based approach and of wide libraries of human and bacterial purified proteins, novel host-pathogen interactions were identified. This approach was first applied to Staphylococcus aureus, cause of a wide variety of diseases ranging from skin infections to endocarditis and sepsis. The screening led to the identification of several novel interactions between the human and the S. aureus extracellular proteomes. The interaction between the S. aureus immune evasion protein FLIPr (formyl-peptide receptor like-1 inhibitory protein) and the human complement component C1q, key players of the offense-defense fighting, was characterized using label-free techniques and functional assays. The same approach was also applied to Neisseria meningitidis, major cause of bacterial meningitis and fulminant sepsis worldwide. The screening led to the identification of several potential human receptors for the neisserial adhesin A (NadA), an important adhesion protein and key determinant of meningococcal interactions with the human host at various stages. The interaction between NadA and human LOX-1 (low-density oxidized lipoprotein receptor) was confirmed using label-free technologies and cell binding experiments in vitro. Taken together, these two examples provided concrete insights into S. aureus and N. meningitidis pathogenesis, and identified protein microarray coupled with appropriate validation methodologies as a powerful large scale tool for host-pathogen interactions studies.

Bispectrum of cosmological models with massive neutrinos

Uno dei più importanti campi di ricerca che coinvolge gli astrofisici è la comprensione della Struttura a Grande Scala dell'universo. I principi della Formazione delle Strutture sono ormai ben saldi, e costituiscono la base del cosiddetto "Modello Cosmologico Standard". Fino agli inizi degli anni 2000, la teoria che spiegava con successo le proprietà statistiche dell'universo era la cosiddetta "Teoria Perturbativa Standard". Attraverso simulazioni numeriche e osservazioni di qualità migliore, si è evidenziato il limite di quest'ultima teoria nel descrivere il comportamento dello spettro di potenza su scale oltre il regime lineare. Ciò spinse i teorici a trovare un nuovo approccio perturbativo, in grado di estendere la validità dei risultati analitici. In questa Tesi si discutono le teorie "Renormalized Perturbation Theory"e"Multipoint Propagator". Queste nuove teorie perturbative sono la base teorica del codice BisTeCca, un codice numerico originale che permette il calcolo dello spettro di potenza a 2 loop e del bispettro a 1 loop in ordine perturbativo. Come esempio applicativo, abbiamo utilizzato BisTeCca per l'analisi dei bispettri in modelli di universo oltre la cosmologia standard LambdaCDM, introducendo una componente di neutrini massicci. Si mostrano infine gli effetti su spettro di potenza e bispettro, ottenuti col nostro codice BisTeCca, e si confrontano modelli di universo con diverse masse di neutrini.

Mechanical properties and structure of gel systems

Understanding the origins of the mechanical properties and its correlation withrnthe microstructure of gel systems is of great scientific and industrial interest. Inrngeneral, colloidal gels can be classified into chemical and physical gels, accordingrnto the life time of the network bonds. The characteristic di↵erences in gelationrndynamics can be observed with rheological measurements.rnAs a model system, a mixture of sodium silicate and low concentration sulfuric acidrnwas used. Nano-sized silica particles grow and aggregate to a system-spanning gelrnnetwork. The influence of the finite solubility of silica at high pH on the gelationrnwas studied with classical and piezo rheometer. The storage modulus of therngel grew logarithmically with time with two distinct growth laws. A relaxationrnat low frequency was observed in the frequency dependent measurements. I attributernthese two behaviors as a sign of structural rearrangements due to the finiternsolubility of silica at high pH. The reaction equilibrium between formation andrndissolution of bonds leads to a finite life time of the bonds and behavior similar tornphysical gel. The frequency dependence was more pronounced for lower water concentrations,rnhigher temperatures and shorter reaction times. With two relaxationrnmodels, I deduced characteristic relaxation times from the experimental data. Besidesrnrheology, the evolution of silica gels at high pH on di↵erent length scales wasrnstudied by NMR and dynamic light scattering. The results revealed that the primaryrnparticles existed already in sodium silicate and aggregated after the mixingrnof reactants due to a chemical reaction. Throughout the aggregation process thernsystem was in its chemical reaction equilibrium. Applying large oscillatory shearrnstrain to the gel allowed for modifying the gel modulus. The e↵ect of shear andrnshear history on the rheological properties of the gel were investigated. The storagernmodulus of the final gel increased with increasing strain. This behavior can be explained with (i) shear-induced aggregate compaction and (ii) combination ofrnbreakage and new formation of bonds.rnIn comparison with the physical gel-like behavior of the silica gel at high pH, typicalrnchemical gel features were exhibited by other gels formed from various chemicalrnreactions. Influences of the chemical structure modification on the gelation wererninvestigated with the piezo-rheometer. The external stimuli can be applied to tunernthe mechanical properties of the gel systems.

Mesozoic fold structure of the Otago and Alpine Schist Belt and its implications on the tectonic evolution of South Island, New Zealand

Erneute Untersuchungen der mesozoischen Faltenstruktur des Otago Schiefergürtels, Südinsel, Neuseeland, zeigen, dass diese aus zwei aufeinander folgenden, ähnlichen, asymmetrischen, offenen bis mäßig engen Großfaltengenerationen im km- Größenbereich besteht anstatt aus den vorher angenommenen Decken- oder Halbfalten. Hauptproblem der Großfaltenstruktur sind Zonen von durchgreifender Boudinage, die in der Nähe der Großfaltenscharniere entstanden sind. Vorherige Bearbeiter deuteten diese Zonen als 'starke Verformungszonen' oder Überschiebungszonen. Diese Arbeit zeigt, dass in diesen Zonen nur durch die asymmetrische Faltung die unteren liegenden Schenkel der Großfalten boudiniert und somit häufig die ansonsten typischen Faltenstrukturen des liegenden Schenkels einer symmetrischen Faltung überprägt wurden. Ein weiteres Problem dieser mesozoischen Großfaltenstruktur ist die Überprägung einer Faltengeneration auf eine frühere. Weil die Verkürzungsrichtung der überprägenden Faltengeneration nicht subparallel zur älteren Faltenachse ist, sondern einen Winkel von rund 30 Grad einschließt, ist ein Wechsel von orthogonalen zu koaxialen Interferenzmustern der Kleinfalten beobachtbar. Folglich ist die Orientierung der Scheitellinie einer überprägenden und überprägten Kleinfalte nicht unbedingt subparallel zur Orientierung der Faltenachse der Großfalte trotz zylindrischer Faltung. Im letzten Teil dieser Arbeit wird die Überprägung der mesozoischen Großfaltenstruktur durch das känozoisch entstandene, transpressionale Alpine Störungssystem, das einen zweiseitigen Falten- und Überschiebungsgürtel im Otago und im Nordwesten anschließenden Alpinen Schiefergürtel bildet, beschrieben.

Factor Structure of the Neck Disability Index

BACKGROUND CONTEXT: The Neck Disability Index frequently is used to measure outcomes of the neck. The statistical rigor of the Neck Disability Index has been assessed with conflicting outcomes. To date, Confirmatory Factor Analysis of the Neck Disability Index has not been reported for a suitably large population study. Because the Neck Disability Index is not a condition-specific measure of neck function, initial Confirmatory Factor Analysis should consider problematic neck patients as a homogenous group. PURPOSE: We sought to analyze the factor structure of the Neck Disability Index through Confirmatory Factor Analysis in a symptomatic, homogeneous, neck population, with respect to pooled populations and gender subgroups. STUDY DESIGN: This was a secondary analysis of pooled data. PATIENT SAMPLE: A total of 1,278 symptomatic neck patients (67.5% female, median age 41 years), 803 nonspecific and 475 with whiplash-associated disorder. OUTCOME MEASURES: The Neck Disability Index was used to measure outcomes. METHODS: We analyzed pooled baseline data from six independent studies of patients with neck problems who completed Neck Disability Index questionnaires at baseline. The Confirmatory Factor Analysis was considered in three scenarios: the full sample and separate sexes. Models were compared empirically for best fit. RESULTS: Two-factor models have good psychometric properties across both the pooled and sex subgroups. However, according to these analyses, the one-factor solution is preferable from both a statistical perspective and parsimony. The two-factor model was close to significant for the male subgroup (p<.07) where questions separated into constructs of mental function (pain, reading headaches and concentration) and physical function (personal care, lifting, work, driving, sleep, and recreation). CONCLUSIONS: The Neck Disability Index demonstrated a one-factor structure when analyzed by Confirmatory Factor Analysis in a pooled, homogenous sample of neck problem patients. However, a two-factor model did approach significance for male subjects where questions separated into constructs of mental and physical function. Further investigations in different conditions, subgroup and sex-specific populations are warranted.

Phenology for tropoclimatological surveys and large-scale mapping

Biotic and abiotic phenological observations can be collected from continental to local spatial scale. Plant phenological observations may only be recorded wherever there is vegetation. Fog, snow and ice are available as phenological para-meters wherever they appear. The singularity of phenological observations is the possibility of spatial intensification to a microclimatic scale where the equipment of meteorological measurements is too expensive for intensive campaigning. The omnipresence of region-specific phenological parameters allows monitoring for a spatially much more detailed assessment of climate change than with weather data. We demonstrate this concept with phenological observations with the use of a special network in the Canton of Berne, Switzerland, with up to 600 observations sites (more than 1 to 10 km² of the inhabited area). Classic cartography, gridding, the integration into a Geographic Information System GIS and large-scale analysis are the steps to a detailed knowledge of topoclimatic conditions of a mountainous area. Examples of urban phenology provide other types of spatially detailed applications. Large potential in phenological mapping in future analyses lies in combining traditionally observed species-specific phenology with remotely sensed and modelled phenology that provide strong spatial information. This is a long history from cartographic intuition to algorithm-based representations of phenology.