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.

False-positive results of a rapid K39-based strip test and Chagas disease

Background: The definitive diagnosis of visceral. leishmaniasis (VL) requires invasive procedures with demonstration of amastigotes in tissue or promastigotes in culture. Unfortunately, these approaches require laboratory materials not available in poor countries where the disease is endemic. The correct diagnosis of VL is important, and made more difficult by the fact that several common tropical diseases such as malaria, disseminated tuberculosis, and enteric fever share the same clinical presentation. Serological tests have been developed to replace parasitological diagnosis in the field. A commercially available K39-based strip test for VL has been developed for this purpose. The endemic area of leishmaniasis in Brazil overlaps the endemic area of Chagas disease, a disease that can cause false-positive serological test results. The aim of this study was to evaluate the incidence of false-positive exams using a rapid test for VL in patients with Chagas disease. Methods: A rapid test based on the recombinant K39 antigen of Leishmania was used in: (1) 30 patients with confirmed Chagas disease, (2) 30 patients with a serological diagnosis of Chagas disease by ELISA, indirect immunofluorescence, indirect hemagglutination, and chemiluminescence, (3) 30 healthy patients from a non-endemic area as the control group, (4) 30 patients with confirmed VL, and (5) 20 patients with proved cutaneous leishmaniasis. Results: The sensitivity and specificity of the rapid strip test were 100% when compared with healthy volunteers and those with confirmed Chagas disease. One false-positive result occurred in the group with Chagas disease diagnosed by serological tests (specificity of 96%). Conclusion: The rapid test based on recombinant K39 is a useful diagnostic assay, and a false-positive result rarely occurs in patients with a serological diagnosis of Chagas disease. (C) 2008 International Society for Infectious Diseases. Published by Elsevier Ltd. All rights reserved.

Spin current in the Mobius cyclacene belts

We report on density functional theory studies of the electronic structure and magnetic properties of Mobius-[n]cyclacenes. The geometry of Mobius bands presents a modulation of bond lengths that is needed to accommodate the twist. This modulation takes the form of bond alternation defects analogous to those of solitons in polyacetylene. The ground state of all Mobius bands is a triplet, with a spin density distribution that follows the bond length modulation. A molecular dynamics simulation of the Mobius cyclacene at 300 K shows that the twist travels around the belt inducing a magnetic current. (C) 2009 Elsevier B. V. All rights reserved.

Effects of Crossing Saddle Coil Conductors: Electric Length X Mutual Inductance

In magnetic resonance imaging (MRI), either on human or animal studies, the main requirements for radiofrequency (RF) coils are to produce a homogeneous RF field while used as a transmitter coil and to have the best signal-to-noise ratio (SNR) while used as a receiver. Besides, they need to be easily frequency adjustable and have input impedance matching 50 Omega to several different load conditions. New theoretical and practical concepts are presented here for considerable enhancing of RF coil homogeneity for MRI experiments on small animals. To optimize field homogeneity, we have performed simulations using Blot and Savart law varying the coil`s window angle, achieving the optimum one. However, when the coil`s dimensions are the same order of the wave length and according to transmission line theory, differences in electrical length and effects of mutual inductances between adjacent strip conductors decrease both field homogeneity and SNR. The problematic interactions between strip conductors by means of mutual inductance were eliminated by inserting crossings at half electrical length, avoiding distortion on current density, thus eliminating sources of field inhomogeneity. Experimental results show that measured field maps and simulations are in good agreement. The new coil design, dubbed double-crossed saddle described here have field homogeneity and SNR superior than the linearly driven 8-rung birdcage coil. One of our major findings was that the effects of mutual inductance are more significant than differences in electrical length for this frequency and coil dimensions. In vitro images of a primate Cebus paela brain were acquired, confirming double-crossed saddle superiority. (C) 2010 Wiley Periodicals, Inc. Concepts Magn Reson Part B (Magn Reson Engineering) 37B: 193-201, 2010

Relics of eclogite facies assemblages in the Ceara Central Domain, NW Borborema Province, NE Brazil: Implications for the assembly of West Gondwana

The Borborema Province, in the NE of Brazil, is a rather complex piece in the Brazil-Africa puzzle as it represents the junction of the Dahomeyide/Pharusian, Central African, Aracuai and Brasilia fold belts located between the West-African/Sao Luis, Congo/Sao Francisco and Amazonas craton. The correlation between the Dahomeyides from W-Africa (Ghana, Benin, Togo, and Mali) and the Borborema Province involves the Medio Coreau and Central Ceara domains. The inferred continuation of the main oceanic suture zone exposed in the Dahomeyides of W Africa is buried beneath the Phanerozoic Parnaiba Basin in Brazil (northwest of the Medio Coreau domain) where some high density gravity anomalies may represent hidden remnants of an oceanic suture. In addition to this major suture a narrow, nearly continuous strip composed of mainly mafic pods containing relics of eclogite-facies assemblages associated with partially migmatized granulite-facies metapelitic gneisses has been found further east in the NW Borborema Province. These high pressure mafic rocks, interpreted as retrograded eclogites, are located between the Transbrasiliano Lineament and the Santa Quiteria continental arc and comprise primitive to evolved arc-related rocks with either arc- or MORB-type imprints that can indicate either deep subduction of oceanic lithosphere or roots of continental and oceanic magmatic arcs. Average peak P-T conditions under eclogite-facies metamorphism (T=770 degrees C and P = 17.3 kbar) were estimated using garnet-clinopyroxene thermometry and Jd content in clinopyroxene. Transition to granulite-facies conditions, as well as later widespread re-equilibration under amphibolite facies, were registered both in the basic and the metapelitic rocks and suggest a clockwise P-T path characterized by an increase in temperature followed by strong decompression. A phenomenon possibly related to the exhumation of a highly thickened crust associated with the suturing of the Medio Coreau and Central Ceara domains, two distinct crustal blocks separated by the Transbrasiliano Lineament. (C) 2009 International Association for Gondwana Research. Published by Elsevier B.V. All rights reserved.

Three-dimensional packings with rotations

We present approximation algorithms for the three-dimensional strip packing problem, and the three-dimensional bin packing problem. We consider orthogonal packings where 90 degrees rotations are allowed. The algorithms we show for these problems have asymptotic performance bounds 2.64, and 4.89, respectively. These algorithms are for the more general case in which the bounded dimensions of the bin given in the input are not necessarily equal (that is, we consider bins for which the length. the width and the height are not necessarily equal). Moreover, we show that these problems-in the general version-are as hard to approximate as the corresponding oriented version. (C) 2009 Elsevier Ltd. All rights reserved.

Minimizing the object dimensions in circle and sphere packing problems

Given a fixed set of identical or different-sized circular items, the problem we deal with consists on finding the smallest object within which the items can be packed. Circular, triangular, squared, rectangular and also strip objects are considered. Moreover, 2D and 3D problems are treated. Twice-differentiable models for all these problems are presented. A strategy to reduce the complexity of evaluating the models is employed and, as a consequence, instances with a large number of items can be considered. Numerical experiments show the flexibility and reliability of the new unified approach. (C) 2007 Elsevier Ltd. All rights reserved.

HOMEOMORPHISMS OF THE ANNULUS WITH A TRANSITIVE LIFT II

Let f be a homeomorphism of the closed annulus A that preserves the orientation, the boundary components and that has a lift (f) over tilde to the in finite strip (A) over tilde which is transitive. We show that, if the rotation number of (f) over tilde restricted to both boundary components of A is strictly positive, then there exists a closed nonempty connected set Gamma subset of (A) over tilde such that Gamma subset of] - infinity,0] x [0,1], Gamma is unbounded, the projection of to Gamma A is dense, Gamma - (1, 0) subset of Gamma and (f) over tilde(Gamma) subset of Gamma. Also, if p(1) is the projection on the first coordinate of (A) over tilde, then there exists d > 0 such that, for any (z) over tilde is an element of Gamma, lim sup (n ->infinity) p(1)((f) over tilde (n) ((Z) over tilde)) - p(1) ((Z) over tilde)/n < -d.

Homeomorphisms of the annulus with a transitive lift

Let f be a homeomorphism of the closed annulus A that preserves the orientation, the boundary components and that has a lift (f) over tilde to the infinite strip (A) over tilde which is transitive. We show that, if the rotation numbers of both boundary components of A are strictly positive, then there exists a closed nonempty unbounded set B(-) subset of (A) over tilde such that B(-) is bounded to the right, the projection of B to A is dense, B - (1, 0) subset of B and (f) over tilde (B) subset of B. Moreover, if p(1) is the projection on the first coordinate of (A) over tilde, then there exists d > 0 such that, for any (z) over tilde is an element of B(-), lim sup (n ->infinity) p1((f) over tilde (n)((z) over tilde)) - p(1) ((z) over tilde)/n < - d. In particular, using a result of Franks, we show that the rotation set of any homeomorphism of the annulus that preserves orientation, boundary components, which has a transitive lift without fixed points in the boundary is an interval with 0 in its interior.