Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

Constraint reasoning for differential models

The basic motivation of this work was the integration of biophysical models within the interval constraints framework for decision support. Comparing the major features of biophysical models with the expressive power of the existing interval constraints framework, it was clear that the most important inadequacy was related with the representation of differential equations. System dynamics is often modelled through differential equations but there was no way of expressing a differential equation as a constraint and integrate it within the constraints framework. Consequently, the goal of this work is focussed on the integration of ordinary differential equations within the interval constraints framework, which for this purpose is extended with the new formalism of Constraint Satisfaction Differential Problems. Such framework allows the specification of ordinary differential equations, together with related information, by means of constraints, and provides efficient propagation techniques for pruning the domains of their variables. This enabled the integration of all such information in a single constraint whose variables may subsequently be used in other constraints of the model. The specific method used for pruning its variable domains can then be combined with the pruning methods associated with the other constraints in an overall propagation algorithm for reducing the bounds of all model variables. The application of the constraint propagation algorithm for pruning the variable domains, that is, the enforcement of local-consistency, turned out to be insufficient to support decision in practical problems that include differential equations. The domain pruning achieved is not, in general, sufficient to allow safe decisions and the main reason derives from the non-linearity of the differential equations. Consequently, a complementary goal of this work proposes a new strong consistency criterion, Global Hull-consistency, particularly suited to decision support with differential models, by presenting an adequate trade-of between domain pruning and computational effort. Several alternative algorithms are proposed for enforcing Global Hull-consistency and, due to their complexity, an effort was made to provide implementations able to supply any-time pruning results. Since the consistency criterion is dependent on the existence of canonical solutions, it is proposed a local search approach that can be integrated with constraint propagation in continuous domains and, in particular, with the enforcing algorithms for anticipating the finding of canonical solutions. The last goal of this work is the validation of the approach as an important contribution for the integration of biophysical models within decision support. Consequently, a prototype application that integrated all the proposed extensions to the interval constraints framework is developed and used for solving problems in different biophysical domains.

Socioeconomic inequality in catastrophic health expenditure in Brazil

OBJECTIVE To analyze the evolution of catastrophic health expenditure and the inequalities in such expenses, according to the socioeconomic characteristics of Brazilian families.METHODS Data from the National Household Budget 2002-2003 (48,470 households) and 2008-2009 (55,970 households) were analyzed. Catastrophic health expenditure was defined as excess expenditure, considering different methods of calculation: 10.0% and 20.0% of total consumption and 40.0% of the family’s capacity to pay. The National Economic Indicator and schooling were considered as socioeconomic characteristics. Inequality measures utilized were the relative difference between rates, the rates ratio, and concentration index.RESULTS The catastrophic health expenditure varied between 0.7% and 21.0%, depending on the calculation method. The lowest prevalences were noted in relation to the capacity to pay, while the highest, in relation to total consumption. The prevalence of catastrophic health expenditure increased by 25.0% from 2002-2003 to 2008-2009 when the cutoff point of 20.0% relating to the total consumption was considered and by 100% when 40.0% or more of the capacity to pay was applied as the cut-off point. Socioeconomic inequalities in the catastrophic health expenditure in Brazil between 2002-2003 and 2008-2009 increased significantly, becoming 5.20 times higher among the poorest and 4.17 times higher among the least educated.CONCLUSIONS There was an increase in catastrophic health expenditure among Brazilian families, principally among the poorest and those headed by the least-educated individuals, contributing to an increase in social inequality.

The black box of health care expenditure growth determinants

In this paper, the determinants of growth of aggregate health expenditures are investigated. The study departs from previous literature in that it looks at differences across countries in growth (and not levels) of health care expenditures. Estimation is made for 24 OECD countries. Health system characteristics usually believed to influence health expenditures growth, like population ageing, the type of health system (public reimbursement, public contract or integrate) and existence of gatekeepers, are found to be non-significant. Nevertheless, there is evidence that health expenditures experienced a clear slower growth in the last decade. The explanation for this slowdown could not be found in the proposed model and should stimulate further research.

Modern techniques for constraint solving the CASPER experience

Dissertação apresentada para obtenção do Grau de Doutor em Engenharia Informática, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Constraint-based modeling of minimum set covering: application to species differentation

Work presented in the context of the European Master in Computational Logics, as partial requisit for the graduation as Master in Computational Logics

Constraint-based verification of imperative programs

work presented in the context of the European Master’s program in Computational Logic, as the partial requirement for obtaining Master of Science degree in Computational Logic

Research and development expenditure in the business sector as indicator of knowledge economy: the Portuguese experience

The objective of the paper is to help to understand recent changes in the structure of R&D activities, by analyzing data on the expenditure of the business sector in research and development (R&D). The results are framed in an international context, through comparison with indicators from the most developed countries, divided by technological intensity and economic activity. The study reveals that the indicators of Portuguese R&D expenditure in the business sector are closely linked both to fiscal policy and to high foreign direct investment in knowledge-intensive industries. It also links these indicators to phenomena such as the abundance of skilled labor in pharmaceutical industries and the government intervention in some sectors of the economy (namely health and rail transportation).

Probabilistic constraint reasoning

Dissertação apresentada para obtenção do Grau de Doutor em Engenharia Informática, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Constraint-based modelling of mixed microbial populations: Application to polyhydroxyalkanoates production

Dissertação para obtenção do Grau de Doutor em Engenharia Química e Bioquímica

Constraint reasoning with local search for continuous optimization

Optimization is a very important field for getting the best possible value for the optimization function. Continuous optimization is optimization over real intervals. There are many global and local search techniques. Global search techniques try to get the global optima of the optimization problem. However, local search techniques are used more since they try to find a local minimal solution within an area of the search space. In Continuous Constraint Satisfaction Problems (CCSP)s, constraints are viewed as relations between variables, and the computations are supported by interval analysis. The continuous constraint programming framework provides branch-and-prune algorithms for covering sets of solutions for the constraints with sets of interval boxes which are the Cartesian product of intervals. These algorithms begin with an initial crude cover of the feasible space (the Cartesian product of the initial variable domains) which is recursively refined by interleaving pruning and branching steps until a stopping criterion is satisfied. In this work, we try to find a convenient way to use the advantages in CCSP branchand- prune with local search of global optimization applied locally over each pruned branch of the CCSP. We apply local search techniques of continuous optimization over the pruned boxes outputted by the CCSP techniques. We mainly use steepest descent technique with different characteristics such as penalty calculation and step length. We implement two main different local search algorithms. We use “Procure”, which is a constraint reasoning and global optimization framework, to implement our techniques, then we produce and introduce our results over a set of benchmarks.

Probabilistic constraint reasoning with Monte Carlo integration to robot localization

This work studies the combination of safe and probabilistic reasoning through the hybridization of Monte Carlo integration techniques with continuous constraint programming. In continuous constraint programming there are variables ranging over continuous domains (represented as intervals) together with constraints over them (relations between variables) and the goal is to find values for those variables that satisfy all the constraints (consistent scenarios). Constraint programming “branch-and-prune” algorithms produce safe enclosures of all consistent scenarios. Special proposed algorithms for probabilistic constraint reasoning compute the probability of sets of consistent scenarios which imply the calculation of an integral over these sets (quadrature). In this work we propose to extend the “branch-and-prune” algorithms with Monte Carlo integration techniques to compute such probabilities. This approach can be useful in robotics for localization problems. Traditional approaches are based on probabilistic techniques that search the most likely scenario, which may not satisfy the model constraints. We show how to apply our approach in order to cope with this problem and provide functionality in real time.

Determinants of social security pensions expenditure in Portugal

In most European countries Social Security (SS) systems are characterized as Pay-asyou- go systems. Their sustainability is being challenged with demographic changes, namely population ageing. Portugal’s population is ageing rapidly being one of the countries where this problem is more critical. With the growing debate on this topic several public choice models have been developed so as to explain SS size. In this work project there is an attempt to understand whether these models contribute to better explain Social security expenditure with pensions (SSEP) and to establish the need of finding ways to reduce present commitment with pension expenditure in Portugal.

Energy expenditure after 2- to 3-hour elective surgical operations

Energy expenditure was measured by indirect calorimetry in 17 adult patients (8 women and 9 men) before surgery, 4 hours immediately after surgery , and 24 hours late after surgery in patients undergoing elective surgery of small-to-medium scope. MATERIAL AND METHODS: The total duration of surgery ranged from 2 to 3 hours. Repeated measures were performed on the same patient, so that each patient was considered to be his/her own control. All patients received a 5% dextrose solution (2000 mL/day) throughout the postoperative period. RESULTS: Men showed a reduction in CO2 production during the immediately after surgery period (257±42 mL/min) compared to before surgery (306±48 mL/min) and late after surgery (301±45 mL/min); this reduction was not observed in women. Energy expenditure was also lower in men during immediately after surgery (6.6 kJ/min). None of the other measurements, including substrate oxidation, showed significant differences. CONCLUSION: Therefore, elective surgery itself cannot be considered an important trauma that would result in increased energy expenditure. According to this study, it is not necessary to prescribe an energy supply exceeding basal expenditure during the immediate after-surgery period. The present results suggest that the energy supply prescribed during the postoperative period after elective surgery of small-to-medium scope should not exceed 5-7 kJ/min, so the patient does not receive a carbohydrate overload from energy supplementation.

Associations between energetic expenditure, physical activity and body composition: exploratory study with industrial workers

This study, which involved a target population comprised by 292 workers of different industrial areas (metalmechanics, foundry, chemical, wood, food), aimed to verify the association between energy expenditure-EE, physical activity level-PAL and body composition (Body Mass Index-BMI, Waist-Hip Ratio-WHR and Waist To Height Ratio, WTHR) of participants. The work was completed with the description of the variables relating to the gender of the individuals (male and female) and the activities carried out in the two sectors of industrial work (administrative sector and productive sector). In this research, the statistical technique of principal components analysis (PCA) and the hierarchical analysis of clusters (HCA) were used. Sociodemographic and anthropometric data were collected as well as the level of physical activity and energy expenditure were assessed. The vast majority of individuals who spend greater energy expenditure and has more intense physical activity were male. Most of these workers are in the production sector. We can confirm that that both, gender and labor activity, are factors that have influence on the EE and the PAL.