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.

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics. (C) 2009 Elsevier B.V. All rights reserved.

A novel continuous time representation for the scheduling of pipeline systems with pumping yield rate constraints

Pipeline systems play a key role in the petroleum business. These operational systems provide connection between ports and/or oil fields and refineries (upstream), as well as between these and consumer markets (downstream). The purpose of this work is to propose a novel MINLP formulation based on a continuous time representation for the scheduling of multiproduct pipeline systems that must supply multiple consumer markets. Moreover, it also considers that the pipeline operates intermittently and that the pumping costs depend on the booster stations yield rates, which in turn may generate different flow rates. The proposed continuous time representation is compared with a previously developed discrete time representation [Rejowski, R., Jr., & Pinto, J. M. (2004). Efficient MILP formulations and valid cuts for multiproduct pipeline scheduling. Computers and Chemical Engineering, 28, 1511] in terms of solution quality and computational performance. The influence of the number of time intervals that represents the transfer operation is studied and several configurations for the booster stations are tested. Finally, the proposed formulation is applied to a larger case, in which several booster configurations with different numbers of stages are tested. (C) 2007 Elsevier Ltd. All rights reserved.

Optimized harvest scheduling in eucalyptus plantations under operational, spatial and climatic constraints

The representation of sustainability concerns in industrial forests management plans, in relation to environmental, social and economic aspects, involve a great amount of details when analyzing and understanding the interaction among these aspects to reduce possible future impacts. At the tactical and operational planning levels, methods based on generic assumptions usually provide non-realistic solutions, impairing the decision making process. This study is aimed at improving current operational harvesting planning techniques, through the development of a mixed integer goal programming model. This allows the evaluation of different scenarios, subject to environmental and supply constraints, increase of operational capacity, and the spatial consequences of dispatching harvest crews to certain distances over the evaluation period. As a result, a set of performance indicators was selected to evaluate all optimal solutions provided to different possible scenarios and combinations of these scenarios, and to compare these outcomes with the real results observed by the mill in the study case area. Results showed that it is possible to elaborate a linear programming model that adequately represents harvesting limitations, production aspects and environmental and supply constraints. The comparison involving the evaluated scenarios and the real observed results showed the advantage of using more holistic approaches and that it is possible to improve the quality of the planning recommendations using linear programming techniques.

ACCM/PALS haemodynamic support guidelines for paediatric septic shock: an outcomes comparison with and without monitoring central venous oxygen saturation

Introduction: The ACCM/PALS guidelines address early correction of paediatric septic shock using conventional measures. In the evolution of these recommendations, indirect measures of the balance between systemic oxygen delivery and demands using central venous or superior vena cava oxygen saturation ( ScvO(2) >= 70%) in a goal-directed approach have been added. However, while these additional goal-directed endpoints are based on evidence-based adult studies, the extrapolation to the paediatric patient remains unvalidated. Objective: The purpose of this study was to compare treatment according to ACCM/PALS guidelines, performed with and without ScvO(2) goal-directed therapy, on the morbidity and mortality rate of children with severe sepsis and septic shock. Design, participants and interventions: Children and adolescents with severe sepsis or fluid-refractory septic shock were randomly assigned to ACCM/PALS with or without ScvO(2) goal-directed resuscitation. Measurements: Twenty-eight-day mortality was the primary endpoint. Results: Of the 102 enrolled patients, 51 received ACCM/PALS with ScvO(2) goal-directed therapy and 51 received ACCM/PALS without ScvO(2) goal-directed therapy. ScvO(2) goal-directed therapy resulted in less mortality ( 28-day mortality 11.8% vs. 39.2%, p = 0.002), and fewer new organ dysfunctions ( p = 0.03). ScvO(2) goal-directed therapy resulted in more crystalloid ( 28 ( 20-40) vs. 5 ( 0-20) ml/kg, p < 0.0001), blood transfusion ( 45.1% vs. 15.7%, p = 0.002) and inotropic ( 29.4% vs. 7.8%, p = 0.01) support in the first 6 h. Conclusions: This study supports the current ACCM/PALS guidelines. Goal-directed therapy using the endpoint of a ScvO(2) = 70% has a significant and additive impact on the outcome of children and adolescents with septic shock.

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

On the cutting stock problem under stochastic demand

This paper addresses the one-dimensional cutting stock problem when demand is a random variable. The problem is formulated as a two-stage stochastic nonlinear program with recourse. The first stage decision variables are the number of objects to be cut according to a cutting pattern. The second stage decision variables are the number of holding or backordering items due to the decisions made in the first stage. The problem`s objective is to minimize the total expected cost incurred in both stages, due to waste and holding or backordering penalties. A Simplex-based method with column generation is proposed for solving a linear relaxation of the resulting optimization problem. The proposed method is evaluated by using two well-known measures of uncertainty effects in stochastic programming: the value of stochastic solution-VSS-and the expected value of perfect information-EVPI. The optimal two-stage solution is shown to be more effective than the alternative wait-and-see and expected value approaches, even under small variations in the parameters of the problem.

A systemic approach for optimal cooling tower operation

The thermal performance of a cooling tower and its cooling water system is critical for industrial plants, and small deviations from the design conditions may cause severe instability in the operation and economics of the process. External disturbances such as variation in the thermal demand of the process or oscillations in atmospheric conditions may be suppressed in multiple ways. Nevertheless, such alternatives are hardly ever implemented in the industrial operation due to the poor coordination between the utility and process sectors. The complexity of the operation increases because of the strong interaction among the process variables. In the present work, an integrated model for the minimization of the operating costs of a cooling water system is developed. The system is composed of a cooling tower as well as a network of heat exchangers. After the model is verified, several cases are studied with the objective of determining the optimal operation. It is observed that the most important operational resources to mitigate disturbances in the thermal demand of the process are, in this order: the increase in recycle water flow rate, the increase in air flow rate and finally the forced removal of a portion of the water flow rate that enters the cooling tower with the corresponding make-up flow rate. (C) 2009 Elsevier Ltd. All rights reserved.

Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming

This paper addresses the non-preemptive single machine scheduling problem to minimize total tardiness. We are interested in the online version of this problem, where orders arrive at the system at random times. Jobs have to be scheduled without knowledge of what jobs will come afterwards. The processing times and the due dates become known when the order is placed. The order release date occurs only at the beginning of periodic intervals. A customized approximate dynamic programming method is introduced for this problem. The authors also present numerical experiments that assess the reliability of the new approach and show that it performs better than a myopic policy.

THE VANISHING DISCOUNT APPROACH FOR THE AVERAGE CONTINUOUS CONTROL OF PIECEWISE DETERMINISTIC MARKOV PROCESSES

This work is concerned with the existence of an optimal control strategy for the long-run average continuous control problem of piecewise-deterministic Markov processes (PDMPs). In Costa and Dufour (2008), sufficient conditions were derived to ensure the existence of an optimal control by using the vanishing discount approach. These conditions were mainly expressed in terms of the relative difference of the alpha-discount value functions. The main goal of this paper is to derive tractable conditions directly related to the primitive data of the PDMP to ensure the existence of an optimal control. The present work can be seen as a continuation of the results derived in Costa and Dufour (2008). Our main assumptions are written in terms of some integro-differential inequalities related to the so-called expected growth condition, and geometric convergence of the post-jump location kernel associated to the PDMP. An example based on the capacity expansion problem is presented, illustrating the possible applications of the results developed in the paper.

Three-dimensional electrical impedance, tomography: A topology optimization approach

Electrical impedance tomography is a technique to estimate the impedance distribution within a domain, based on measurements on its boundary. In other words, given the mathematical model of the domain, its geometry and boundary conditions, a nonlinear inverse problem of estimating the electric impedance distribution can be solved. Several impedance estimation algorithms have been proposed to solve this problem. In this paper, we present a three-dimensional algorithm, based on the topology optimization method, as an alternative. A sequence of linear programming problems, allowing for constraints, is solved utilizing this method. In each iteration, the finite element method provides the electric potential field within the model of the domain. An electrode model is also proposed (thus, increasing the accuracy of the finite element results). The algorithm is tested using numerically simulated data and also experimental data, and absolute resistivity values are obtained. These results, corresponding to phantoms with two different conductive materials, exhibit relatively well-defined boundaries between them, and show that this is a practical and potentially useful technique to be applied to monitor lung aeration, including the possibility of imaging a pneumothorax.

Surgical management of glomus jugulare tumors: a proposal for approach selection based on tumor relationships with the facial nerve Clinical article

Object. The goal of this paper is to analyze the extension and relationships of glomus jugulare tumor with the temporal bone and the results of its surgical treatment aiming at preservation of the facial nerve. Based on the tumor extension and its relationships with the facial nerve, new criteria to be used in the selection of different surgical approaches are proposed. Methods. Between December 1997 and December 2007, 34 patients (22 female and 12 male) with glomus jugulare tumors were treated. Their mean age was 48 years. The mean follow-up was 52.5 months. Clinical findings included hearing loss in 88%, swallowing disturbance in 50%, and facial nerve palsy in 41%. Magnetic resonance imaging demonstrated a mass in the jugular foramen in all cases, a mass in the middle ear in 97%, a cervical mass in 85%, and an intradural mass in 41%. The tumor was supplied by the external carotid artery in all cases, the internal carotid artery in 44%, and the vertebral artery in 32%. Preoperative embolization was performed in 15 cases. The approach was tailored to each patient, and 4 types of approaches were designed. The infralabyrinthine retrofacial approach (Type A) was used in 32.5%; infralabyrinthine pre- and retrofacial approach without occlusion of the external acoustic meatus (Type B) in 20.5%; infralabyrinthine pre- and retrofacial approach with occlusion of the external acoustic meatus (Type C) in 41 W. and the infralabyrinthine approach with transposition of the facial nerve and removal of the middle ear structures (Type D) in 6% of the patients. Results. Radical removal was achieved in 91% of the cases and partial removal in 9%. Among 20 patients without preoperative facial nerve dysfunction, the nerve was kept in anatomical position in 19 (95%), and facial nerve function was normal during the immediate postoperative period in 17 (85%). Six patients (17.6%) had a new lower cranial nerve deficit, but recovery of swallowing function was adequate in all cases. Voice disturbance remained in all 6 cases. Cerebrospinal fluid leakage occurred in 6 patients (17.6%), with no need for reoperation in any of them. One patient died in the postoperative period due to pulmonary complications. The global recovery, based on the Karnofsky Performance Scale (KPS), was 100% in 15% of the patients, 90% in 45%, 80% in 33%, and 70% in 6%. Conclusions. Radical removal of glomus jugulare tumor can be achieved without anterior transposition of the facial nerve. The extension of dissection, however, should be tailored to each case based on tumor blood supply, preoperative symptoms, and tumor extension. The operative field provided by the retrofacial infralabyrinthine approach, or the pre- and retrofacial approaches. with or without Closure of the external acoustic meatus, allows a wide exposure of the jugular foramen area. Global functional recovery based on the KPS is acceptable in 94% of the patients. (DOI: 10.3171/2008.10.JNS08612)

A hands-on approach for fitting long-term survival models under the GAMLSS framework

In many data sets from clinical studies there are patients insusceptible to the occurrence of the event of interest. Survival models which ignore this fact are generally inadequate. The main goal of this paper is to describe an application of the generalized additive models for location, scale, and shape (GAMLSS) framework to the fitting of long-term survival models. in this work the number of competing causes of the event of interest follows the negative binomial distribution. In this way, some well known models found in the literature are characterized as particular cases of our proposal. The model is conveniently parameterized in terms of the cured fraction, which is then linked to covariates. We explore the use of the gamlss package in R as a powerful tool for inference in long-term survival models. The procedure is illustrated with a numerical example. (C) 2009 Elsevier Ireland Ltd. All rights reserved.

An approach for solving the lot-sizing problem of a market-driven foundry

Foundries can be found all over Brazil and they are very important to its economy. In 2008, a mixed integer-programming model for small market-driven foundries was published, attempting to minimize delivery delays. We undertook a study of that model. Here, we present a new approach based on the decomposition of the problem into two sub-problems: production planning of alloys and production planning of items. Both sub-problems are solved using a Lagrangian heuristic based on transferences. An important aspect of the proposed heuristic is its ability to take into account a secondary practice objective solution: the furnace waste. Computational tests show that the approach proposed here is able to generate good quality solutions that outperform prior results. Journal of the Operational Research Society (2010) 61, 108-114. doi:10.1057/jors.2008.151

A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem

Industrial production processes involving both lot-sizing and cutting stock problems are common in many industrial settings. However, they are usually treated in a separate way, which could lead to costly production plans. In this paper, a coupled mathematical model is formulated and a heuristic method based on Lagrangian relaxation is proposed. Computational results prove its effectiveness. (C) 2009 Elsevier B.V. All rights reserved.