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.

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.

Development of Dynamic Constraint Models for a Model Based Transient Calibration Process

Model based calibration has gained popularity in recent years as a method to optimize increasingly complex engine systems. However virtually all model based techniques are applied to steady state calibration. Transient calibration is by and large an emerging technology. An important piece of any transient calibration process is the ability to constrain the optimizer to treat the problem as a dynamic one and not as a quasi-static process. The optimized air-handling parameters corresponding to any instant of time must be achievable in a transient sense; this in turn depends on the trajectory of the same parameters over previous time instances. In this work dynamic constraint models have been proposed to translate commanded to actually achieved air-handling parameters. These models enable the optimization to be realistic in a transient sense. The air handling system has been treated as a linear second order system with PD control. Parameters for this second order system have been extracted from real transient data. The model has been shown to be the best choice relative to a list of appropriate candidates such as neural networks and first order models. The selected second order model was used in conjunction with transient emission models to predict emissions over the FTP cycle. It has been shown that emission predictions based on air-handing parameters predicted by the dynamic constraint model do not differ significantly from corresponding emissions based on measured air-handling parameters.

The Provision and Use of Mental Health Services in Nursing Homes: Results from the National Medical Expenditure Survey

Data from the Institutional Population Component of the National Medical Expenditure Survey were used to provide national estimates of annual mental health service provision and use in nursing homes. In addition, the relationship between service provision and setting characteristics such as ownership, size, Medicaid certification, and chain status was examined. Although more than three quarters of residents with a mental disorder resided at a nursing home that provided counseling services, fewer than one fifth actually received any mental health services within the year.

Leaf Asymmetry as a Developmental Constraint Imposed by Auxin-Dependent Phyllotactic Patterning

In a majority of species, leaf development is thought to proceed in a bilaterally symmetric fashion without systematic asymmetries. This is despite the left and right sides of an initiating primordium occupying niches that differ in their distance from sinks and sources of auxin. Here, we revisit an existing model of auxin transport sufficient to recreate spiral phyllotactic patterns and find previously overlooked asymmetries between auxin distribution and the centers of leaf primordia. We show that it is the direction of the phyllotactic spiral that determines the side of the leaf these asymmetries fall on. We empirically confirm the presence of an asymmetric auxin response using a DR5 reporter and observe morphological asymmetries in young leaf primordia. Notably, these morphological asymmetries persist in mature leaves, and we observe left-right asymmetries in the superficially bilaterally symmetric leaves of tomato (Solanum lycopersicum) and Arabidopsis thaliana that are consistent with modeled predictions. We further demonstrate that auxin application to a single side of a leaf primordium is sufficient to recapitulate the asymmetries we observe. Our results provide a framework to study a previously overlooked developmental axis and provide insights into the developmental constraints imposed upon leaf morphology by auxin-dependent phyllotactic patterning.

Explaining the Ditransitive Person-Role Constraint

This paper proposes a frequency-based explanation of the Ditransitive Person-Role Constraint, a cross-linguistic generalization that can be formulated as follows: "Combinations of bound pronouns with the roles Recipient and Theme are disfavored if the Theme pronoun is first or second person and the Recipient pronoun is third person."

Development and validation of energy expenditure prediction models based on GT3X accelerometer data in 5- to 9-year-old children

Background: Accelerometry has been established as an objective method that can be used to assess physical activity behavior in large groups. The purpose of the current study was to provide a validated equation to translate accelerometer counts of the triaxial GT3X into energy expenditure in young children. Methods: Thirty-two children aged 5–9 years performed locomotor and play activities that are typical for their age group. Children wore a GT3X accelerometer and their energy expenditure was measured with indirect calorimetry. Twenty-one children were randomly selected to serve as development group. A cubic 2-regression model involving separate equations for locomotor and play activities was developed on the basis of model fit. It was then validated using data of the remaining children and compared with a linear 2-regression model and a linear 1-regression model. Results: All 3 regression models produced strong correlations between predicted and measured MET values. Agreement was acceptable for the cubic model and good for both linear regression approaches. Conclusions: The current linear 1-regression model provides valid estimates of energy expenditure for ActiGraph GT3X data for 5- to 9-year-old children and shows equal or better predictive validity than a cubic or a linear 2-regression model.

Accelerometry and Energy Expenditure in Obese Adults and Normal Weight Controls

Objective: To evaluate a new triaxial accelerometer device for prediction of energy expenditure, measured as VO2/kg, in obese adults and normal-weight controls during activities of daily life. Subjects and methods: Thirty-seven obese adults (Body Mass Index (BMI) 37±5.4) and seventeen controls (BMI 23±1.8) performed eight activities for 5 to 8 minutes while wearing a triaxial accelerometer on the right thigh. Simultaneously, VO2 and VCO2 were measured using a portable metabolic system. The relationship between accelerometer counts (AC) and VO2/kg was analysed using spline regression and linear mixed-effects models. Results: For all activities, VO2/kg was significantly lower in obese participants than in normalweight controls. A linear relationship between AC and VO2/kg existed only within accelerometer values from 0 to 300 counts/min, with an increase of 3.7 (95%-confidence interval (CI) 3.4 - 4.1) and 3.9 ml/min (95%-CI 3.4 - 4.3) per increase of 100 counts/min in obese and normal-weight adults, respectively. Linear modelling of the whole range yields wide prediction intervals for VO2/kg of ± 6.3 and ±7.3 ml/min in both groups. Conclusion: In obese and normal-weight adults, the use of AC for predicting energy expenditure, defined as VO2/kg, from a broad range of physical activities, characterized by varying intensities and types of muscle work, is limited.

Energy expenditure, body-part discomfort and mental work load among nurses

The purpose of this prospective observational field study was to present a model for measuring energy expenditure among nurses and to determine if there was a difference between the energy expenditure of nurses providing direct care to adult patients on general medical-surgical units in two major metropolitan hospitals and a recommended energy expenditure of 3.0 kcal/minute over 8 hours. One-third of the predicted cycle ergometer VO2max for the study population was used to calculate the recommended energy expenditure.^ Two methods were used to measure energy expenditure among participants during an 8 hour day shift. First, the Energy Expenditure Prediction Program (EEPP) developed by the University of Michigan Center for Ergonomics was used to calculate energy expenditure using activity recordings from observation (OEE; n = 39). The second method used ambulatory electrocardiography and the heart rate-oxygen consumption relationship (HREE; n = 20) to measure energy expenditure. It was concluded that energy expenditure among nurses can be estimated using the EEPP. Using classification systems from previous research, work load among the study population was categorized as "moderate" but was significantly less than (p = 0.021) 3.0 kcal/minute over 8 hours or 1/3 of the predicted VO2max.^ In addition, the relationships between OEE, body-part discomfort (BPCDS) and mental work load (MWI) were evaluated. The relationships between OEE/BPCDS and OEE/MWI were not significant (p = 0.062 and 0.091, respectively). Among the study population, body-part discomfort significantly increased for upper arms, mid-back, lower-back, legs and feet by mid-shift and by the end of the shift, the increase was also significant for neck and thighs.^ The study also provided documentation of a comprehensive list of nursing activities. Among the most important findings were the facts that the study population spent 23% of the workday in a bent posture, walked an average of 3.14 miles, and spent two-thirds of the shift doing activities other than direct patient care, such as paperwork and communicating with other departments. A discussion is provided regarding the ergonomic implications of these findings. ^

The energy expenditure of 2 Holstein cow strains in an organic grazing system

Until recently, measurements of energy expenditure (EE; herein defined as heat production) in respiration chambers did not account for the extra energy requirements of grazing dairy cows on pasture. As energy is first limiting in most pasture-based milk production systems, its efficient use is important. Therefore, the aim of the present study was to compare EE, which can be affected by differences in body weight (BW), body composition, grazing behavior, physical activity, and milk production level, in 2 Holstein cow strains. Twelve Swiss Holstein-Friesian (HCH; 616 kg of BW) and 12 New Zealand Holstein-Friesian (HNZ; 570 kg of BW) cows in the third stage of lactation were paired according to their stage of lactation and kept in a rotational, full-time grazing system without concentrate supplementation. After adaption, the daily milk yield, grass intake using the alkane double-indicator technique, nutrient digestibility, physical activity, and grazing behavior recorded by an automatic jaw movement recorder were investigated over 7d. Using the (13)C bicarbonate dilution technique in combination with an automatic blood sampling system, EE based on measured carbon dioxide production was determined in 1 cow pair per day between 0800 to 1400 h. The HCH were heavier and had a lower body condition score compared with HNZ, but the difference in BW was smaller compared with former studies. Milk production, grass intake, and nutrient digestibility did not differ between the 2 cow strains, but HCH grazed for a longer time during the 6-h measurement period and performed more grazing mastication compared with the HNZ. No difference was found between the 2 cow strains with regard to EE (291 ± 15.6 kJ) per kilogram of metabolic BW, mainly due to a high between-animal variation in EE. As efficiency and energy use are important in sustainable, pasture-based, organic milk production systems, the determining factors for EE, such as methodology, genetics, physical activity, grazing behavior, and pasture quality, should be investigated and quantified in more detail in future studies.