Compositional model repositories via dynamic constraint satisfaction with order-of-magnitude preferences

J. Keppens and Q. Shen. Compositional model repositories via dynamic constraint satisfaction with order-of-magnitude preferences. Journal of Artificial Intelligence Research, 21:499-550, 2004.

A genetic algorithm based economic dispatch (GAED) with environmental constraint optimisation

The role of renewable energy in power systems is becoming more significant due to the increasing cost of fossil fuels and climate change concerns. However, the inclusion of Renewable Energy Generators (REG), such as wind power, has created additional problems for power system operators due to the variability and lower predictability of output of most REGs, with the Economic Dispatch (ED) problem being particularly difficult to resolve. In previous papers we had reported on the inclusion of wind power in the ED calculations. The simulation had been performed using a system model with wind power as an intermittent source, and the results of the simulation have been compared to that of the Direct Search Method (DSM) for similar cases. In this paper we report on our continuing investigations into using Genetic Algorithms (GA) for ED for an independent power system with a significant amount of wind energy in its generator portfolio. The results demonstrate, in line with previous reports in the literature, the effectiveness of GA when measured against a benchmark technique such as DSM.

System F with Constraint Types

System F is a type system that can be seen as both a proof system for second-order propositional logic and as a polymorphic programming language. In this work we explore several extensions of System F by types which express subtyping constraints. These systems include terms which represent proofs of subtyping relationships between types. Given a proof that one type is a subtype of another, one may use a coercion term constructor to coerce terms from the first type to the second. The ability to manipulate type constraints as first-class entities gives these systems a lot of expressive power, including the ability to encode generalized algebraic data types and intensional type analysis. The main contributions of this work are in the formulation of constraint types and a proof of strong normalization for an extension of System F with constraint types.

Constraint-based Mining of Frequent Arrangements of Temporal Intervals

The problem of discovering frequent arrangements of temporal intervals is studied. It is assumed that the database consists of sequences of events, where an event occurs during a time-interval. The goal is to mine temporal arrangements of event intervals that appear frequently in the database. The motivation of this work is the observation that in practice most events are not instantaneous but occur over a period of time and different events may occur concurrently. Thus, there are many practical applications that require mining such temporal correlations between intervals including the linguistic analysis of annotated data from American Sign Language as well as network and biological data. Two efficient methods to find frequent arrangements of temporal intervals are described; the first one is tree-based and uses depth first search to mine the set of frequent arrangements, whereas the second one is prefix-based. The above methods apply efficient pruning techniques that include a set of constraints consisting of regular expressions and gap constraints that add user-controlled focus into the mining process. Moreover, based on the extracted patterns a standard method for mining association rules is employed that applies different interestingness measures to evaluate the significance of the discovered patterns and rules. The performance of the proposed algorithms is evaluated and compared with other approaches on real (American Sign Language annotations and network data) and large synthetic datasets.

Computing explanations for interactive constraint-based systems

Constraint programming has emerged as a successful paradigm for modelling combinatorial problems arising from practical situations. In many of those situations, we are not provided with an immutable set of constraints. Instead, a user will modify his requirements, in an interactive fashion, until he is satisfied with a solution. Examples of such applications include, amongst others, model-based diagnosis, expert systems, product configurators. The system he interacts with must be able to assist him by showing the consequences of his requirements. Explanations are the ideal tool for providing this assistance. However, existing notions of explanations fail to provide sufficient information. We define new forms of explanations that aim to be more informative. Even if explanation generation is a very hard task, in the applications we consider, we must manage to provide a satisfactory level of interactivity and, therefore, we cannot afford long computational times. We introduce the concept of representative sets of relaxations, a compact set of relaxations that shows the user at least one way to satisfy each of his requirements and at least one way to relax them, and present an algorithm that efficiently computes such sets. We introduce the concept of most soluble relaxations, maximising the number of products they allow. We present algorithms to compute such relaxations in times compatible with interactivity, achieving this by indifferently making use of different types of compiled representations. We propose to generalise the concept of prime implicates to constraint problems with the concept of domain consequences, and suggest to generate them as a compilation strategy. This sets a new approach in compilation, and allows to address explanation-related queries in an efficient way. We define ordered automata to compactly represent large sets of domain consequences, in an orthogonal way from existing compilation techniques that represent large sets of solutions.

Identifying sources of global contention in constraint satisfaction search

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine-grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this work we present two methods for learning from search using restarts, in order to identify these critical variables prior to solving. Both methods are based on the conflict-directed heuristic (weighted-degree heuristic) introduced by Boussemart et al. and are aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimizing the overhead of these restarts. We further examine the impact of different sampling strategies and different measurements of contention, and assess different restarting strategies for the heuristic. Finally, two applications for constraint weighting are considered in detail: dynamic constraint satisfaction problems and unary resource scheduling problems.

Burning a hole in the budget: tobacco spending and its crowd-out of other goods.

Smoking is an expensive habit. Smoking households spend, on average, more than $US1000 annually on cigarettes. When a family member quits, in addition to the former smoker's improved long-term health, families benefit because savings from reduced cigarette expenditures can be allocated to other goods. For households in which some members continue to smoke, smoking expenditures crowd-out other purchases, which may affect other household members, as well as the smoker. We empirically analyse how expenditures on tobacco crowd-out consumption of other goods, estimating the patterns of substitution and complementarity between tobacco products and other categories of household expenditure. We use the Consumer Expenditure Survey data for the years 1995-2001, which we complement with regional price data and state cigarette prices. We estimate a consumer demand system that includes several main expenditure categories (cigarettes, food, alcohol, housing, apparel, transportation, medical care) and controls for socioeconomic variables and other sources of observable heterogeneity. Descriptive data indicate that, comparing smokers to nonsmokers, smokers spend less on housing. Results from the demand system indicate that as the price of cigarettes rises, households increase the quantity of food purchased, and, in some samples, reduce the quantity of apparel and housing purchased.

Changes in landing mechanics in patients following anterior cruciate ligament reconstruction when wearing an extension constraint knee brace.

BACKGROUND: Anterior cruciate ligament (ACL) reconstruction is associated with a high incidence of second tears (graft tears and contralateral ACL tears). These secondary tears have been attributed to asymmetrical lower extremity mechanics. Knee bracing is one potential intervention that can be used during rehabilitation that has the potential to normalize lower extremity asymmetry; however, little is known about the effect of bracing on movement asymmetry in patients following ACL reconstruction. HYPOTHESIS: Wearing a knee brace would increase knee joint flexion and joint symmetry. It was also expected that the joint mechanics would become more symmetrical in the braced condition. OBJECTIVE: To examine how knee bracing affects knee joint function and symmetry over the course of rehabilitation in patients 6 months following ACL reconstruction. STUDY DESIGN: Controlled laboratory study. LEVEL OF EVIDENCE: Level 3. METHODS: Twenty-three adolescent patients rehabilitating from ACL reconstruction surgery were recruited for the study. The subjects all underwent a motion analysis assessment during a stop-jump activity with and without a functional knee brace on the surgical side that resisted extension for 6 months following the ACL reconstruction surgery. Statistical analysis utilized a 2 × 2 (limb × brace) analysis of variance with a significant alpha level of 0.05. RESULTS: Subjects had increased knee flexion on the surgical side when they were braced. The brace condition increased knee flexion velocity, decreased the initial knee flexion angle, and increased the ground reaction force and knee extension moment on both limbs. Side-to-side asymmetry was present across conditions for the vertical ground reaction force and knee extension moment. CONCLUSION: Wearing a knee brace appears to increase lower extremity compliance and promotes normalized loading on the surgical side. CLINICAL RELEVANCE: Knee extension constraint bracing in postoperative ACL patients may improve symmetry of lower extremity mechanics, which is potentially beneficial in progressing rehabilitation and reducing the incidence of second ACL tears.

Two-machine open shop scheduling with an availability constraint

We study a two-machine open shop scheduling problem, in which one machine is not available for processing during a given time interval. The objective is to minimize the makespan. We show that the problem is NP-hard and present an approximation algorithm with a worst-case ratio of 4/3.

Characterizing the most general temporal constraint

This paper introduces a characterization of the so-called most general temporal constraint (GTC), which guarantees the common-sense assertion that "the beginning of the effect cannot precede the beginning of the cause". The formalism is based on general time theory which takes both points and intervals as primitive. It is shown that there are in fact 8 possible causal relationships which satisfy GTC, including cases where, on the one hand, effects start simultaneously with, during, immediately after, or some time after their causes, and on the other hand, events end before, simultaneously with, or after their causes. These causal relationships are versatile enough to subsume those representatives in the literature.

A price worth paying?: Women and work – choice, constraint or satisficing

Purpose – Are women held back or holding back? Do women choose their jobs/careers or are they structurally or normatively constrained? The purpose of this paper is to shed fresh light on these questions and contribute to an on-going debate that has essentially focused on the extent to which part-time work is women’s choice, the role of structural and organisational constraints and the role of men in excluding women. Design/methodology/approach – The paper uses data from interviews with 80 working women – both full-time and part-time – performing diverse work roles in a range of organisations in the south east of England. Findings – It was found that many women do not make strategic job choices, rather they often ‘‘fall into’’ jobs that happen to be available to them. Some would not have aspired to their present jobs without male encouragement; many report incidents of male exclusion; and virtually all either know or suspect that they are paid less than comparable men. Those working reduced hours enjoy that facility, yet they are aware that reduced hours and senior roles are seen as incompatible. In short, they recognise both the positive and negative aspects of their jobs, whether they work full or part-time, whether they work in male-dominated or female-dominated occupations, and whatever their position in the organisational hierarchy. Accordingly, the paper argues that the concept of ‘‘satisficing’’, i.e. a decision which is good enough but not optimal, is a more appropriate way to view women’s working lives than are either choice or constraint theories. Originality/value – There is an ongoing, and often polarised, debate between those who maintain that women choose whether to give preference to work or home/family and others who maintain that women, far from being self-determining actors, are constrained structurally and normatively. Rather than supporting these choice or constraint theories, this paper argues that ‘‘satisficing’’ is a more appropriate and nuanced concept to explain women’s working lives.

Parameterisation of bivalve functional traits for mechanistic eco-physiological dynamic energy budget (DEB) models

Mechanistic models such as those based on dynamic energy budget (DEB) theory are emergent ecomechanics tools to investigate the extent of fitness in organisms through changes in life history traits as explained by bioenergetic principles. The rapid growth in interest around this approach originates from the mechanistic characteristics of DEB, which are based on a number of rules dictating the use of mass and energy flow through organisms. One apparent bottleneck in DEB applications comes from the estimations of DEB parameters which are based on mathematical and statistical methods (covariation method). The parameterisation process begins with the knowledge of some functional traits of a target organism (e. g. embryo, sexual maturity and ultimate body size, feeding and assimilation rates, maintenance costs), identified from the literature or laboratory experiments. However, considering the prominent role of the mechanistic approach in ecology, the reduction of possible uncertainties is an important objective. We propose a revaluation of the laboratory procedures commonly used in ecological studies to estimate DEB parameters in marine bivalves. Our experimental organism was Brachidontes pharaonis. We supported our proposal with a validation exercise which compared life history traits as obtained by DEBs (implemented with parameters obtained using classical laboratory methods) with the actual set of species traits obtained in the field. Correspondence between the 2 approaches was very high (>95%) with respect to estimating both size and fitness. Our results demonstrate a good agreement between field data and model output for the effect of temperature and food density on age-size curve, maximum body size and total gamete production per life span. The mechanistic approach is a promising method of providing accurate predictions in a world that is under in creasing anthropogenic pressure.

Global carbon budget 2014

Accurate assessment of anthropogenic carbon dioxide (CO2) emissions and their redistribution among the atmosphere, ocean, and terrestrial biosphere is important to better understand the global carbon cycle, support the development of climate policies, and project future climate change. Here we describe data sets and a methodology to quantify all major components of the global carbon budget, including their uncertainties, based on the combination of a range of data, algorithms, statistics, and model estimates and their interpretation by a broad scientific community. We discuss changes compared to previous estimates, consistency within and among components, alongside methodology and data limitations. CO2 emissions from fossil fuel combustion and cement production (E-FF) are based on energy statistics and cement production data, respectively, while emissions from land-use change (E-LUC), mainly deforestation, are based on combined evidence from land-cover-change data, fire activity associated with deforestation, and models. The global atmospheric CO2 concentration is measured directly and its rate of growth (G(ATM)) is computed from the annual changes in concentration. The mean ocean CO2 sink (S-OCEAN) is based on observations from the 1990s, while the annual anomalies and trends are estimated with ocean models. The variability in S-OCEAN is evaluated with data products based on surveys of ocean CO2 measurements. The global residual terrestrial CO2 sink (S-LAND) is estimated by the difference of the other terms of the global carbon budget and compared to results of independent dynamic global vegetation models forced by observed climate, CO2, and land-cover-change (some including nitrogen-carbon interactions). We compare the mean land and ocean fluxes and their variability to estimates from three atmospheric inverse methods for three broad latitude bands. All uncertainties are reported as +/- 1 sigma, reflecting the current capacity to characterise the annual estimates of each component of the global carbon budget. For the last decade available (2004-2013), E-FF was 8.9 +/- 0.4 GtC yr(-1), E-LUC 0.9 +/- 0.5 GtC yr(-1), G(ATM) 4.3 +/- 0.1 GtC yr(-1), S-OCEAN 2.6 +/- 0.5 GtC yr(-1), and S-LAND 2.9 +/- 0.8 GtC yr(-1). For year 2013 alone, E-FF grew to 9.9 +/- 0.5 GtC yr(-1), 2.3% above 2012, continuing the growth trend in these emissions, E-LUC was 0.9 +/- 0.5 GtC yr(-1), G(ATM) was 5.4 +/- 0.2 GtC yr(-1), S-OCEAN was 2.9 +/- 0.5 GtC yr(-1), and S-LAND was 2.5 +/- 0.9 GtC yr(-1). G(ATM) was high in 2013, reflecting a steady increase in E-FF and smaller and opposite changes between S-OCEAN and S-LAND compared to the past decade (2004-2013). The global atmospheric CO2 concentration reached 395.31 +/- 0.10 ppm averaged over 2013. We estimate that E-FF will increase by 2.5% (1.3-3.5 %) to 10.1 +/- 0.6 GtC in 2014 (37.0 +/- 2.2 GtCO(2) yr(-1)), 65% above emissions in 1990, based on projections of world gross domestic product and recent changes in the carbon intensity of the global economy. From this projection of E-FF and assumed constant E-LUC for 2014, cumulative emissions of CO2 will reach about 545 +/- 55 GtC (2000 +/- 200 GtCO(2)) for 1870-2014, about 75% from E-FF and 25% from E-LUC. This paper documents changes in the methods and data sets used in this new carbon budget compared with previous publications of this living data set (Le Quere et al., 2013, 2014). All observations presented here can be downloaded from the Carbon Dioxide Information Analysis Center (doi:10.3334/CDIAC/GCP_2014).