Towards a Multi-device Constraints Solver

To reduce the amount of time needed to solve the most complex Constraint Satisfaction Problems (CSPs) usually multi-core CPUs are used. There are already many applications capable of harnessing the parallel power of these devices to speed up the CSPs solving process. Nowadays, the Graphics Processing Units (GPUs) possess a level of parallelism that surpass the CPUs, containing from a few hundred to a few thousand cores and there are much less applications capable of solving CSPs on GPUs, leaving space for possible improvements. This article describes the work in progress for solving CSPs on GPUs and CPUs and compares results with some state-of-the-art solvers, presenting already some good results on GPUs.

Asymmetrically fair rules for an indivisible good problem with a budget constraint

We study a particular restitution problem where there is an indivisible good (land or property) over which two agents have rights: the dispossessed agent and the owner. A third party, possibly the government, seeks to resolve the situation by assigning rights to one and compensate the other. There is also a maximum amount of money available for the compensation. We characterize a family of asymmetrically fair rules that are immune to strategic behavior, guarantee minimal welfare levels for the agents, and satisfy the budget constraint.

Conditioning of the weak-constraint variational data assimilation problem for numerical weather prediction

4-Dimensional Variational Data Assimilation (4DVAR) assimilates observations through the minimisation of a least-squares objective function, which is constrained by the model flow. We refer to 4DVAR as strong-constraint 4DVAR (sc4DVAR) in this thesis as it assumes the model is perfect. Relaxing this assumption gives rise to weak-constraint 4DVAR (wc4DVAR), leading to a different minimisation problem with more degrees of freedom. We consider two wc4DVAR formulations in this thesis, the model error formulation and state estimation formulation. The 4DVAR objective function is traditionally solved using gradient-based iterative methods. The principle method used in Numerical Weather Prediction today is the Gauss-Newton approach. This method introduces a linearised `inner-loop' objective function, which upon convergence, updates the solution of the non-linear `outer-loop' objective function. This requires many evaluations of the objective function and its gradient, which emphasises the importance of the Hessian. The eigenvalues and eigenvectors of the Hessian provide insight into the degree of convexity of the objective function, while also indicating the difficulty one may encounter while iterative solving 4DVAR. The condition number of the Hessian is an appropriate measure for the sensitivity of the problem to input data. The condition number can also indicate the rate of convergence and solution accuracy of the minimisation algorithm. This thesis investigates the sensitivity of the solution process minimising both wc4DVAR objective functions to the internal assimilation parameters composing the problem. We gain insight into these sensitivities by bounding the condition number of the Hessians of both objective functions. We also precondition the model error objective function and show improved convergence. We show that both formulations' sensitivities are related to error variance balance, assimilation window length and correlation length-scales using the bounds. We further demonstrate this through numerical experiments on the condition number and data assimilation experiments using linear and non-linear chaotic toy models.

Quantization of (2+1)-spinning particles and bifermionic constraint problem

This work is a natural continuation of our recent study in quantizing relativistic particles. There it was demonstrated that, by applying a consistent quantization scheme to the classical model of a spinless relativistic particle as well as to the Berezin-Marinov model of a 3 + 1 Dirac particle, it is possible to obtain a consistent relativistic quantum mechanics of such particles. In the present paper, we apply a similar approach to the problem of quantizing the massive 2 + 1 Dirac particle. However, we stress that such a problem differs in a nontrivial way from the one in 3 + 1 dimensions. The point is that in 2 + 1 dimensions each spin polarization describes different fermion species. Technically this fact manifests itself through the presence of a bifermionic constant and of a bifermionic first-class constraint. In particular, this constraint does not admit a conjugate gauge condition at the classical level. The quantization problem in 2 + 1 dimensions is also interesting from the physical viewpoint (e.g., anyons). In order to quantize the model, we first derive a classical formulation in an effective phase space, restricted by constraints and gauges. Then the condition of preservation of the classical symmetries allows us to realize the operator algebra in an unambiguous way and construct an appropriate Hilbert space. The physical sector of the constructed quantum mechanics contains spin-1/2 particles and antiparticles without an infinite number of negative-energy levels, and exactly reproduces the one-particle sector of the 2 + 1 quantum theory of a spinor field.

Solving the multiobjective environmental/economic dispatch problem using weighted sum and ε-constraint strategies and a predictor-corrector primal-dual interior point method

This paper proposes a technique for solving the multiobjective environmental/economic dispatch problem using the weighted sum and ε-constraint strategies, which transform the problem into a set of single-objective problems. In the first strategy, the objective function is a weighted sum of the environmental and economic objective functions. The second strategy considers one of the objective functions: in this case, the environmental function, as a problem constraint, bounded above by a constant. A specific predictor-corrector primal-dual interior point method which uses the modified log barrier is proposed for solving the set of single-objective problems generated by such strategies. The purpose of the modified barrier approach is to solve the problem with relaxation of its original feasible region, enabling the method to be initialized with unfeasible points. The tests involving the proposed solution technique indicate i) the efficiency of the proposed method with respect to the initialization with unfeasible points, and ii) its ability to find a set of efficient solutions for the multiobjective environmental/economic dispatch problem.

A STUDY OF PENALTY FORMULATIONS USED IN THE NUMERICAL APPROXIMATION OF A RADIALLY SYMMETRIC ELASTICITY PROBLEM

We consider a class of two-dimensional problems in classical linear elasticity for which material overlapping occurs in the absence of singularities. Of course, material overlapping is not physically realistic, and one possible way to prevent it uses a constrained minimization theory. In this theory, a minimization problem consists of minimizing the total potential energy of a linear elastic body subject to the constraint that the deformation field must be locally invertible. Here, we use an interior and an exterior penalty formulation of the minimization problem together with both a standard finite element method and classical nonlinear programming techniques to compute the minimizers. We compare both formulations by solving a plane problem numerically in the context of the constrained minimization theory. The problem has a closed-form solution, which is used to validate the numerical results. This solution is regular everywhere, including the boundary. In particular, we show numerical results which indicate that, for a fixed finite element mesh, the sequences of numerical solutions obtained with both the interior and the exterior penalty formulations converge to the same limit function as the penalization is enforced. This limit function yields an approximate deformation field to the plane problem that is locally invertible at all points in the domain. As the mesh is refined, this field converges to the exact solution of the plane problem.

Reducing problem behavior during care-giving in families of preschool-aged children with developmental disabilities

This study evaluated two variants of a behavioral parent training program known as Stepping Stones Triple P (SSTP) using 74 preschool-aged children with developmental disabilities. Families were randomly allocated to an enhanced parent training intervention that combined parenting skills and care-giving coping skills (SSTP-E), standard parent training intervention alone (SSTP-S) or waitlist control (WL) condition. At post-intervention, both programs were associated with lower levels of observed negative child behavior, reductions in the number of care-giving settings where children displayed problem behavior, and improved parental competence and satisfaction in the parenting role as compared with the waitlist condition. Gains attained at post-intervention were maintained at 1-year follow-up. Both interventions produced significant reductions in child problem behavior, with 67% of children in the SSTP-E and 77% of children in the SSTPS showing clinically reliable change from pre-intervention to follow-up. Parents reported a high level of satisfaction with both interventions.

Women's satisfaction with general practice consultations

Objective: To determine women's satisfaction with general practice services. Design: Cross-sectional postal questionnaire conducted during April to September 1996 (part of the baseline survey of the Australian Longitudinal Study on Women's Health). Participants: Women aged 18-22 (n=14739), 45-49 (n=14013) and 70-74 (n=12941) years, randomly selected from the Medicare database, with oversampling of women from rural and remote areas. Main outcome measures: Frequency of use of general practice services; satisfaction with the most recent visit to a general practitioner (CP), prevalence of selected symptoms; preference for a female doctor. Results: The most recent visit to a GP was rated overall as good, very good or excellent by more than 80% of women, with increasing levels of satisfaction with increasing age of the women. However, satisfaction was lower for waiting room time and cost of the visit. A third of the young and middle-aged women living in rural and remote areas were dissatisfied with the cost of the visit. Young women were more likely to prefer a female doctor, and many were dissatisfied with their GP's skills at explaining their problem and giving them a chance to give an opinion and ask questions. The most prevalent symptoms for all women included headaches and tiredness, and many were not satisfied with the health services available to help them deal with these symptoms. Conclusions: Australian women have high levels of satisfaction with GP consultations. However, more effective strategies may be needed to improve communication with younger women, and there is an unmet need for services to help all women deal with some common symptoms. Dissatisfaction with cost of services and women's preference for female doctors have implications for future health policy.

Materialized view selection under the maintenance time constraint

A data warehouse is a data repository which collects and maintains a large amount of data from multiple distributed, autonomous and possibly heterogeneous data sources. Often the data is stored in the form of materialized views in order to provide fast access to the integrated data. One of the most important decisions in designing a data warehouse is the selection of views for materialization. The objective is to select an appropriate set of views that minimizes the total query response time with the constraint that the total maintenance time for these materialized views is within a given bound. This view selection problem is totally different from the view selection problem under the disk space constraint. In this paper the view selection problem under the maintenance time constraint is investigated. Two efficient, heuristic algorithms for the problem are proposed. The key to devising the proposed algorithms is to define good heuristic functions and to reduce the problem to some well-solved optimization problems. As a result, an approximate solution of the known optimization problem will give a feasible solution of the original problem. (C) 2001 Elsevier Science B.V. All rights reserved.

Scheduling maintenance activities of electric power transmission networks using an hybrid constraint method

In this paper we present a Constraint Logic Programming (CLP) based model, and hybrid solving method for the Scheduling of Maintenance Activities in the Power Transmission Network. The model distinguishes from others not only because of its completeness but also by the way it models and solves the Electric Constraints. Specifically we present a efficient filtering algorithm for the Electrical Constraints. Furthermore, the solving method improves the pure CLP methods efficiency by integrating a type of Local Search technique with CLP. To test the approach we compare the method results with another method using a 24 bus network, which considerers 42 tasks and 24 maintenance periods.

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.

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

A Communication Intervention for Training Southern European Oncologists to Recognize Psychosocial Morbidity in Cancer. I - Development of the Model and Preliminary Results on Physicians' Satisfaction

BACKGROUND: The detection of psychosocial distress is a significant communication problem in Southern Europe and other countries. Work in this area is hampered by a lack of data. Because not much is known about training aimed at improving the recognition of psychosocial disorders in cancer patients, we developed a basic course model for medical oncology professionals. METHODS: A specific educational and experiential model (12 hours divided into 2 modules) involving formal teaching (ie, journal articles, large-group presentations), practice in small groups (ie, small-group exercises and role playing), and discussion in large groups was developed with the aim of improving the ability of oncologists to detect emotional disturbances in cancer patients (ie, depression, anxiety, and adjustment disorders). RESULTS: A total of 30 oncologists from 3 Southern European countries (Italy, Portugal, and Spain) participated in the workshop. The training course was well accepted by most participants who expressed general satisfaction and a positive subjective perception of the utility of the course for clinical practice. Of the total participants, 28 physicians (93.3%) thought that had they been exposed to this material sooner, they would have incorporated the techniques received in the workshop into their practices; 2 participants stated they would likely have done so. Half of the doctors (n = 15) believed that their clinical communication techniques were improved by participating in the workshop, and the remaining half thought that their abilities to communicate with cancer patients had improved. CONCLUSIONS: This model is a feasible approach for oncologists and is easily applicable to various oncology settings. Further studies will demonstrate the effectiveness of this method for improving oncologists skills in recognizing emotional disorders in their patients with cancer.