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.

Metaheuristics for Search Problems in Genomics - New Algorithms and Applications

In this thesis we made the first steps towards the systematic application of a methodology for automatically building formal models of complex biological systems. Such a methodology could be useful also to design artificial systems possessing desirable properties such as robustness and evolvability. The approach we follow in this thesis is to manipulate formal models by means of adaptive search methods called metaheuristics. In the first part of the thesis we develop state-of-the-art hybrid metaheuristic algorithms to tackle two important problems in genomics, namely, the Haplotype Inference by parsimony and the Founder Sequence Reconstruction Problem. We compare our algorithms with other effective techniques in the literature, we show strength and limitations of our approaches to various problem formulations and, finally, we propose further enhancements that could possibly improve the performance of our algorithms and widen their applicability. In the second part, we concentrate on Boolean network (BN) models of gene regulatory networks (GRNs). We detail our automatic design methodology and apply it to four use cases which correspond to different design criteria and address some limitations of GRN modeling by BNs. Finally, we tackle the Density Classification Problem with the aim of showing the learning capabilities of BNs. Experimental evaluation of this methodology shows its efficacy in producing network that meet our design criteria. Our results, coherently to what has been found in other works, also suggest that networks manipulated by a search process exhibit a mixture of characteristics typical of different dynamical regimes.

Multicelled Behaviour in E. coli: Design and experimental characterization of an engineered library of hybrid promoters.

Synthetic biology has recently had a great development, many papers have been published and many applications have been presented, spanning from the production of biopharmacheuticals to the synthesis of bioenergetic substrates or industrial catalysts. But, despite these advances, most of the applications are quite simple and don’t fully exploit the potential of this discipline. This limitation in complexity has many causes, like the incomplete characterization of some components, or the intrinsic variability of the biological systems, but one of the most important reasons is the incapability of the cell to sustain the additional metabolic burden introduced by a complex circuit. The objective of the project, of which this work is part, is trying to solve this problem through the engineering of a multicellular behaviour in prokaryotic cells. This system will introduce a cooperative behaviour that will allow to implement complex functionalities, that can’t be obtained with a single cell. In particular the goal is to implement the Leader Election, this procedure has been firstly devised in the field of distributed computing, to identify the process that allow to identify a single process as organizer and coordinator of a series of tasks assigned to the whole population. The election of the Leader greatly simplifies the computation providing a centralized control. Further- more this system may even be useful to evolutionary studies that aims to explain how complex organisms evolved from unicellular systems. The work presented here describes, in particular, the design and the experimental characterization of a component of the circuit that solves the Leader Election problem. This module, composed of an hybrid promoter and a gene, is activated in the non-leader cells after receiving the signal that a leader is present in the colony. The most important element, in this case, is the hybrid promoter, it has been realized in different versions, applying the heuristic rules stated in [22], and their activity has been experimentally tested. The objective of the experimental characterization was to test the response of the genetic circuit to the introduction, in the cellular environment, of particular molecules, inducers, that can be considered inputs of the system. The desired behaviour is similar to the one of a logic AND gate in which the exit, represented by the luminous signal produced by a fluorescent protein, is one only in presence of both inducers. The robustness and the stability of this behaviour have been tested by changing the concentration of the input signals and building dose response curves. From these data it is possible to conclude that the analysed constructs have an AND-like behaviour over a wide range of inducers’ concentrations, even if it is possible to identify many differences in the expression profiles of the different constructs. This variability accounts for the fact that the input and the output signals are continuous, and so their binary representation isn’t able to capture the complexity of the behaviour. The module of the circuit that has been considered in this analysis has a fundamental role in the realization of the intercellular communication system that is necessary for the cooperative behaviour to take place. For this reason, the second phase of the characterization has been focused on the analysis of the signal transmission. In particular, the interaction between this element and the one that is responsible for emitting the chemical signal has been tested. The desired behaviour is still similar to a logic AND, since, even in this case, the exit signal is determined by the hybrid promoter activity. The experimental results have demonstrated that the systems behave correctly, even if there is still a substantial variability between them. The dose response curves highlighted that stricter constrains on the inducers concentrations need to be imposed in order to obtain a clear separation between the two levels of expression. In the conclusive chapter the DNA sequences of the hybrid promoters are analysed, trying to identify the regulatory elements that are most important for the determination of the gene expression. Given the available data it wasn’t possible to draw definitive conclusions. In the end, few considerations on promoter engineering and complex circuits realization are presented. This section aims to briefly recall some of the problems outlined in the introduction and provide a few possible solutions.

Inverse problems in classical and quantum physics

The subject of this thesis is in the area of Applied Mathematics known as Inverse Problems. Inverse problems are those where a set of measured data is analysed in order to get as much information as possible on a model which is assumed to represent a system in the real world. We study two inverse problems in the fields of classical and quantum physics: QCD condensates from tau-decay data and the inverse conductivity problem. Despite a concentrated effort by physicists extending over many years, an understanding of QCD from first principles continues to be elusive. Fortunately, data continues to appear which provide a rather direct probe of the inner workings of the strong interactions. We use a functional method which allows us to extract within rather general assumptions phenomenological parameters of QCD (the condensates) from a comparison of the time-like experimental data with asymptotic space-like results from theory. The price to be paid for the generality of assumptions is relatively large errors in the values of the extracted parameters. Although we do not claim that our method is superior to other approaches, we hope that our results lend additional confidence to the numerical results obtained with the help of methods based on QCD sum rules. EIT is a technology developed to image the electrical conductivity distribution of a conductive medium. The technique works by performing simultaneous measurements of direct or alternating electric currents and voltages on the boundary of an object. These are the data used by an image reconstruction algorithm to determine the electrical conductivity distribution within the object. In this thesis, two approaches of EIT image reconstruction are proposed. The first is based on reformulating the inverse problem in terms of integral equations. This method uses only a single set of measurements for the reconstruction. The second approach is an algorithm based on linearisation which uses more then one set of measurements. A promising result is that one can qualitatively reconstruct the conductivity inside the cross-section of a human chest. Even though the human volunteer is neither two-dimensional nor circular, such reconstructions can be useful in medical applications: monitoring for lung problems such as accumulating fluid or a collapsed lung and noninvasive monitoring of heart function and blood flow.

Study of Candidate Genes for production and carcass traits in Italian Heavy Pigs: identification of a new DNA Markers, Expression Studies and Association Analysis using Different Experimental Design

Heavy pig breeding in Italy is mainly oriented for the production of high quality processed products. Of particular importance is the dry cured ham production, which is strictly regulated and requires specific carcass characteristics correlated with green leg characteristics. Furthermore, as pigs are slaughtered at about 160 kg live weight, the Italian pig breeding sector faces severe problems of production efficiency that are related to all biological aspects linked to growth, feed conversion, fat deposition and so on. It is well known that production and carcass traits are in part genetically determined. Therefore, as a first step to understand genetic basis of traits that could have a direct or indirect impact on dry cured ham production, a candidate gene approach can be used to identify DNA markers associated with parameters of economic importance. In this thesis, we investigated three candidate genes for carcass and production traits (TRIB3, PCSK1, MUC4) in pig breeds used for dry cured ham production, using different experimental approaches in order to find molecular markers associated with these parameters.

Oxygen: problems and solutions in electrochemistry

Different aspects of the electrochemistry of oxygen are examined through four experimental examples: corrosion, passivation via organic thin films, oxygen reduction and water oxidation catalysis are outlined in order to outline the very different ways and circumstances in which oxygen plays a major role in electrochemistry.

Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Boundary condition identification of a bridge pier using experimental data and FEM modal updating

Over the past twenty years, new technologies have required an increasing use of mathematical models in order to understand better the structural behavior: finite element method is the one mostly used. However, the reliability of this method applied to different situations has to be tried each time. Since it is not possible to completely model the reality, different hypothesis must be done: these are the main problems of FE modeling. The following work deals with this problem and tries to figure out a way to identify some of the unknown main parameters of a structure. This main research focuses on a particular path of study and development, but the same concepts can be applied to other objects of research. The main purpose of this work is the identification of unknown boundary conditions of a bridge pier using the data acquired experimentally with field tests and a FEM modal updating process. This work doesn’t want to be new, neither innovative. A lot of work has been done during the past years on this main problem and many solutions have been shown and published. This thesis just want to rework some of the main aspects of the structural optimization process, using a real structure as fitting model.

Novel insights into mechanisms of food allergy and allergic airway inflammation using experimental mouse models

Over the last decades, considerable efforts have been undertaken in the development of animal models mimicking the pathogenesis of allergic diseases occurring in humans. The mouse has rapidly emerged as the animal model of choice, due to considerations of handling and costs and, importantly, due to the availability of a large and increasing arsenal of genetically modified mouse strains and molecular tools facilitating the analysis of complex disease models. Here, we review latest developments in allergy research that have arisen from in vivo experimentation in the mouse, with a focus on models of food allergy and allergic asthma, which constitute major health problems with increasing incidence in industrialized countries. We highlight recent novel findings and controversies in the field, most of which were obtained through the use of gene-deficient or germ-free mice, and discuss new potential therapeutic approaches that have emerged from animal studies and that aim at attenuating allergic reactions in human patients.

Romany Families in Romania: Intelligence and Personality of Children Cross-cultural and Specific Problems of Development

Psychogenetic research has emphasised the influence of social factors on a child's intellectual development. In her work, Ms. Dumitrascu examines two such factors; family size and order of birth. However, since these formal parameters tend to be unstable, other more informal factors should be taken into consideration. Of these, perhaps the most interesting is the "style" of parental education, which Ms. Dumitrascu regards as an expression of national traditions at the family level. This educational style is culture dependent. Only a comparative, cross-cultural study can reveal the real mechanism through which educational style influences the development of a child's intellect and personality. Ms. Dumitrascu conducted an experimental cross-cultural study aimed at examining the effects of the family environment on a child's intellectual development. Three distinct populations were involved in her investigation, each having quite a distinct status in their geographical area; Romanians, Romanies (Gypsies) from Romania, and Russians from the Republic of Moldova. She presented her research in the form of a series of articles written in English totalling 85 pages, and also on disc. A significant difference was revealed between the intelligence of a child living in a large family, and that of a child with no brothers or sisters. In the case of Romany children, the gap is remarkably large. Ms. Dumitrascu concludes that the simultaneous action of several negative factors (low socio-economic status, large family size, socio-cultural isolation of a population) may delay child development. Subjected to such a precarious environment, Romany children do not seek self-realisation, but rather struggle to survive the hardship. Most of them remain out of civilisation. Unfortunately, adult Romanies seldom express any concern regarding their children's successful social integration. The school as main socialisation tool has no value for most parents. Ms. Dumitrascu argues the need for a major effort aimed at helping Romany's social integration. She hopes this project will be of some help for psychologists, social workers, teachers, and all those who are interested in the integration into society of minority groups.

EXPERIMENTAL AND COMPUTATIONAL STUDIES OF ELECTROMAGNETIC CLOAKING AT MICROWAVES

An invisibility cloak is a device that can hide the target by enclosing it from the incident radiation. This intriguing device has attracted a lot of attention since it was first implemented at a microwave frequency in 2006. However, the problems of existing cloak designs prevent them from being widely applied in practice. In this dissertation, we try to remove or alleviate the three constraints for practical applications imposed by loosy cloaking media, high implementation complexity, and small size of hidden objects compared to the incident wavelength. To facilitate cloaking design and experimental characterization, several devices and relevant techniques for measuring the complex permittivity of dielectric materials at microwave frequencies are developed. In particular, a unique parallel plate waveguide chamber has been set up to automatically map the electromagnetic (EM) field distribution for wave propagation through the resonator arrays and cloaking structures. The total scattering cross section of the cloaking structures was derived based on the measured scattering field by using this apparatus. To overcome the adverse effects of lossy cloaking media, microwave cloaks composed of identical dielectric resonators made of low loss ceramic materials are designed and implemented. The effective permeability dispersion was provided by tailoring dielectric resonator filling fractions. The cloak performances had been verified by full-wave simulation of true multi-resonator structures and experimental measurements of the fabricated prototypes. With the aim to reduce the implementation complexity caused by metamaterials employment for cloaking, we proposed to design 2-D cylindrical cloaks and 3-D spherical cloaks by using multi-layer ordinary dielectric material (εr>1) coating. Genetic algorithm was employed to optimize the dielectric profiles of the cloaking shells to provide the minimum scattering cross sections of the cloaked targets. The designed cloaks can be easily scaled to various operating frequencies. The simulation results show that the multi-layer cylindrical cloak essentially outperforms the similarly sized metamaterials-based cloak designed by using the transformation optics-based reduced parameters. For the designed spherical cloak, the simulated scattering pattern shows that the total scattering cross section is greatly reduced. In addition, the scattering in specific directions could be significantly reduced. It is shown that the cloaking efficiency for larger targets could be improved by employing lossy materials in the shell. At last, we propose to hide a target inside a waveguide structure filled with only epsilon near zero materials, which are easy to implement in practice. The cloaking efficiency of this method, which was found to increase for large targets, has been confirmed both theoretically and by simulations.

EXPERIMENTAL INVESTIGATION OF CERTAIN INTERNAL CONDENSING AND BOILING FLOWS: THEIR SENSITIVITY TO PRESSURE FLUCTUATIONS AND HEAT TRANSFER ENHANCEMENTS

Space-based (satellite, scientific probe, space station, etc.) and millimeter – to – microscale (such as are used in high power electronics cooling, weapons cooling in aircraft, etc.) condensers and boilers are shear/pressure driven. They are of increasing interest to system engineers for thermal management because flow boilers and flow condensers offer both high fluid flow-rate-specific heat transfer capacity and very low thermal resistance between the fluid and the heat exchange surface, so large amounts of heat may be removed using reasonably-sized devices without the need for excessive temperature differences. However, flow stability issues and degradation of performance of shear/pressure driven condensers and boilers due to non-desirable flow morphology over large portions of their lengths have mostly prevented their use in these applications. This research is part of an ongoing investigation seeking to close the gap between science and engineering by analyzing two key innovations which could help address these problems. First, it is recommended that the condenser and boiler be operated in an innovative flow configuration which provides a non-participating core vapor stream to stabilize the annular flow regime throughout the device length, accomplished in an energy-efficient manner by means of ducted vapor re-circulation. This is demonstrated experimentally. Second, suitable pulsations applied to the vapor entering the condenser or boiler (from the re-circulating vapor stream) greatly reduce the thermal resistance of the already effective annular flow regime. For experiments reported here, application of pulsations increased time-averaged heat-flux up to 900 % at a location within the flow condenser and up to 200 % at a location within the flow boiler, measured at the heat-exchange surface. Traditional fully condensing flows, reported here for comparison purposes, show similar heat-flux enhancements due to imposed pulsations over a range of frequencies. Shear/pressure driven condensing and boiling flow experiments are carried out in horizontal mm-scale channels with heat exchange through the bottom surface. The sides and top of the flow channel are insulated. The fluid is FC-72 from 3M Corporation.

Third party assessments in trust problems with conflict of interest: An experiment on the effects of promisesm

Is it possible to elicit reliable assessment from an assessor having a conflict of interest (e.g. a professor that writes a recommendation letter for a formal PhD student)? We propose an experimental test and show that compared to a not-incentivized assessment, a promise to give a truthful assessment reduces misreporting to the same extent as an incentivized assessment (i.e. when the assessor gains higher payoff if the assessment is correct).

Validation of a paradigm to measure instrumental aggression (iap) on a sample of male adolescents with adjustment problems

Aggressive behavior can be classified in hostile and instrumental aggressions (anderson & bushman, 2002). this classification is mostly synonymously used with reactive and proactive aggression, whereas the differences between hostile and instrumental aggression lie on three dimensions, the primary goal, amount of anger and planning and calculation(bushman & anderson, 2001). although there are rating instruments and experimental paradigms to measure hostile aggression, there is no instrument to measure instrumental aggression. the following study will present an account to measure instrumental aggression with an experimental laboratory paradigm. the instrument was firstly tested on two samples of normal young adolescents (n1 = 100; amage. = 19.14; n2 = 60; amage. = 21.46). the first study revealed a strong correlation with a laboratory aggression paradigm measuring hostile aggression, but no correlations with self-reported aggression in the buss and perry questionnaire. these results were replicated in a second study, revealing an additional correlation with aggressive but not adaptive assertiveness. secondly the instrument was part of the evaluation of the reasoning and rehabilitation program r&r2 (ross, hilborn & lidell, 1984) in an institution for male adolescents with adjustment problems in switzerland. the r&r2 is a cognitive behavioral group therapy to reduce antisocial and promote prosocial cognitions and behavior. the treatment group (n= 16; rangeage = 15-17) is compared to a no treatment control group (n=24; rangeage = 17-19) preand post- treatment. further aggressive behavior was surveyed and experimentally measured. hostile rumination, aggressive and adaptive assertiveness, emotional and social competence were included in the measurement to estimate construct validity.

Sensitive Questions in Online Surveys: An Experimental Comparison of the RRT and the Crosswise Model

Self-administered online surveys provide a higher level of privacy protection to respondents than surveys administered by an interviewer. Yet, studies show that asking sensitive questions is problematic also in self-administered mode. Because respondents might not be willing to reveal the truth and provide answers that are subject to social desirability bias, the validity of prevalence estimates of sensitive behaviors gained via online surveys can be challenged. A wellknown method to combat these problems is the Randomized Response Technique (RRT). However, convincing evidence that the RRT provides more valid estimates than direct questioning in online mode is still lacking. Moreover, an alternative approach called the Crosswise Model (CM) has recently been suggested to overcome some of the deficiencies of the RRT. We therefore conducted an experimental study in which different implementations of the RRT and the CM have been tested and compared to direct questioning. Our study is a large-scale online survey on sensitive behaviors by students such as cheating in exams and paper plagiarism. The results of the study reveal poor per-formance of the RRT, while the CM yielded significantly higher estimates of sensitive behaviors than direct questioning. We conclude that the CM is a promising approach for asking sensitive questions in self-administered surveys.