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.

Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints

This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. (C) 2007 Elsevier B.V. All rights reserved.

Epidemics in networks of spatially correlated three-dimensional root-branching structures

Using digitized images of the three-dimensional, branching structures for root systems of bean seedlings, together with analytical and numerical methods that map a common susceptible-infected- recovered (`SIR`) epidemiological model onto the bond percolation problem, we show how the spatially correlated branching structures of plant roots affect transmission efficiencies, and hence the invasion criterion, for a soil-borne pathogen as it spreads through ensembles of morphologically complex hosts. We conclude that the inherent heterogeneities in transmissibilities arising from correlations in the degrees of overlap between neighbouring plants render a population of root systems less susceptible to epidemic invasion than a corresponding homogeneous system. Several components of morphological complexity are analysed that contribute to disorder and heterogeneities in the transmissibility of infection. Anisotropy in root shape is shown to increase resilience to epidemic invasion, while increasing the degree of branching enhances the spread of epidemics in the population of roots. Some extension of the methods for other epidemiological systems are discussed.

One-dimensional trapped atoms: critical coupling parameter and critical number of particles

In this paper we consider the case of a Bose gas in low dimension in order to illustrate the applicability of a method that allows us to construct analytical relations, valid for a broad range of coupling parameters, for a function which asymptotic expansions are known. The method is well suitable to investigate the problem of stability of a collection of Bose particles trapped in one- dimensional configuration for the case where the scattering length presents a negative value. The eigenvalues for this interacting quantum one-dimensional many particle system become negative when the interactions overcome the trapping energy and, in this case, the system becomes unstable. Here we calculate the critical coupling parameter and apply for the case of Lithium atoms obtaining the critical number of particles for the limit of stability.

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.

ENO adaptive method for solving one-dimensional conservation laws

In this work an efficient third order non-linear finite difference scheme for solving adaptively hyperbolic systems of one-dimensional conservation laws is developed. The method is based oil applying to the solution of the differential equation an interpolating wavelet transform at each time step, generating a multilevel representation for the solution, which is thresholded and a sparse point representation is generated. The numerical fluxes obtained by a Lax-Friedrichs flux splitting are evaluated oil the sparse grid by an essentially non-oscillatory (ENO) approximation, which chooses the locally smoothest stencil among all the possibilities for each point of the sparse grid. The time evolution of the differential operator is done on this sparse representation by a total variation diminishing (TVD) Runge-Kutta method. Four classical examples of initial value problems for the Euler equations of gas dynamics are accurately solved and their sparse solutions are analyzed with respect to the threshold parameters, confirming the efficiency of the wavelet transform as an adaptive grid generation technique. (C) 2008 IMACS. Published by Elsevier B.V. All rights reserved.

Approaches for multicopper oxidases in the design of electrochemical sensors for analytical applications

We report an effective approach for the construction of a biomimetic sensor of multicopper oxidases by immobilizing a cyclic-tetrameric copper(II) species, containing the ligand (4-imidazolyl)ethylene-2-amino-1-ethylpyridine (apyhist), in the Nafion (R) membrane on a vitreous carbon electrode surface. This complex provides a tetranuclear arrangement of copper ions that allows an effective reduction of oxygen to water, in a catalytic cycle involving four electrons. The electrochemical reduction of oxygen was studied at pH 9.0 buffer solution by using cyclic voltammetry, chronoamperometry, rotating disk electrode voltammetry and scanning electrochemical microscopy techniques. The mediator shows good electrocatalytic ability for the reduction of O(2) at pH 9.0, with reduction of overpotential (350 mV) and increased current response in comparison with results obtained with a bare glassy carbon electrode. The heterogeneous rate constant (k(ME)`) for the reduction of O(2) at the modified electrode was determined by using a Koutecky-Levich plot. In addition, the charge transport rate through the coating and the apparent diffusion coefficient of O(2) into the modifier film were also evaluated. The overall process was found to be governed by the charge transport through the coating, occurring at the interface or at a finite layer at the electrode/coating interface. The proposed study opens up the way for the development of bioelectronic devices based on molecular recognition and self-organization. (C) 2010 Elsevier Ltd. All rights reserved.

Simultaneous voltammetric detection of ascorbic acid, dopamine and uric acid using a pyrolytic graphite electrode modified into dopamine solution

Pyrolytic graphite electrodes (PGE) were modified into dopamine solutions using phosphate buffer solutions, pH 10 and 6.5, as supporting electrolyte. The modification process involved a previous anodization of the working electrode at +1. 5 V into 0. 1 mol-L-1 NaOH followed by other anodization step, in the same experimental conditions, into dopamine (DA) solutions. pH of the supporting electrolyte performed an important role in the production of a superficial melanin polymeric film, which permitted the simultaneous detection of ascorbic acid (AA), (DA) and uric acid (UA), Delta EAA-DA = 222 mV-, Delta EAA-UA = 360 mV and Delta EDA-UA=138mV, avoiding the superficial poisoning effects. The calculated detection limits were: 1.4 x 10(-6) mol L-1 for uric acid, 1.3x10-(5) molL(-1) for ascorbic acid and 1.1 X 10(-7) mol L-1 for dopamine, with sensitivities of (7.7 +/- 0.5), (0.061 +/- 0.001) and (9.5 +/- 0.05)A mol(-1) cm(-2), respectively, with no mutual interference. Uric acid was determined in urine, blood and serum human samples after dilution in phosphate buffer and no additional sample pre-treatment was necessary. The concentration of uric acid in urine was higher than the values found in blood and serum and the recovery tests (92-102%) indicated that no matrix effects were observed. (C) 2008 Elsevier B.V. All rights reserved.

Automated two-dimensional separation flow system with electrochemical preconcentration, stripping, capillary electrophoresis and contactless conductivity detection for trace metal ion analysis

This paper describes the automation of a fully electrochemical system for preconcentration, cleanup, separation and detection, comprising the hyphenation of a thin layer electrochemical flow cell with CE coupled with contactless conductivity detection (CE-C(4)D). Traces of heavy metal ions were extracted from the pulsed-flowing sample and accumulated on a glassy carbon working electrode by electroreduction for some minutes. Anodic stripping of the accumulated metals was synchronized with hydrodynamic injection into the capillary. The effect of the angle of the slant polished tip of the CE capillary and its orientation against the working electrode in the electrochemical preconcentration (EPC) flow cell and of the accumulation time were studied, aiming at maximum CE-C(4)D signal enhancement. After 6 min of EPC, enhancement factors close to 50 times were obtained for thallium, lead, cadmium and copper ions, and about 16 for zinc ions. Limits of detection below 25 nmol/L were estimated for all target analytes but zinc. A second separation dimension was added to the CE separation capabilities by staircase scanning of the potentiostatic deposition and/or stripping potentials of metal ions, as implemented with the EPC-CE-C(4)D flow system. A matrix exchange between the deposition and stripping steps, highly valuable for sample cleanup, can be straightforwardly programmed with the multi-pumping flow management system. The automated simultaneous determination of the traces of five accumulable heavy metals together with four non-accumulated alkaline and alkaline earth metals in a single run was demonstrated, to highlight the potentiality of the system.

Removal of metal ions from aqueous solution by chelating polymeric hydrogel

Polysaccharide natural seed coat from the tree Magonia pubescens, in the form of hydrogel was used to remove metals in aqueous solution. Swelling tests indicate that seed coat presents hydrogel behavior, with maximum water absorption of 292 g water/g. Adsorption experiments performed using Na(+), Mg(2+), K(+), Ca(2+), Cr(3+), Fe(3+) and Zn(2+) demonstrated that the polysaccharide structure has a high capacity to extract these ions from the aqueous solution. Scanning electron microscopy revealed significant morphological changes of the material before and after water contact. Differential scanning calorimetry measurements indicate a signal shift of the water evaporation temperature in the material with adsorbed zinc. X-ray photoelectron spectroscopy analysis combined with theoretical studies by the density functional theory and on Hartree-Fock (HF) level evidence that the metallic ions were adsorbed through coordination with hydroxyl groups of polysaccharide. In the case of Zn(2+) the lowest HF energy was observed for the tetracoordination mode, where Zn(2+) is coordinated by two hydroxyl groups and two water molecules.

Static and dynamic bimolecular fluorescence quenching of porphyrin dendrimers in solution

The fluorescence quenching kinetics of two porphyrin dendrimer series (GnTPPH(2) and GnPZn) by different type of quenchers is reported. The microenvironment surrounding the core in GnPZn was probing by core-quencher interactions using benzimidazole. The dependence of quencher binding constant (K(a) ) on generation indicates the presence of a weak interaction between branches and the core of the porphyrin dendrimer. The similar free volume in dendrimers of third and fourth generation suggests that structural collapse in high generations occurs by packing of the dendrimer peripheral layer. Dynamic fluorescence quenching of the porphyrin core by 1,3-dicyanomethylene-2-methyl-2-pentyl-indan (PDCMI) in GnTPPH(2) is a distance dependent electron transfer process with an exponential attenuation factor beta=0.33 angstrom(-1). The quenching by 1,2-dibromobenzene occurs by diffusion process of the quencher toward to the porphyrin core, and its rate constant is practically independent of dendrimer generation.

Development of an Analytical Methodology for Quantification of Strong Acid in Diesel Oil

Many factors can affect the quality of diesel oil, in particular the degradation processes that are directly related to some organosulfur compounds. During the degradation process, these compounds are oxidized into their corresponding sulfonic acids, generating a strong acid content during the process. p-Toluene sulfonic acid analysis was performed using the linear sweep voltammetry technique with a platinum ultramicroelectrode in aqueous solution containing 3 mol L(-1) potassium chloride. An extraction step was introduced prior to the voltammetric detection in order to avoid the adsorption of organic molecules, which inhibit the electrochemical response. The extraction step promoted the transference of sulfonic acid from the diesel oil to an aqueous phase. The method was accurate and reproducible, with detection and quantification limits of 5 ppm and 15 ppm, respectively. Recovery of sulfonic acid was around 90%.

Structural studies of prephenate dehydratase from Mycobacterium tuberculosis H37Rv by SAXS, ultracentrifugation, and computational analysis

Tuberculosis (TB) is one of the most common infectious diseases known to man and responsible for millions of human deaths in the world. The increasing incidence of TB in developing countries, the proliferation of multidrug resistant strains, and the absence of resources for treatment have highlighted the need of developing new drugs against TB. The shikimate pathway leads to the biosynthesis of chorismate, a precursor of aromatic amino acids. This pathway is absent from mammals and shown to be essential for the survival of Mycobacterium tuberculosis, the causative agent of TB. Accordingly, enzymes of aromatic amino acid biosynthesis pathway represent promising targets for structure-based drug design. The first reaction in phenylalanine biosynthesis involves the conversion of chorismate to prephenate, catalyzed by chorismate mutase. The second reaction is catalyzed by prephenate dehydratase (PDT) and involves decarboxylation and dehydratation of prephenate to form phenylpyruvate, the precursor of phenylalanine. Here, we describe utilization of different techniques to infer the structure of M. tuberculosis PDT (MtbPDT) in solution. Small angle X-ray scattering and ultracentrifugation analysis showed that the protein oligomeric state is a tetramer and MtbPDT is a flat disk protein. Bioinformatics tools were used to infer the structure of MtbPDT A molecular model for MtbPDT is presented and molecular dynamics simulations indicate that MtbPDT i.s stable. Experimental and molecular modeling results were in agreement and provide evidence for a tetrameric state of MtbPDT in solution.

Electroanalytical determination of N-nitrosamines in aqueous solution using a boron-doped diamond electrode

The electrochemical methods cyclic and square-wave voltammetry were applied to develop an electroanalytical procedure for the determination of N-nitrosamines (N-nitrosopyrrolidine, N-nitrosopiperidine and N-nitrosodiethylamine) in aqueous solutions. Cyclic voltammetry was used to evaluate the electrochemical behaviors of N-nitrosamines on boron-doped diamond electrodes. It was observed an irreversible electrooxidation peak located in approximately 1.8 V (vs. Ag/AgCl) for both N-nitrosamines. The optimal electrochemical response was obtained using the following square-wave voltammetry parameters: f = 250 Hz, E(sw) = 50 mV and E(s) = 2 mV using a Britton-Robinson buffer solution as electrolyte (pH 2). The detection and quantification limits determined for total N-nitrosamines were 6.0 x 10(-8) and 2.0 x 10(-7) mol L(-1), respectively.

Determination of Minoxidil by Bleaching the Permanganate Carrier Solution in a Flow-Based Spectrophotometric System

The determination of minoxidil (MX) with potassium permanganate as a carrier in a flow injection method is described. The detection at 550nm was linear from 1.0x10-5 to 5.0x10-4mol L-1. The limit of detection (3 sigma/slope) was 8.92x10-6mol L-1, with an analytical frequency of 32h-1. The proposed method was applied to commercial samples, with recoveries from 104.7 to 106.4%. Comparison with the HPLC procedure reveled relative errors from 0.48 to 1.4%, and the results agreed within a 95% confidence level.