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.

Designing Novel Antitrypanosomal Agents from a Mixed Graph-Theoretical Substructural Approach

Chagas disease is nowadays the most serious parasitic health problem. This disease is caused by Trypanosoma cruzi. The great number of deaths and the insufficient effectiveness of drugs against this parasite have alarmed the scientific community worldwide. In an attempt to overcome this problem, a model for the design and prediction of new antitrypanosomal agents was obtained. This used a mixed approach, containing simple descriptors based on fragments and topological substructural molecular design descriptors. A data set was made up of 188 compounds, 99 of them characterized an antitrypanosomal activity and 88 compounds that belong to other pharmaceutical categories. The model showed sensitivity, specificity and accuracy values above 85%. Quantitative fragmental contributions were also calculated. Then, and to confirm the quality of the model, 15 structures of molecules tested as antitrypanosomal compounds (that we did not include in this study) were predicted, taking into account the information on the abovementioned calculated fragmental contributions. The model showed an accuracy of 100% which means that the ""in silico"" methodology developed by our team is promising for the rational design of new antitrypanosomal drugs. (C) 2009 Wiley Periodicals, Inc. J Comput Chem 31: 882-894. 2010

An oracle approach for interaction neighborhood estimation in random fields

We consider the problem of interaction neighborhood estimation from the partial observation of a finite number of realizations of a random field. We introduce a model selection rule to choose estimators of conditional probabilities among natural candidates. Our main result is an oracle inequality satisfied by the resulting estimator. We use then this selection rule in a two-step procedure to evaluate the interacting neighborhoods. The selection rule selects a small prior set of possible interacting points and a cutting step remove from this prior set the irrelevant points. We also prove that the Ising models satisfy the assumptions of the main theorems, without restrictions on the temperature, on the structure of the interacting graph or on the range of the interactions. It provides therefore a large class of applications for our results. We give a computationally efficient procedure in these models. We finally show the practical efficiency of our approach in a simulation study.

A pointcut-based coverage analysis approach for aspect-oriented programs

Aspect-oriented programming (AOP) is a promising technology that supports separation of crosscutting concerns (i.e., functionality that tends to be tangled with, and scattered through the rest of the system). In AOP, a method-like construct named advice is applied to join points in the system through a special construct named pointcut. This mechanism supports the modularization of crosscutting behavior; however, since the added interactions are not explicit in the source code, it is hard to ensure their correctness. To tackle this problem, this paper presents a rigorous coverage analysis approach to ensure exercising the logic of each advice - statements, branches, and def-use pairs - at each affected join point. To make this analysis possible, a structural model based on Java bytecode - called PointCut-based Del-Use Graph (PCDU) - is proposed, along with three integration testing criteria. Theoretical, empirical, and exploratory studies involving 12 aspect-oriented programs and several fault examples present evidence of the feasibility and effectiveness of the proposed approach. (C) 2010 Elsevier Inc. All rights reserved.

A complex network approach to text summarization

Automatic summarization of texts is now crucial for several information retrieval tasks owing to the huge amount of information available in digital media, which has increased the demand for simple, language-independent extractive summarization strategies. In this paper, we employ concepts and metrics of complex networks to select sentences for an extractive summary. The graph or network representing one piece of text consists of nodes corresponding to sentences, while edges connect sentences that share common meaningful nouns. Because various metrics could be used, we developed a set of 14 summarizers, generically referred to as CN-Summ, employing network concepts such as node degree, length of shortest paths, d-rings and k-cores. An additional summarizer was created which selects the highest ranked sentences in the 14 systems, as in a voting system. When applied to a corpus of Brazilian Portuguese texts, some CN-Summ versions performed better than summarizers that do not employ deep linguistic knowledge, with results comparable to state-of-the-art summarizers based on expensive linguistic resources. The use of complex networks to represent texts appears therefore as suitable for automatic summarization, consistent with the belief that the metrics of such networks may capture important text features. (c) 2008 Elsevier Inc. All rights reserved.

Design of novel antituberculosis compounds using graph-theoretical and substructural approaches

The increasing resistance of Mycobacterium tuberculosis to the existing drugs has alarmed the worldwide scientific community. In an attempt to overcome this problem, two models for the design and prediction of new antituberculosis agents were obtained. The first used a mixed approach, containing descriptors based on fragments and the topological substructural molecular design approach (TOPS-MODE) descriptors. The other model used a combination of two-dimensional (2D) and three-dimensional (3D) descriptors. A data set of 167 compounds with great structural variability, 72 of them antituberculosis agents and 95 compounds belonging to other pharmaceutical categories, was analyzed. The first model showed sensitivity, specificity, and accuracy values above 80% and the second one showed values higher than 75% for these statistical indices. Subsequently, 12 structures of imidazoles not included in this study were designed, taking into account the two models. In both cases accuracy was 100%, showing that the methodology in silico developed by us is promising for the rational design of antituberculosis drugs.

A multi-screening approach for marine-derived fungal metabolites and the isolation of cyclodepsipeptides from Beauveria felina

Extracts obtained from 57 marine-derived fungal strains were analyzed by HPLC-PDA, TLC and ¹H NMR. The analyses showed that the growth conditions affected the chemical profile of crude extracts. Furthermore, the majority of fungal strains which produced either bioactive of chemically distinctive crude extracts have been isolated from sediments or marine algae. The chemical investigation of the antimycobacterial and cytotoxic crude extract obtained from two strains of the fungus Beauveria felina have yielded cyclodepsipeptides related to destruxins. The present approach constitutes a valuable tool for the selection of fungal strains that produce chemically interesting or biologically active secondary metabolites.

Rat pinealectomy: a modified direct visual approach

PURPOSE: To report a new, direct visual approach for rat pinealectomy. METHODS: Eighty adult female rats (Rattus norvegicus albinus EPM-1 strain) were weighted and anesthetized intraperitoneally with 15 mg/kg xylazine and 30 mg/kg ketamine. The animal was fastened to a dissection table, an incision was made in the skin and the subcutaneous tissue, bringing the lambda into view. The skullcap was opened with a dental drill, bringing the cerebral hemispheres and the superior sagittal sinus into view. The pineal gland, located under the venous sinus, was removed in a single piece using tweezers. Next, the bone fragment was returned to its place and the surgical layers were sutured. RESULTS: This new technique is easy to be done, avoids bleedings and removes only the pineal gland without damage to the remaining encephalon. In addition it makes possible the achievement of a sham surgery, allowing the pineal gland to remain intact. CONCLUSION: The proposed technique intends to facilitate studies aiming to better understanding the complexity and importance of the pineal gland on reproductive and other body systems.

STM probing of local oscillations of the Fano-Kondo effect: a Doniach-Sunjic approach for the Kondo peak

The use of the scanning tunneling microscope (STM) for the investigation of Kondo adatoms on normal metallic surfaces reveals a Fano-Kondo behavior of the conductance as a function of the tip bias. In this work, the Doniach-Sunjic expression is used to describe the Kondo peak and we analyze the effect of a complex Fano phase, arising from an external magnetic field, on the conductance pattern. It is demonstrated that such phase generates local oscillations of the Fano-Kondo line shape and can lead to the suppression of anti-resonances.

Air pollution and hospital admissions for respiratory diseases in the subequatorial Amazon: a time series approach

The objective of the study is to evaluate the effect of the daily variation in concentrations of fine particulate matter (diameter less than 2.5µm - PM2.5) resulting from the burning of biomass on the daily number of hospitalizations of children and elderly people for respiratory diseases, in Alta Floresta and Tangará da Serra in the Brazilian Amazon in 2005. This is an ecological time series study that uses data on daily number of hospitalizations of children and the elderly for respiratory diseases, and estimated concentration of PM2.5. In Alta Floresta, the percentage increases in the relative risk (%RR) of hospitalization for respiratory diseases in children were significant for the whole year and for the dry season with 3-4 day lags. In the dry season these measurements reach 6% (95%CI: 1.4-10.8). The associations were sig-nificant for moving averages of 3-5 days. The %RR for the elderly was significant for the current day of the drought, with a 6.8% increase (95%CI: 0.5-13.5) for each additional 10µg/m3 of PM2.5. No as-sociations were verified for Tangara da Serra. The PM2.5 from the burning of biomass increased hospitalizations for respiratory diseases in children and the elderly.

Anthropogenic influences in a lagoonal environment: a multiproxy approach at the valo grande mouth, Cananéia-Iguape system (SE Brazil)

The Cananéia-Iguape system, SE Brazil, consists of a complex of lagoonal channels, located in a United Nations Educational, Scientific and Cultural Organization (UNESCO) Biosphere Reserve. Nevertheless, important environmental changes have occurred in approximately the last 150 yrs due to the opening of an artificial channel, the Valo Grande, connecting the Ribeira de Iguape River to the lagoonal system. Our objective is to assess the historical record of the uppermost layers of the sedimentary column of the lagoonal system in order to determine the history of environmental changes caused by the opening of the artificial channel. In this sense, an integrated geochemical-faunal approach is used. The environmental changes led significant modifications in salinity, in changes of the depositional patterns of sediments and foraminiferal assemblages (including periods of defaunation), and, more drastically, in the input of heavy metals to the coastal environment. The concentrations Pb in the core analyzed here were up to two times higher than the values measured in contaminated sediments from the Santos estuary, the most industrialized coastal zone in Brazil.

The bubbles or the boiling pot?: an ecosystemic approach to culture, environment and quality of life

For the diagnosis and prognosis of the problems of quality of life, a multidisciplinary ecosystemic approach encompasses four dimensions of being-in-the-world, as donors and recipients: intimate, interactive, social and biophysical. Social, cultural and environmental vulnerabilities are understood and dealt with, in different circumstances of space and time, as the conjugated effect of all dimensions of being-in-the-world, as they induce the events (deficits and assets), cope with consequences (desired or undesired) and contribute for change. Instead of fragmented and reduced representations of reality, diagnosis and prognosis of cultural, educational, environmental and health problems considers the connections (assets) and ruptures (deficits) between the different dimensions, providing a planning model to develop and evaluate research, teaching programmes, public policies and field projects. The methodology is participatory, experiential and reflexive; heuristic-hermeneutic processes unveil cultural and epistemic paradigms that orient subject-object relationships; giving people the opportunity to reflect on their own realities, engage in new experiences and find new ways to live better in a better world. The proposal is a creative model for thought and practice, providing many opportunities for discussion, debate and development of holistic projects integrating different scientific domains (social sciences, psychology, education, philosophy, etc.)

Chemometric Studies on Natural Products as Potential Inhibitors of the NADH Oxidase from Trypanosoma cruzi Using the VolSurf Approach

Natural products have widespread biological activities, including inhibition of mitochondrial enzyme systems. Some of these activities, for example cytotoxicity, may be the result of alteration of cellular bioenergetics. Based on previous computer-aided drug design (CADD) studies and considering reported data on structure-activity relationships (SAR), an assumption regarding the mechanism of action of natural products against parasitic infections involves the NADH-oxidase inhibition. In this study, chemometric tools, such as: Principal Component Analysis (PCA), Consensus PCA (CPCA), and partial least squares regression (PLS), were applied to a set of forty natural compounds, acting as NADH-oxidase inhibitors. The calculations were performed using the VolSurf+ program. The formalisms employed generated good exploratory and predictive results. The independent variables or descriptors having a hydrophobic profile were strongly correlated to the biological data.