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.

DISTRIBUTED APPROACH FOR SOLVING OPTIMAL POWER FLOW PROBLEMS IN THREE-PHASE UNBALANCED DISTRIBUTION NETWORK

The objective of this report is to study distributed (decentralized) three phase optimal power flow (OPF) problem in unbalanced power distribution networks. A full three phase representation of the distribution networks is considered to account for the highly unbalance state of the distribution networks. All distribution network’s series/shunt components, and load types/combinations had been modeled on commercial version of General Algebraic Modeling System (GAMS), the high-level modeling system for mathematical programming and optimization. The OPF problem has been successfully implemented and solved in a centralized approach and distributed approach, where the objective is to minimize the active power losses in the entire system. The study was implemented on the IEEE-37 Node Test Feeder. A detailed discussion of all problem sides and aspects starting from the basics has been provided in this study. Full simulation results have been provided at the end of the report.

An MILP-based heuristic for staff scheduling problems with acceptance levels

We present a real-world staff-assignment problem that was reported to us by a provider of an online workforce scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of requirements related to work laws, work shift compatibility, workload balancing, and personal preferences of employees. A target value is given for each requirement, and all possible deviations from these values are associated with acceptance levels. The objective is to minimize the total number of deviations in ascending order of the acceptance levels. We present an exact lexicographic goal programming MILP formulation and an MILP-based heuristic. The heuristic consists of two phases: in the first phase a feasible schedule is built and in the second phase parts of the schedule are iteratively re-optimized by applying an exact MILP model. A major advantage of such MILP-based approaches is the flexibility to account for additional constraints or modified planning objectives, which is important as the requirements may vary depending on the company or planning period. The applicability of the heuristic is demonstrated for a test set derived from real-world data. Our computational results indicate that the heuristic is able to devise optimal solutions to non-trivial problem instances, and outperforms the exact lexicographic goal programming formulation on medium- and large-sized problem instances.

SOMS: SurrOgate MultiStart algorithm for use with nonlinear programming for global optimization

SOMS is a general surrogate-based multistart algorithm, which is used in combination with any local optimizer to find global optima for computationally expensive functions with multiple local minima. SOMS differs from previous multistart methods in that a surrogate approximation is used by the multistart algorithm to help reduce the number of function evaluations necessary to identify the most promising points from which to start each nonlinear programming local search. SOMS’s numerical results are compared with four well-known methods, namely, Multi-Level Single Linkage (MLSL), MATLAB’s MultiStart, MATLAB’s GlobalSearch, and GLOBAL. In addition, we propose a class of wavy test functions that mimic the wavy nature of objective functions arising in many black-box simulations. Extensive comparisons of algorithms on the wavy testfunctions and on earlier standard global-optimization test functions are done for a total of 19 different test problems. The numerical results indicate that SOMS performs favorably in comparison to alternative methods and does especially well on wavy functions when the number of function evaluations allowed is limited.

Food advertisements during children's television programming in 2007: Comparison with ads in 1994 and the 2005 dietary recommendations

Childhood overweight and obesity are two major public health problems that are of economic and medical concern in the world today (Lobstein, Baur, & Uauy, 2004). Overweight conditions in childhood are important because they are widely prevalent, serious, and carry lifetime consequences for health and well being (Lobstein et al., 2004). Several studies have shown an association between television viewing and obesity in all age groups (Caroli, Argentieri, Cardone, & Masi, 2004; Harper, 2006; Vandewater & Huang, 2006; Wiecha et al., 2006). One mechanism that potentially links television viewing to childhood obesity is food advertising (Story, 2003). ^ The purpose of this study was to examine the types of foods advertised on children's television programming and to determine if there have been any changes in the number and types of commercials over the last 13 years. In addition, the food content of the advertisements was compared to the 2005 Dietary Guidelines to determine if the foods targeted were consistent with the current recommendations. Finally, each television network was analyzed individually to determine any differences between advertising on cable and regular programming. ^ A descriptive analysis was conducted on the most commonly advertised commercials during children's television programming on Saturday morning from 7 a.m. to 10:30 a.m. A total of 10 major television networks were viewed on three different Saturday mornings during June and July 2007. Commercial advertising accounted for approximately 19% of children's total viewing time. Of the 3,185 commercials, 28.5% were for foods, 67.7% were for non-food items, and 3.8% were PSAs. On average, there were 30 commercial advertisements and PSAs per hour, of which approximately nine were for food. ^ Of the 907 food advertisements, 72.0% were for foods classified in the fats, oils, and sugar group. The next largest group (17.3%) was for restaurant food of which 15.3% were for unhealthy/fast food restaurant fare. The most frequently advertised food product on Saturday morning television was regular cereal, accounting for 43.9% of all food advertisements. ^ Cable and regular programming stations varied slightly in the amount, length, and category of commercials. Cable television had about 50% less commercials and PSAs (1098) than regular programming (2087), but only had approximately 150 minutes less total commercial and PSA time; therefore, cable, in general, had longer commercials than regular programming. Overall, cable programming had more advertisements encouraging increased physical activity and positive nutrition behavior with less commercials focusing on the fats, oils, and sugar groups, compared to regular programming. ^ During the last 13 years, food advertisements have not improved, despite the recent IOM report on marketing foods to children (Institute of Medicine-Committee on Food Marketing and the Diets of Children and Youth, 2005), although the frequency of food advertisements has improved slightly. Children are now viewing an average of one food advertisement every 7 minutes, compared to one food advertisement every 5 minutes in 1994 (Kotz & Story, 1994). Therefore, manufacturers are putting a greater emphasis on advertising other products to children. Despite the recent attention to the issue of marketing unhealthy foods to children through television advertisements, not much progress has been noted since 1994. Further advocacy and regulatory issues concerning the content of advertisements during Saturday morning TV need to be explored. ^

Ethnographic and epidemiologic approaches for the programming of prenatal and birth services in Mesa los Hornos, Mexico

The investigator conducted an action-oriented investigation of pregnancy and birth among the women of Mesa los Hornos, an urban squatter slum in Mexico City. Three aims guided the project: (1) To obtain information for improving prenatal and maternity service utilization; (2) To examine the utility of rapid ethnographic and epidemiologic assessment methodologies; (3) To cultivate community involvement in health development.^ Viewing service utilization as a culturally-bound decision, the study included a qualitative phase to explore women's cognition of pregnancy and birth, their perceived needs during pregnancy, and their criteria of service acceptability. A probability-based community survey delineated parameters of service utilization and pregnancy health events, and probed reasons for decisions to use medical services, lay midwives, or other sources of prenatal and labor and delivery assistance. Qualitative survey of service providers at relevant clinics, hospitals, and practices contributed information on service availability and access, and on coordination among private, social security, and public assistance health service sectors. The ethnographic approach to exploring the rationale for use or non-use of services provided a necessary complement to conventional barrier-based assessment, to inform planning of culturally appropriate interventions.^ Information collection and interpretation was conducted under the aegis of an advisory committee of community residents and service agency representatives; the residents' committee formulated recommendations for action based on findings, and forwarded the mandate to governmental social and urban development offices. Recommendations were designed to inform and develop community participation in health care decision-making.^ Rapid research methods are powerful tools for achieving community-based empowerment toward investigation and resolution of local health problems. But while ethnography works well in synergy with quantitative assessment approaches to strengthen the validity and richness of short-term field work, the author strongly urges caution in application of Rapid Ethnographic Assessments. An ethnographic sensibility is essential to the research enterprise for the development of an active and cooperative community base, the design and use of quantitative instruments, the appropriate use of qualitative techniques, and the interpretation of culturally-oriented information. However, prescribed and standardized Rapid Ethnographic Assessment techniques are counter-productive if used as research short-cuts before locale- and subject-specific cultural understanding is achieved. ^

Engaging stakeholders in community-level obesity prevention programming: Evaluation of the Fit Family Challenge

Introduction: Both a systems approach to change and a focus on multi-sector interventions ensures obesity prevention programming within the community is equitable, sustainable, and cost-effective. An authentic community engagement approach is required to implement interventions guided by best-evidence research and practice. Although there are examples illustrating the benefits of community engagement, there is no standardized method to implement it. The San Antonio Sports Foundation (SA Sports), a non-profit community-based organization, implements a variety of free events and programs promoting active life styles. One such program is the Fit Family Challenge which is a summer-long program implemented at the school level targeted at families. ^ Aims: This thesis was a culmination of the experience from the student collaborating with SA Sports as part of a practicum opportunity. Using secondary data collected by the Fit Family Challenge during the 2011 year, the goals of this thesis were: to assess individual changes; evaluate short-term impact; and describe the community engagement process. ^ Methods: SA Sports collected quantitative and qualitative data during the implementation and evaluation of the FFC program. SA Sports allowed the used of de-identified data to be analyzed to study the aims of this thesis. ^ Results: The program was able to provide families with the knowledge, information, and opportunity to exercise as a family and cook healthier meals. School district coordinators were generally satisfied and illustrated the benefits of a community partnership. An authentic community engagement was present highlighting the importance of communication, collaboration and the sustainability of such partnerships in the community. ^ Conclusion: The success of an obesity program should focus on triggers that initiate behavioral change rather than physiological changes. The evaluation was guided by a community engagement approach, which illustrated the development of new partnerships and the strengthening of other collaborations. Ultimately, the engagement approach empowered the community to identify their own problems and build collaboration, rather than tackling obesity prevention alone. ^

An example of integration between en economic and an hydrologic model in the framework of water resource management problems

Growing scarcity, increasing demand and bad management of water resources are causing weighty competition for water and consequently managers are facing more and more pressure in an attempt to satisfy users? requirement. In many regions agriculture is one of the most important users at river basin scale since it concentrates high volumes of water consumption during relatively short periods (irrigation season), with a significant economic, social and environmental impact. The interdisciplinary characteristics of related water resources problems require, as established in the Water Framework Directive 2000/60/EC, an integrated and participative approach to water management and assigns an essential role to economic analysis as a decision support tool. For this reason, a methodology is developed to analyse the economic and environmental implications of water resource management under different scenarios, with a focus on the agricultural sector. This research integrates both economic and hydrologic components in modelling, defining scenarios of water resource management with the goal of preventing critical situations, such as droughts. The model follows the Positive Mathematical Programming (PMP) approach, an innovative methodology successfully used for agricultural policy analysis in the last decade and also applied in several analyses regarding water use in agriculture. This approach has, among others, the very important capability of perfectly calibrating the baseline scenario using a very limited database. However one important disadvantage is its limited capacity to simulate activities non-observed during the reference period but which could be adopted if the scenario changed. To overcome this problem the classical methodology is extended in order to simulate a more realistic farmers? response to new agricultural policies or modified water availability. In this way an economic model has been developed to reproduce the farmers? behaviour within two irrigation districts in the Tiber High Valley. This economic model is then integrated with SIMBAT, an hydrologic model developed for the Tiber basin which allows to simulate the balance between the water volumes available at the Montedoglio dam and the water volumes required by the various irrigation users.

Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming

Irregular computations pose sorne of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures, which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. Starting in the mid 80s there has been significant progress in the development of parallelizing compilers for logic pro­gramming (and more recently, constraint programming) resulting in quite capable paralle­lizers. The typical applications of these paradigms frequently involve irregular computations, and make heavy use of dynamic data structures with pointers, since logical variables represent in practice a well-behaved form of pointers. This arguably makes the techniques used in these compilers potentially interesting. In this paper, we introduce in a tutoríal way, sorne of the problems faced by parallelizing compilers for logic and constraint programs and provide pointers to sorne of the significant progress made in the area. In particular, this work has resulted in a series of achievements in the areas of inter-procedural pointer aliasing analysis for independence detection, cost models and cost analysis, cactus-stack memory management, techniques for managing speculative and irregular computations through task granularity control and dynamic task allocation such as work-stealing schedulers), etc.

Detecting Traffic Problems with ILP

Expert systems for decision support have recently been successfully introduced in road transport management. In this paper, we apply three state-of-the art ILP systems to learn how to detect traffic problems.

Some techniques for automated, resource-aware distributed and mobile computing in a multi-paradigm programming system

Distributed parallel execution systems speed up applications by splitting tasks into processes whose execution is assigned to different receiving nodes in a high-bandwidth network. On the distributing side, a fundamental problem is grouping and scheduling such tasks such that each one involves sufñcient computational cost when compared to the task creation and communication costs and other such practical overheads. On the receiving side, an important issue is to have some assurance of the correctness and characteristics of the code received and also of the kind of load the particular task is going to pose, which can be specified by means of certificates. In this paper we present in a tutorial way a number of general solutions to these problems, and illustrate them through their implementation in the Ciao multi-paradigm language and program development environment. This system includes facilities for parallel and distributed execution, an assertion language for specifying complex programs properties (including safety and resource-related properties), and compile-time and run-time tools for performing automated parallelization and resource control, as well as certification of programs with resource consumption assurances and efñcient checking of such certificates.

Automatic parallelization of irregular and pointer-based computations: perspectives from logic and constraint programming

Irregular computations pose some of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. In the past decade there has been significant progress in the development of parallelizing compilers for logic programming and, more recently, constraint programming. The typical applications of these paradigms frequently involve irregular computations, which arguably makes the techniques used in these compilers potentially interesting. In this paper we introduce in a tutorial way some of the problems faced by parallelizing compilers for logic and constraint programs. These include the need for inter-procedural pointer aliasing analysis for independence detection and having to manage speculative and irregular computations through task granularity control and dynamic task allocation. We also provide pointers to some of the progress made in these áreas. In the associated talk we demónstrate representatives of several generations of these parallelizing compilers.

The role of computational logic as a hinge paradigm among deduction, problem solving, programming, and parallelism

This paper presents some brief considerations on the role of Computational Logic in the construction of Artificial Intelligence systems and in programming in general. It does not address how the many problems in AI can be solved but, rather more modestly, tries to point out some advantages of Computational Logic as a tool for the AI scientist in his quest. It addresses the interaction between declarative and procedural views of programs (deduction and action), the impact of the intrinsic limitations of logic, the relationship with other apparently competing computational paradigms, and finally discusses implementation-related issues, such as the efficiency of current implementations and their capability for efficiently exploiting existing and future sequential and parallel hardware. The purpose of the discussion is in no way to present Computational Logic as the unique overall vehicle for the development of intelligent systems (in the firm belief that such a panacea is yet to be found) but rather to stress its strengths in providing reasonable solutions to several aspects of the task.

A dynamic programming approach to the formulation and solution of finite element equations

A method for formulating and algorithmically solving the equations of finite element problems is presented. The method starts with a parametric partition of the domain in juxtaposed strips that permits sweeping the whole region by a sequential addition (or removal) of adjacent strips. The solution of the difference equations constructed over that grid proceeds along with the addition removal of strips in a manner resembling the transfer matrix approach, except that different rules of composition that lead to numerically stable algorithms are used for the stiffness matrices of the strips. Dynamic programming and invariant imbedding ideas underlie the construction of such rules of composition. Among other features of interest, the present methodology provides to some extent the analyst's control over the type and quantity of data to be computed. In particular, the one-sweep method presented in Section 9, with no apparent counterpart in standard methods, appears to be very efficient insofar as time and storage is concerned. The paper ends with the presentation of a numerical example

A Fuzzy approach based on dynamic programming and metaheuristics for selecting safeguards for risk management for information systems

In this paper we focus on the selection of safeguards in a fuzzy risk analysis and management methodology for information systems (IS). Assets are connected by dependency relationships, and a failure of one asset may affect other assets. After computing impact and risk indicators associated with previously identified threats, we identify and apply safeguards to reduce risks in the IS by minimizing the transmission probabilities of failures throughout the asset network. However, as safeguards have associated costs, the aim is to select the safeguards that minimize costs while keeping the risk within acceptable levels. To do this, we propose a dynamic programming-based method that incorporates simulated annealing to tackle optimizations problems.