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.

What Happened to Participation? Urban Development and Authoritarian Upgrading in Cairo's Informal Neighbourhoods

Participation appeared in development discourses for the first time in the 1970s, as a generic call for the involvement of the poor in development initiatives. Over the last three decades, the initial perspectives on participation intended as a project method for poverty reduction have evolved into a coherent and articulated theoretical elaboration, in which participation figures among the paraphernalia of good governance promotion: participation has acquired the status of “new orthodoxy”. Nevertheless, the experience of the implementation of participatory approaches in development projects seemed to be in the majority of cases rather disappointing, since the transformative potential of ‘participation in development’ depends on a series of factors in which every project can actually differ from others: the ultimate aim of the approach promoted, its forms and contents and, last but not least, the socio-political context in which the participatory initiative is embedded. In Egypt, the signature of a project agreement between the Arab Republic of Egypt and the Federal Republic of Germany, in 1998, inaugurated a Participatory Urban Management Programme (PUMP) to be implemented in Greater Cairo by the German Technical Cooperation (Deutsche Gesellschaft für Technische Zusammenarbeit, GTZ) and the Ministry of Planning (now Ministry of Local Development) and the Governorates of Giza and Cairo as the main counterparts. Now, ten years after the beginning of the PUMP/PDP and close to its end (December 2010), it is possible to draw some conclusions about the scope, the significance and the effects of the participatory approach adopted by GTZ and appropriated by the Egyptian counterparts in dealing with the issue of informal areas and, more generally, of urban development. Our analysis follows three sets of questions: the first set regards the way ‘participation’ has been interpreted and concretised by PUMP and PDP. The second is about the emancipating potential of the ‘participatory approach’ and its ability to ‘empower’ the ‘marginalised’. The third focuses on one hand on the efficacy of GTZ strategy to lead to an improvement of the delivery service in informal areas (especially in terms of planning and policies), and on the other hand on the potential of GTZ development intervention to trigger an incremental process of ‘democratisation’ from below.

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.

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.

The Road to Poverty Reduction: Corporate Governance and Female Participation in MFIs

1.Microfinance Industry – Context of Analysis. This paper is an introduction to the microfinance industry. It serves as a context of analysis, for the empirical settings and basis for building the theoretical argument for the thesis. 2.Women in Microfinance Institutions: The Road to Poverty Reduction and Gender Equality? One of the unique aspects of microfinance institutions is their focus on outreach, i.e. their ability to reach the poor. This paper explores whether the presence of women in microfinance institutions is associated with improved outreach. Building on prior research that shows that women tend to improve financial performance and social responsibility, we examine an original dataset of 226 microfinance institutions. The empirical results suggest that the presence of a female CEO, female managers and female loan officers is directly related to improved outreach, while the presence of women board members is not. 3. Women in Microfinance Institutions: Is There a Trade-Off Between Outreach and Sustainability? Abstract This paper’s contribution to the understanding of microfinance is two-fold. First, while it has been shown that female CEOs in MFIs increase financial performance, it will be argued that female managers, female loan officers and female board members will do the same. Secondly, having previously shown that having a female presence in management in MFIs improves social performance the outreach, it will be argued that having females in the MFIs’ management will not lead to a trade-off between outreach and sustainability. These findings are based on an original data set of 226 MFIs. Statistical analysis demonstrates that a weak relationship between female managers and female loan officers vis-à-vis financial performance, but female board members do not. The trade-off between outreach and sustainability can be avoided with the appointment of females to the MFIs’ management positions, but the same cannot be concluded for female board members.

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.