Constraint handling rules. Compositional semantics and program transformation

This thesis intends to investigate two aspects of Constraint Handling Rules (CHR). It proposes a compositional semantics and a technique for program transformation. CHR is a concurrent committed-choice constraint logic programming language consisting of guarded rules, which transform multi-sets of atomic formulas (constraints) into simpler ones until exhaustion [Frü06] and it belongs to the declarative languages family. It was initially designed for writing constraint solvers but it has recently also proven to be a general purpose language, being as it is Turing equivalent [SSD05a]. Compositionality is the first CHR aspect to be considered. A trace based compositional semantics for CHR was previously defined in [DGM05]. The reference operational semantics for such a compositional model was the original operational semantics for CHR which, due to the propagation rule, admits trivial non-termination. In this thesis we extend the work of [DGM05] by introducing a more refined trace based compositional semantics which also includes the history. The use of history is a well-known technique in CHR which permits us to trace the application of propagation rules and consequently it permits trivial non-termination avoidance [Abd97, DSGdlBH04]. Naturally, the reference operational semantics, of our new compositional one, uses history to avoid trivial non-termination too. Program transformation is the second CHR aspect to be considered, with particular regard to the unfolding technique. Said technique is an appealing approach which allows us to optimize a given program and in more detail to improve run-time efficiency or spaceconsumption. Essentially it consists of a sequence of syntactic program manipulations which preserve a kind of semantic equivalence called qualified answer [Frü98], between the original program and the transformed ones. The unfolding technique is one of the basic operations which is used by most program transformation systems. It consists in the replacement of a procedure-call by its definition. In CHR every conjunction of constraints can be considered as a procedure-call, every CHR rule can be considered as a procedure and the body of said rule represents the definition of the call. While there is a large body of literature on transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages. We define an unfolding rule, show its correctness and discuss some conditions in which it can be used to delete an unfolded rule while preserving the meaning of the original program. Finally, confluence and termination maintenance between the original and transformed programs are shown. This thesis is organized in the following manner. Chapter 1 gives some general notion about CHR. Section 1.1 outlines the history of programming languages with particular attention to CHR and related languages. Then, Section 1.2 introduces CHR using examples. Section 1.3 gives some preliminaries which will be used during the thesis. Subsequentely, Section 1.4 introduces the syntax and the operational and declarative semantics for the first CHR language proposed. Finally, the methodologies to solve the problem of trivial non-termination related to propagation rules are discussed in Section 1.5. Chapter 2 introduces a compositional semantics for CHR where the propagation rules are considered. In particular, Section 2.1 contains the definition of the semantics. Hence, Section 2.2 presents the compositionality results. Afterwards Section 2.3 expounds upon the correctness results. Chapter 3 presents a particular program transformation known as unfolding. This transformation needs a particular syntax called annotated which is introduced in Section 3.1 and its related modified operational semantics !0t is presented in Section 3.2. Subsequently, Section 3.3 defines the unfolding rule and prove its correctness. Then, in Section 3.4 the problems related to the replacement of a rule by its unfolded version are discussed and this in turn gives a correctness condition which holds for a specific class of rules. Section 3.5 proves that confluence and termination are preserved by the program modifications introduced. Finally, Chapter 4 concludes by discussing related works and directions for future work.

Kiwifruit bud release from dormancy: effect of exogenous cytokinins

A new formulate containing citokinins, that is commercialized as Cytokin, has been introduced as dormancy breaking agents. During a three-years study, Cytokin was applied at different concentrations and application times in two producing areas of the Emilia-Romagna region to verify its efficacy as a DBA. Cytokin application increased the bud break and showed a lateral flower thinning effect. Moreover, treated vines showed an earlier and more uniform flowering as compared to control ones. Results obtained on the productive performance revealed a constant positive effect in the fruit fresh weight at harvest. Moreover, Cytokin did not cause any phytotoxicity even at the highest concentrations. Starting from the field observation, which suggested the involvement of cytokinins in kiwifruit bud release from dormancy, 6-BA was applied in open field condition and molecular and histological analyses were carried out in kiwifruit buds collected starting from the endo dormant period up to complete bud break to compare the natural occurring situation to the one induced by exogenous cytokinin application. In details, molecular analyses were set up on to verify the expression of genes involved in the reactivation of cell cycle: cyclin D3, histone H4, cyclin-dependent kinase B, as well as of others which are known to be up regulated during bud release in other species, i.e.isopenteniltransferases (IPTs), which catalyze the first step in the CK biosynthesis, and sucrose synthase 1 and A, which are involved in the sugar supplied. Moreover, histological analyses of the cell division rate in kiwifruit bud apical meristems were performed. These analyses showed a reactivation of the cell divisions during bud release and changes in the expression level of the investigated genes.

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.

The role of the West African Monsoon in the tropical to mid-latitudes climate

The interaction between atmosphere–land–ocean–biosphere systems plays a prominent role on the atmospheric dynamics and on the convective rainfall distribution over the West Africa monsoon area during the boreal summer. In particular, the initialization of convective systems in the Sub – Sahelian region has been directly linked to soil moisture heterogeneities identified as the major triggering, development and propagation of convective systems. The present study aims at investigating African monsoon large scale convective dynamics and rainfall diurnal cycle through an exploration of the hypothesis behind the mechanisms of a monsoon phenomenon as an emergence of a collective dynamics of many propagating convective systems. Such hypothesis is based on the existence of an internal self – regulation mechanism among the various components. To achieve these results a multiple analysis was performed based on remote sensed rainfall dataset, and global and regional modelling data for a period of 5 seasons: 2004 - 2008. Satellite rainfall data and convective occurrence variability were studied for assessing typical spatio – temporal signatures and characteristics with an emphasis to the diurnal cycle footprint. A global model and regional model simulation datasets, specifically developed for this analysis and based on Regional Atmospheric Modelling System – RAMS, have been analysed. Results from numerical model datasets highlight the evidence of a synchronization between the destabilization of the convective boundary layer and rainfall occurrence due to the solar radiation forcing through the latent heat release. This supports the conclusion that the studied interacting systems are associated with a process of mutual adjustment of rhythms. Furthermore, this rainfall internal coherence was studied in relation to the West African Heat Low pressure system, which has a prominent role in the large scale summer variability over the Mediterranean area since it is acting as one of dynamic link between sub tropical and midlatitudes variability.

Radar based improvements and diagnosis of the convective capabilities of the cosmo-2 model

In the last few years the resolution of numerical weather prediction (nwp) became higher and higher with the progresses of technology and knowledge. As a consequence, a great number of initial data became fundamental for a correct initialization of the models. The potential of radar observations has long been recognized for improving the initial conditions of high-resolution nwp models, while operational application becomes more frequent. The fact that many nwp centres have recently taken into operations convection-permitting forecast models, many of which assimilate radar data, emphasizes the need for an approach to providing quality information which is needed in order to avoid that radar errors degrade the model's initial conditions and, therefore, its forecasts. Environmental risks can can be related with various causes: meteorological, seismical, hydrological/hydraulic. Flash floods have horizontal dimension of 1-20 Km and can be inserted in mesoscale gamma subscale, this scale can be modeled only with nwp model with the highest resolution as the COSMO-2 model. One of the problems of modeling extreme convective events is related with the atmospheric initial conditions, in fact the scale dimension for the assimilation of atmospheric condition in an high resolution model is about 10 Km, a value too high for a correct representation of convection initial conditions. Assimilation of radar data with his resolution of about of Km every 5 or 10 minutes can be a solution for this problem. In this contribution a pragmatic and empirical approach to deriving a radar data quality description is proposed to be used in radar data assimilation and more specifically for the latent heat nudging (lhn) scheme. Later the the nvective capabilities of the cosmo-2 model are investigated through some case studies. Finally, this work shows some preliminary experiments of coupling of a high resolution meteorological model with an Hydrological one.

Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Biomimetic Scaffolds for the Controlled Release of Bioactive Molecules for Tissue Engineering Applications

The temporospatial controlled delivery of growth factors is crucial to trigger the desired healing mechanisms in target tissues. The uncontrolled release of growth factors has been demonstrated to cause severe side effects in its surrounding tissues. Thus, the first working hypothesis was to tune and optimize a newly developed multiscale delivery platform based on a nanostructured silicon particle core (pSi) and a poly (dl-lactide-co-glycolide) acid (PLGA) outer shell. In a murine subcutaneous model, the platform was demonstrated to be fully tunable for the temporal and spatial control release of the payload. Secondly, a multiscale approach was followed in a multicompartment collagen scaffold, to selectively integrate different sets of PLGA-pSi loaded with different reporter proteins. The spatial confinement of the microspheres allowed the release of the reporter proteins in each of the layers of the scaffold. Finally, the staged and zero-order release kinetics enabled the temporal biochemical patterning of the scaffold. The last step of this PhD project was to test if by fully embedding PLGA microspheres in a highly structured and fibrous collagen-based scaffold (camouflaging), it was possible to prevent their early detection and clearance by macrophages. It was further studied whether such a camouflaging strategy was efficient in reducing the production of key inflammatory molecules, while preserving the release kinetics of the payload of the PLGA microspheres. Results demonstrated that the camouflaging allowed for a 10-fold decrease in the number of PLGA microspheres internalized by macrophages, suggesting that the 3D scaffold operated by cloaking the PLGA microspheres. When the production of key inflammatory cytokines induced by the scaffold was assessed, macrophages' response to the PLGA microspheres-integrated scaffolds resulted in a response similar to that observed in the control (not functionalized scaffold) and the release kinetic of a reporter protein was preserved.

Portfolio Approaches in Constraint Programming

Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance. In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core. We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.