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.

A Separation Principle for the Continuous-Time LQ-Problem With Markovian Jump Parameters

In this paper, we devise a separation principle for the finite horizon quadratic optimal control problem of continuous-time Markovian jump linear systems driven by a Wiener process and with partial observations. We assume that the output variable and the jump parameters are available to the controller. It is desired to design a dynamic Markovian jump controller such that the closed loop system minimizes the quadratic functional cost of the system over a finite horizon period of time. As in the case with no jumps, we show that an optimal controller can be obtained from two coupled Riccati differential equations, one associated to the optimal control problem when the state variable is available, and the other one associated to the optimal filtering problem. This is a separation principle for the finite horizon quadratic optimal control problem for continuous-time Markovian jump linear systems. For the case in which the matrices are all time-invariant we analyze the asymptotic behavior of the solution of the derived interconnected Riccati differential equations to the solution of the associated set of coupled algebraic Riccati equations as well as the mean square stabilizing property of this limiting solution. When there is only one mode of operation our results coincide with the traditional ones for the LQG control of continuous-time linear systems.

Performance results of running parallel applications on the InteGrade

The InteGrade middleware intends to exploit the idle time of computing resources in computer laboratories. In this work we investigate the performance of running parallel applications with communication among processors on the InteGrade grid. As costly communication on a grid can be prohibitive, we explore the so-called systolic or wavefront paradigm to design the parallel algorithms in which no global communication is used. To evaluate the InteGrade middleware we considered three parallel algorithms that solve the matrix chain product problem, the 0-1 Knapsack Problem, and the local sequence alignment problem, respectively. We show that these three applications running under the InteGrade middleware and MPI take slightly more time than the same applications running on a cluster with only LAM-MPI support. The results can be considered promising and the time difference between the two is not substantial. The overhead of the InteGrade middleware is acceptable, in view of the benefits obtained to facilitate the use of grid computing by the user. These benefits include job submission, checkpointing, security, job migration, etc. Copyright (C) 2009 John Wiley & Sons, Ltd.

Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths

This paper deals with the classical one-dimensional integer cutting stock problem, which consists of cutting a set of available stock lengths in order to produce smaller ordered items. This process is carried out in order to optimize a given objective function (e.g., minimizing waste). Our study deals with a case in which there are several stock lengths available in limited quantities. Moreover, we have focused on problems of low demand. Some heuristic methods are proposed in order to obtain an integer solution and compared with others. The heuristic methods are empirically analyzed by solving a set of randomly generated instances and a set of instances from the literature. Concerning the latter. most of the optimal solutions of these instances are known, therefore it was possible to compare the solutions. The proposed methods presented very small objective function value gaps. (C) 2008 Elsevier Ltd. All rights reserved.

A hybrid heuristic for the multi-plant capacitated lot sizing problem with setup carry-over

This paper addresses the capacitated lot sizing problem (CLSP) with a single stage composed of multiple plants, items and periods with setup carry-over among the periods. The CLSP is well studied and many heuristics have been proposed to solve it. Nevertheless, few researches explored the multi-plant capacitated lot sizing problem (MPCLSP), which means that few solution methods were proposed to solve it. Furthermore, to our knowledge, no study of the MPCLSP with setup carry-over was found in the literature. This paper presents a mathematical model and a GRASP (Greedy Randomized Adaptive Search Procedure) with path relinking to the MPCLSP with setup carry-over. This solution method is an extension and adaptation of a previously adopted methodology without the setup carry-over. Computational tests showed that the improvement of the setup carry-over is significant in terms of the solution value with a low increase in computational time.

Lossless filter for multiple repeats with bounded edit distance

Background: Identifying local similarity between two or more sequences, or identifying repeats occurring at least twice in a sequence, is an essential part in the analysis of biological sequences and of their phylogenetic relationship. Finding such fragments while allowing for a certain number of insertions, deletions, and substitutions, is however known to be a computationally expensive task, and consequently exact methods can usually not be applied in practice. Results: The filter TUIUIU that we introduce in this paper provides a possible solution to this problem. It can be used as a preprocessing step to any multiple alignment or repeats inference method, eliminating a possibly large fraction of the input that is guaranteed not to contain any approximate repeat. It consists in the verification of several strong necessary conditions that can be checked in a fast way. We implemented three versions of the filter. The first is simply a straightforward extension to the case of multiple sequences of an application of conditions already existing in the literature. The second uses a stronger condition which, as our results show, enable to filter sensibly more with negligible (if any) additional time. The third version uses an additional condition and pushes the sensibility of the filter even further with a non negligible additional time in many circumstances; our experiments show that it is particularly useful with large error rates. The latter version was applied as a preprocessing of a multiple alignment tool, obtaining an overall time (filter plus alignment) on average 63 and at best 530 times smaller than before (direct alignment), with in most cases a better quality alignment. Conclusion: To the best of our knowledge, TUIUIU is the first filter designed for multiple repeats and for dealing with error rates greater than 10% of the repeats length.

Void fraction measurement and signal analysis from multiple-electrode impedance sensors

Void fraction sensors are important instruments not only for monitoring two-phase flow, but for furnishing an important parameter for obtaining flow map pattern and two-phase flow heat transfer coefficient as well. This work presents the experimental results obtained with the analysis of two axially spaced multiple-electrode impedance sensors tested in an upward air-water two-phase flow in a vertical tube for void fraction measurements. An electronic circuit was developed for signal generation and post-treatment of each sensor signal. By phase shifting the electrodes supplying the signal, it was possible to establish a rotating electric field sweeping across the test section. The fundamental principle of using a multiple-electrode configuration is based on reducing signal sensitivity to the non-uniform cross-section void fraction distribution problem. Static calibration curves were obtained for both sensors, and dynamic signal analyses for bubbly, slug, and turbulent churn flows were carried out. Flow parameters such as Taylor bubble velocity and length were obtained by using cross-correlation techniques. As an application of the void fraction tested, vertical flow pattern identification could be established by using the probability density function technique for void fractions ranging from 0% to nearly 70%.

Multiple cranial burr holes as an alternative treatment for total scalp avulsion

Total scalp avulsion is a devastating injury in clinical practice. It often occurs in female adults, being rare in children. The standard treatment for scalp avulsion is microsurgical replantation, when feasible. Coverage becomes a major problem when replantation fails or is contraindicated, resulting in significant morbidity and requiring multiple procedures. In this article, in addition to reviewing the literature, we report a historical method for obtaining skin coverage after failure of replantation. The authors report a case of a 10-year-old girl who had her scalp totally avulsed by an agricultural machine, including her right auricle. Microsurgery scalp replantation was attempted immediately after fluid resuscitation. The surgery failed probably due to the long time interval between trauma and surgery, which resulted in total ischemic time of 11 h and consequently made vascular microanastomosis impracticable. Multiple trephination of the calvarium was performed in order to expose the diploe. After 4 weeks, granulation tissue from the holes began to cover the defect, allowing the formation of a vascular bed suitable for skin grafting. Total scalp avulsion in children is seldom reported in the literature. Therefore, its management is both difficult and challenging. The exposure of the diploe with multiple burr holes is a safe and effective method for treating this injury. It may be considered, along with skin grafting, a good therapeutic alternative to be used when microsurgical replantation fails or is not feasible.

A coupling cutting stock-lot sizing problem in the paper industry

An important production programming problem arises in paper industries coupling multiple machine scheduling with cutting stocks. Concerning machine scheduling: how can the production of the quantity of large rolls of paper of different types be determined. These rolls are cut to meet demand of items. Scheduling that minimizes setups and production costs may produce rolls which may increase waste in the cutting process. On the other hand, the best number of rolls in the point of view of minimizing waste may lead to high setup costs. In this paper, coupled modeling and heuristic methods are proposed. Computational experiments are presented.

Dor nos dentes e gengivas e fatores associados em adolescentes brasileiros: análise do inquérito nacional de saúde bucal SB-Brasil 2002-2003

Estimou-se a prevalência de dor nos dentes e gengivas e fatores associados em adolescentes brasileiros de 15 a 19 anos de idade. Foram utilizadas informações de 16.126 adolescentes participantes do levantamento epidemiológico nacional de saúde bucal - SB Brasil 2002-2003. O desfecho foi o relato de dor nos dentes e gengivas nos últimos seis meses. As variáveis exploratórias foram: renda per capita, escolaridade, condição de estudo, sexo, cor da pele, idade, localização geográfica da residência, tipo de serviço odontológico utilizado pela última vez, tempo decorrido da última consulta odontológica, índice CPO-D e seus componentes, cálculo dentário e o índice de estética dental. Foram realizadas análises brutas e múltiplas utilizando a regressão de Poisson. A prevalência da dor de dentes e gengivas foi de 35,6% (IC95%: 34,8-36,4). A prevalência de dor foi maior nas meninas, naqueles pertencentes a famílias com baixa renda per capita, nos não estudantes e estudantes de escola pública e naqueles com baixa escolaridade para a idade. Indivíduos que apresentaram altos níveis de cárie e cálculo dentário também apresentaram maiores prevalências do desfecho. A dor nos dentes e gengivas em adolescentes pode ser considerada um problema relevante em saúde pública sugerindo a necessidade de ações preventivas e de promoção da saúde.

Categorization skills and recall in brain damaged children: a multiple case study

During development, children become capable of categorically associating stimuli and of using these relationships for memory recall. Brain damage in childhood can interfere with this development. This study investigated categorical association of stimuli and recall in four children with brain damages. The etiology, topography and timing of the lesions were diverse. Tasks included naming and immediate recall of 30 perceptually and semantically related figures, free sorting, delayed recall, and cued recall of the same material. Traditional neuropsychological tests were also employed. Two children with brain damage sustained in middle childhood relied on perceptual rather than on categorical associations in making associations between figures and showed deficits in delayed or cued recall, in contrast to those with perinatal lesions. One child exhibited normal performance in recall despite categorical association deficits. The present results suggest that brain damaged children show deficits in categorization and recall that are not usually identified in traditional neuropsychological tests.

A closer look at multiple-clone Plasmodium vivax infections: detection methods, prevalence and consequences

The naturally occurring clonal diversity among field isolates of the major human malaria parasite Plasmodium vivax remained unexplored until the early 1990s, when improved molecular methods allowed the use of blood samples obtained directly from patients, without prior in vitro culture, for genotyping purposes. Here we briefly review the molecular strategies currently used to detect genetically distinct clones in patient-derived P. vivax samples, present evidence that multiple-clone P. vivax infections are commonly detected in areas with different levels of malaria transmission and discuss possible evolutionary and epidemiological consequences of the competition between genetically distinct clones in natural human infections. We suggest that, when two or more genetically distinct clones are present in the same host, intra-host competition for limited resources may select for P. vivax traits that represent major public health challenges, such as increased virulence, increased transmissibility and antimalarial drug resistance.

Working memory impairment in multiple sclerosis relapsing-remitting patients with episodic memory deficits

Episodic memory is impaired in multiple sclerosis (MS) patients, possibly because of deficits in working memory (WM) functioning. If so, WM alterations should necessarily be found in patients with episodic memory deficits, but this has not yet been demonstrated. In this study we aimed at determining whether episodic memory deficits in relapsing-remitting MS are found in conjunction with impaired WM. We evaluated 32 MS patients and 32 matched healthy controls. Nineteen of the 32 patients had episodic memory impairment, and as a group only these individuals showed deficits in WM capacity, which may lead to difficulty in encoding, and/or retrieving information from episodic memory.

Search for cytotoxic agents in multiple Laurencia complex seaweed species (Ceramiales, Rhodophyta) harvested from the Atlantic Ocean with emphasis on the Brazilian State of Espírito Santo

The development of new anti-cancer drugs of algal origin represents one of the least explored frontiers in medicinal chemistry. In this regard, the diversity of micro- and macroalgae found in Brazilian coastal waters can be viewed as a largely untapped natural resource. In this report, we describe a comparative study on the cytotoxic properties of extracts obtained from the Laurencia complex: Laurencia aldingensis, L. catarinensis, L. dendroidea, L. intricata, L. translucida, L. sp, and Palisada flagellifera. All of these species were collected in the coastal waters of the State of Espírito Santo, Brazil. Four out of the twelve samples initially investigated were found to show significant levels of toxicity towards a model tumor cell line (human uterine sarcoma, MES-SA). The highest levels of cytotoxicity were typically associated with non-polar (hexane) algal extracts, while the lowest levels of cytotoxicity were found with the corresponding polar (methanol) extracts. In this report, we also describe a biological model currently in development that will not only facilitate the search for new anti-cancer drug candidates of algal origin, but also permit the identification of compounds capable of inducing the destruction of multi-drug resistant tumors with greater efficiency than the pharmaceuticals currently in clinical use.

Mortalidade feminina por hipertensão: análise por causas múltiplas

INTRODUÇÃO: A prevalência da hipertensão arterial vem crescendo no país, constituindo-se em um problema de saúde pública por sua magnitude e dificuldades no controle. OBJETIVO: Avaliar a qualidade dos dados sobre hipertensão como causa de morte e verificar o ganho de informação na mortalidade por hipertensão arterial de mulheres de 10 a 49 anos, por meio da metodologia de análise por causas múltiplas de morte. MATERIAL E MÉTODOS: Foi constituída uma base de dados com 7.332 óbitos ocorridos no primeiro semestre de 2002 pertencentes ao "Estudo da Morbi-Mortalidade de Mulheres de 10 a 49 anos". A metodologia RAMOS (Reproductive Age Mortality Survey) foi aplicada em todas as capitais de Estados brasileiros e Distrito Federal. Com as informações adicionais, foi preenchida uma nova declaração de óbito - DO-NOVA. Foram analisados dois conjuntos de dados (DO-ORIGINAL - antes da investigação - e DO-NOVA - após resgate das informações. Foram realizadas comparações segundo causas básicas e múltiplas por fontes dos dados (DO-O, DO-N). RESULTADOS E CONCLUSÃO: A DO-ORIGINAL apresentou algumas falhas quantitativas e qualitativas. Concluiu-se que a análise por causas múltiplas enriquece a informação, com base nas DO. São necessárias ações contínuas para um melhor preenchimento da DO, pelos médicos, e deve haver mais estudos que adotem a metodologia de causas múltiplas.