Specialization and optimization of constraint programs with dynamic scheduling

In this report we discuss some of the issues involved in the specialization and optimization of constraint logic programs with dynamic scheduling. Dynamic scheduling, as any other form of concurrency, increases the expressive power of constraint logic programs, but also introduces run-time overhead. The objective of the specialization and optimization is to reduce as much as possible such overhead automatically, while preserving the semantics of the original programs. This is done by program transformation based on global analysis. We present implementation techniques for this purpose and report on experimental results obtained from an implementation of the techniques in the context of the CIAO compiler.

Automatic compile-time parallelization of CLP programs by analysis and transformation to a concurrent constraint language.

The concept of independence has been recently generalized to the constraint logic programming (CLP) paradigm. Also, several abstract domains specifically designed for CLP languages, and whose information can be used to detect the generalized independence conditions, have been recently defined. As a result we are now in a position where automatic parallelization of CLP programs is feasible. In this paper we study the task of automatically parallelizing CLP programs based on such analyses, by transforming them to explicitly concurrent programs in our parallel CC platform (CIAO) as well as to AKL. We describe the analysis and transformation process, and study its efficiency, accuracy, and effectiveness in program parallelization. The information gathered by the analyzers is evaluated not only in terms of its accuracy, i.e. its ability to determine the actual dependencies among the program variables, but also of its effectiveness, measured in terms of code reduction in the resulting parallelized programs. Given that only a few abstract domains have been already defined for CLP, and that none of them were specifically designed for dependency detection, the aim of the evaluation is not only to asses the effectiveness of the available domains, but also to study what additional information it would be desirable to infer, and what domains would be appropriate for further improving the parallelization process.

Independence and search space preservation in dynamically scheduled constraint logic languages

This paper performs a further generalization of the notion of independence in constraint logic programs to the context of constraint logic programs with dynamic scheduling. The complexity of this new environment made necessary to first formally define the relationship between independence and search space preservation in the context of CLP languages. In particular, we show that search space preservation is, in the context of CLP languages, not only a sufficient but also a necessary condition for ensuring that both the intended solutions and the number of transitions performed do not change. These results are then extended to dynamically scheduled languages and used as the basis for the extension of the concepts of independence. We also propose several a priori sufficient conditions for independence and also give correctness and efficiency results for parallel execution of constraint logic programs based on the proposed notions of independence.

A constraint-based approach to quality assurance in service choreographies.

Knowledge about the quality characteristics (QoS) of service com- positions is crucial for determining their usability and economic value. Ser- vice quality is usually regulated using Service Level Agreements (SLA). While end-to-end SLAs are well suited for request-reply interactions, more complex, decentralized, multiparticipant compositions (service choreographies) typ- ically involve multiple message exchanges between stateful parties and the corresponding SLAs thus encompass several cooperating parties with interde- pendent QoS. The usual approaches to determining QoS ranges structurally (which are by construction easily composable) are not applicable in this sce- nario. Additionally, the intervening SLAs may depend on the exchanged data. We present an approach to data-aware QoS assurance in choreographies through the automatic derivation of composable QoS models from partici- pant descriptions. Such models are based on a message typing system with size constraints and are derived using abstract interpretation. The models ob- tained have multiple uses including run-time prediction, adaptive participant selection, or design-time compliance checking. We also present an experimen- tal evaluation and discuss the benefits of the proposed approach.

Independence, Global analysis, and parallelism, in dinamically scheduled constraint logic programming.

El punto de vista de muchas otras aplicaciones que modifican las reglas de computación. En segundo lugar, y una vez generalizado el concepto de independencia, es necesario realizar un estudio exhaustivo de la efectividad de las herramientas de análisis en la tarea de la paralelizacion automática. Los resultados obtenidos de dicha evaluación permiten asegurar de forma empírica que la utilización de analizadores globales en la tarea de la paralelizacion automática es vital para la consecución de una paralelizarían efectiva. Por último, a la luz de los buenos resultados obtenidos sobre la efectividad de los analizadores de flujo globales basados en la interpretación abstracta, se presenta la generalización de las herramientas de análisis al contexto de los lenguajes lógicos restricciones y planificación dinámica.

Constraint qualifications in linear vector semi-infinite optimization

Linear vector semi-infinite optimization deals with the simultaneous minimization of finitely many linear scalar functions subject to infinitely many linear constraints. This paper provides characterizations of the weakly efficient, efficient, properly efficient and strongly efficient points in terms of cones involving the data and Karush–Kuhn–Tucker conditions. The latter characterizations rely on different local and global constraint qualifications. The global constraint qualifications are illustrated on a collection of selected applications.

Robust Solutions of MultiObjective Linear Semi-Infinite Programs under Constraint Data Uncertainty

The multiobjective optimization model studied in this paper deals with simultaneous minimization of finitely many linear functions subject to an arbitrary number of uncertain linear constraints. We first provide a radius of robust feasibility guaranteeing the feasibility of the robust counterpart under affine data parametrization. We then establish dual characterizations of robust solutions of our model that are immunized against data uncertainty by way of characterizing corresponding solutions of robust counterpart of the model. Consequently, we present robust duality theorems relating the value of the robust model with the corresponding value of its dual problem.

Three-dimensional planar model estimation using multi-constraint knowledge based on k-means and RANSAC

Plane model extraction from three-dimensional point clouds is a necessary step in many different applications such as planar object reconstruction, indoor mapping and indoor localization. Different RANdom SAmple Consensus (RANSAC)-based methods have been proposed for this purpose in recent years. In this study, we propose a novel method-based on RANSAC called Multiplane Model Estimation, which can estimate multiple plane models simultaneously from a noisy point cloud using the knowledge extracted from a scene (or an object) in order to reconstruct it accurately. This method comprises two steps: first, it clusters the data into planar faces that preserve some constraints defined by knowledge related to the object (e.g., the angles between faces); and second, the models of the planes are estimated based on these data using a novel multi-constraint RANSAC. We performed experiments in the clustering and RANSAC stages, which showed that the proposed method performed better than state-of-the-art methods.

Constraint qualifications in convex vector semi-infinite optimization

Convex vector (or multi-objective) semi-infinite optimization deals with the simultaneous minimization of finitely many convex scalar functions subject to infinitely many convex constraints. This paper provides characterizations of the weakly efficient, efficient and properly efficient points in terms of cones involving the data and Karush–Kuhn–Tucker conditions. The latter characterizations rely on different local and global constraint qualifications. The results in this paper generalize those obtained by the same authors on linear vector semi-infinite optimization problems.

Bertrand Competition with an Asymmetric No-discrimination Constraint. Bruges European Economic Research (BEER) 23/June 2012

Regulators and competition authorities often prevent firms with significant market power or dominant firms from practicing price discrimination. The goal of such an asymmetric no- discrimination constraint is to encourage entry and serve consumers’ interests. This constraint prohibits the firm with significant market power to practice both behaviour-based price discrimination within the competitive segment and third-degree price discrimination across the monopolistic and competitive segments. We find that this constraint hinders entry and reduces welfare when the monopolistic segment is small.

Criminal responsibility and social constraint.

Mode of access: Internet.

The rate of return, rate base methods, and the regulatory constraint /

Bibliography: leaves 18-19.

Nonbreeding Eastern Curlews Numenius madagascariensis Do Not Increase the Rate of Intake or Digestive Efficiency before Long-Distance Migration because of an Apparent Digestive Constraint

The possibility of premigratory modulation in gastric digestive performance was investigated in a long-distance migrant, the eastern curlew (Numenius madagascariensis), in eastern Australia. The rate of intake in the curlews was limited by the rate of digestion but not by food availability. It was hypothesized that before migration, eastern curlews would meet the increased energy demand by increasing energy consumption. It was predicted that (1) an increase in the rate of intake and the corresponding rate of gastric throughput would occur or (2) the gastric digestive efficiency would increase between the mid-nonbreeding and premigratory periods. Neither crude intake rate (the rate of intake calculated including inactive pauses; 0.22 g DM [grams dry mass] or 3.09 kJ min(-1)) nor the rate of gastric throughput (0.15 g DM or 2.85 kJ min(-1)) changed over time. Gastric digestive efficiency did not improve between the periods (91%) nor did the estimated overall energy assimilation efficiency (63% and 58%, respectively). It was concluded that the crustacean-dominated diet of the birds is processed at its highest rate and efficiency throughout a season. It appears that without a qualitative shift in diet, no increase in intake rate is possible. Accepting these findings at their face value poses the question of how and over what time period the eastern curlews store the nutrients necessary for the ensuing long, northward nonstop flight.

Lack of an osmotic constraint on intake rate of the eastern curlew Numenius madagascariensis

Rates of food intake in animals consuming abundant prey can be constrained by the rates of digestion or excretion of ingested substances, such as salt, particularly so in the animals that regularly migrate between freshwater and saltwater environments. We tested this hypothesis in a long-distance migrant shorebird, the eastern curlew Numenius madagascariensis (suborder Charadrii), foraging on intertidal decapods in eastern Australia. We predicted that if food intake rates are constrained osmotically, individuals with access to freshwater and less saline prey (FW group) would have higher rates of food and water intake than individuals with seawater-only access (SW group). Food intake rates did not differ between the FW and SW groups (0.14 g ash-free dry mass min(-1)), nor did the water influx rates (0.75 g min(-1)). Salt intake rates were lower at FW sites (19.3 versus 23.3 mg NaCl min(-1)) and overall they were similar to those of marine birds. Food intake rate in the eastern curlew appeared limited by digestive rather than by osmoregulatory capacity.