An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

A transformational language for mutant description

Mutation testing has been used to assess the quality of test case suites by analyzing the ability in distinguishing the artifact under testing from a set of alternative artifacts, the so-called mutants. The mutants are generated from the artifact under testing by applying a set of mutant operators, which produce artifacts with simple syntactical differences. The mutant operators are usually based on typical errors that occur during the software development and can be related to a fault model. In this paper, we propose a language-named MuDeL (MUtant DEfinition Language)-for the definition of mutant operators, aiming not only at automating the mutant generation, but also at providing precision and formality to the operator definition. The proposed language is based on concepts from transformational and logical programming paradigms, as well as from context-free grammar theory. Denotational semantics formal framework is employed to define the semantics of the MuDeL language. We also describe a system-named mudelgen-developed to support the use of this language. An executable representation of the denotational semantics of the language is used to check the correctness of the implementation of mudelgen. At the very end, a mutant generator module is produced, which can be incorporated into a specific mutant tool/environment. (C) 2008 Elsevier Ltd. All rights reserved.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Three-Dimensional Semiautomatic Road Extraction From a High-Resolution Aerial Image by Dynamic-Programming Optimization in the Object Space

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Binary integer programming formulations for scheduling in market-driven foundries

This paper describes the development and solution of binary integer formulations for production scheduling problems in market-driven foundries. This industrial sector is comprised of small and mid-sized companies with little or no automation, working with diversified production, involving several different metal alloy specifications in small tailor-made product lots. The characteristics and constraints involved in a typical production environment at these industries challenge the formulation of mathematical programming models that can be computationally solved when considering real applications. However, despite the interest on the part of these industries in counting on effective methods for production scheduling, there are few studies available on the subject. The computational tests prove the robustness and feasibility of proposed models in situations analogous to those found in production scheduling at the analyzed industrial sector. (C) 2010 Elsevier Ltd. All rights reserved.

Allocation of protective devices in distribution circuits using nonlinear programming models and genetic algorithms

The optimized allocation of protective devices in strategic points of the circuit improves the quality of the energy supply and the system reliability index. This paper presents a nonlinear integer programming (NLIP) model with binary variables, to deal with the problem of protective device allocation in the main feeder and all branches of an overhead distribution circuit, to improve the reliability index and to provide customers with service of high quality and reliability. The constraints considered in the problem take into account technical and economical limitations, such as coordination problems of serial protective devices, available equipment, the importance of the feeder and the circuit topology. The use of genetic algorithms (GAs) is proposed to solve this problem, using a binary representation that does (1) or does not (0) show allocation of protective devices (reclosers, sectionalizers and fuses) in predefined points of the circuit. Results are presented for a real circuit (134 busses), with the possibility of protective device allocation in 29 points. Also the ability of the algorithm in finding good solutions while improving significantly the indicators of reliability is shown. (C) 2003 Elsevier B.V. All rights reserved.

Interior point algorithm for linear programming used in transmission network synthesis

This article presents a well-known interior point method (IPM) used to solve problems of linear programming that appear as sub-problems in the solution of the long-term transmission network expansion planning problem. The linear programming problem appears when the transportation model is used, and when there is the intention to solve the planning problem using a constructive heuristic algorithm (CHA), ora branch-and-bound algorithm. This paper shows the application of the IPM in a CHA. A good performance of the IPM was obtained, and then it can be used as tool inside algorithm, used to solve the planning problem. Illustrative tests are shown, using electrical systems known in the specialized literature. (C) 2005 Elsevier B.V. All rights reserved.

Utilizando programação orientada a aspectos no projeto de sistemas hardware desenvolvidos com SystemC

New programming language paradigms have commonly been tested and eventually incorporated into hardware description languages. Recently, aspect-oriented programming (AOP) has shown successful in improving the modularity of object-oriented and structured languages such Java, C++ and C. Thus, one can expect that, using AOP, one can improve the understanding of the hardware systems under design, as well as make its components more reusable and easier to maintain. We apply AOP in applications developed using the SystemC library. Several examples will be presented illustrating how to combine AOP and SystemC. During the presentation of these examples, the benefits of this new approach will also be discussed

Determination of the optimal quantity of crop residues for energy in sugarcane crop management using linear programming in variety selection and planting strategy

The aim of this work was to present organizational models for optimizing the reduction of crop residue generated by the sugarcane culture. The first model consisted of the selection of varieties of sugarcane to be planted meeting the mill requirements and, at the same time, to minimize the quantity of residue produced. The second model discussed the use of residue to produce energy. This is related to the selection of variety and quantity to be planted, in order to meet the requirements of the mill, to reduce the quantity of residue, and to maximize as much as possible the energy production. The use of linear programming was proposed. The two models presented similar results in this study, and both may be used to define the varieties and areas to be cultivated. (C) 2001 Published by Elsevier B.V. Ltd.

Design and management optimization of trickle irrigation systems using non-linear programming

A non-linear model is presented which optimizes the lay-out, as well as the design and management of trickle irrigation systems, to achieve maximum net benefit. The model consists of an objective function that maximizes profit at the farm level, subject to appropriate geometric and hydraulic constraints. It can be applied to rectangular shaped fields, with uniform or zero slope. The software used is the Gams-Minos package. The basic inputs are the crop-water-production function, the cost function and cost of system components, and design variables. The main outputs are the annual net benefit and pipe diameters and lengths. To illustrate the capability of the model, a sensitivity analysis of the annual net benefit for a citrus field is evaluated with respect to irrigated area, ground slope, micro-sprinkler discharge and shape of the field. The sensitivity analysis suggests that the greatest benefit is obtained with the smallest microsprinkler discharge, the greatest area, a square field and zero ground slope. The costs of the investment and energy are the components of the objective function that had the greatest effect in the 120 situations evaluated. (C) 1996 Academic Press Limited

The Neuropsychiatric Inventory-Clinician rating scale (NPI-C): Reliability and validity of a revised assessment of neuropsychiatric symptoms in dementia

Background: Neuropsychiatric symptoms (NPS) affect almost all patients with dementia and are a major focus of study and treatment. Accurate assessment of NPS through valid, sensitive and reliable measures is crucial. Although current NPS measures have many strengths, they also have some limitations (e.g. acquisition of data is limited to informants or caregivers as respondents, limited depth of items specific to moderate dementia). Therefore, we developed a revised version of the NPI, known as the NPI-C. The NPI-C includes expanded domains and items, and a clinician-rating methodology. This study evaluated the reliability and convergent validity of the NPI-C at ten international sites (seven languages). Methods: Face validity for 78 new items was obtained through a Delphi panel. A total of 128 dyads (caregivers/patients) from three severity categories of dementia (mild = 58, moderate = 49, severe = 21) were interviewed separately by two trained raters using two rating methods: the original NPI interview and a clinician-rated method. Rater 1 also administered four additional, established measures: the Apathy Evaluation Scale, the Brief Psychiatric Rating Scale, the Cohen-Mansfield Agitation Index, and the Cornell Scale for Depression in Dementia. Intraclass correlations were used to determine inter-rater reliability. Pearson correlations between the four relevant NPI-C domains and their corresponding outside measures were used for convergent validity. Results: Inter-rater reliability was strong for most items. Convergent validity was moderate (apathy and agitation) to strong (hallucinations and delusions; agitation and aberrant vocalization; and depression) for clinician ratings in NPI-C domains. Conclusion: Overall, the NPI-C shows promise as a versatile tool which can accurately measure NPS and which uses a uniform scale system to facilitate data comparisons across studies. Copyright © 2010 International Psychogeriatric Association.