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.

Development and applications of three-dimensional gamma ray tomography system using ray casting volume rendering techniques

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A STUDY OF PENALTY FORMULATIONS USED IN THE NUMERICAL APPROXIMATION OF A RADIALLY SYMMETRIC ELASTICITY PROBLEM

We consider a class of two-dimensional problems in classical linear elasticity for which material overlapping occurs in the absence of singularities. Of course, material overlapping is not physically realistic, and one possible way to prevent it uses a constrained minimization theory. In this theory, a minimization problem consists of minimizing the total potential energy of a linear elastic body subject to the constraint that the deformation field must be locally invertible. Here, we use an interior and an exterior penalty formulation of the minimization problem together with both a standard finite element method and classical nonlinear programming techniques to compute the minimizers. We compare both formulations by solving a plane problem numerically in the context of the constrained minimization theory. The problem has a closed-form solution, which is used to validate the numerical results. This solution is regular everywhere, including the boundary. In particular, we show numerical results which indicate that, for a fixed finite element mesh, the sequences of numerical solutions obtained with both the interior and the exterior penalty formulations converge to the same limit function as the penalization is enforced. This limit function yields an approximate deformation field to the plane problem that is locally invertible at all points in the domain. As the mesh is refined, this field converges to the exact solution of the plane problem.

Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions

This work deals with the problem of minimizing the waste of space that occurs on a rotational placement of a set of irregular two dimensional polygons inside a two dimensional container. This problem is approached with an heuristic based on simulated annealing. Traditional 14 external penalization"" techniques are avoided through the application of the no-fit polygon, that determinates the collision free area for each polygon before its placement. The simulated annealing controls: the rotation applied, the placement and the sequence of placement of the polygons. For each non placed polygon, a limited depth binary search is performed to find a scale factor that when applied to the polygon, would allow it to be fitted in the container. It is proposed a crystallization heuristic, in order to increase the number of accepted solutions. The bottom left and larger first deterministic heuristics were also studied. The proposed process is suited for non convex polygons and containers, the containers can have holes inside. (C) 2009 Elsevier Ltd. All rights reserved.

Evolution of three-dimensional folds for a non-Newtonian plate in a viscous medium

We derive analytical solutions for the three-dimensional time-dependent buckling of a non-Newtonian viscous plate in a less viscous medium. For the plate we assume a power-law rheology. The principal, axes of the stretching D-ij in the homogeneously deformed ground state are parallel and orthogonal to the bounding surfaces of the plate in the flat state. In the model formulation the action of the less viscous medium is replaced by equivalent reaction forces. The reaction forces are assumed to be parallel to the normal vector of the deformed plate surfaces. As a consequence, the buckling process is driven by the differences between the in-plane stresses and out of plane stress, and not by the in-plane stresses alone as assumed in previous models. The governing differential equation is essentially an orthotropic plate equation for rate dependent material, under biaxial pre-stress, supported by a viscous medium. The differential problem is solved by means of Fourier transformation and largest growth coefficients and corresponding wavenumbers are evaluated. We discuss in detail fold evolutions for isotropic in-plane stretching (D-11 = D-22), uniaxial plane straining (D-22 = 0) and in-plane flattening (D-11 = -2D(22)). Three-dimensional plots illustrate the stages of fold evolution for random initial perturbations or initial embryonic folds with axes non-parallel to the maximum compression axis. For all situations, one dominant set of folds develops normal to D-11, although the dominant wavelength differs from the Biot dominant wavelength except when the plate has a purely Newtonian viscosity. However, in the direction parallel to D-22, there exist infinitely many modes in the vicinity of the dominant wavelength which grow only marginally slower than the one corresponding to the dominant wavelength. This means that, except for very special initial conditions, the appearance of a three-dimensional fold will always be governed by at least two wavelengths. The wavelength in the direction parallel to D-11 is the dominant wavelength, and the wavelength(s) in the direction parallel to D-22 is determined essentially by the statistics of the initial state. A comparable sensitivity to the initial geometry does not exist in the classic two-dimensional folding models. In conformity with tradition we have applied Kirchhoff's hypothesis to constrain the cross-sectional rotations of the plate. We investigate the validity of this hypothesis within the framework of Reissner's plate theory. We also include a discussion of the effects of adding elasticity into the constitutive relations and show that there exist critical ratios of the relaxation times of the plate and the embedding medium for which two dominant wavelengths develop, one at ca. 2.5 of the classical Biot dominant wavelength and the other at ca. 0.45 of this wavelength. We propose that herein lies the origin of parasitic folds well known in natural examples.

Algebraic Bethe ansatz for integrable Kondo impurities in the one-dimensional supersymmetric t-J model

An integrable Kondo problem in the one-dimensional supersymmetric t-J model is studied by means of the boundary supersymmetric quantum inverse scattering method. The boundary K matrices depending on the local moments of the impurities are presented as a nontrivial realization of the graded reflection equation algebras in a two-dimensional impurity Hilbert space. Further, the model is solved by using the algebraic Bethe ansatz method and the Bethe ansatz equations are obtained. (C) 1999 Elsevier Science B.V.

Integrable Kondo impurities in the one-dimensional supersymmetric extended Hubbard model

An integrable Kondo problem in the one-dimensional supersymmetric extended Hubbard model is studied by means of the boundary graded quantum inverse scattering method. The boundary K-matrices depending on the local moments of the impurities are presented as a non-trivial realization of the graded reflection equation algebras in a two-dimensional impurity Hilbert space. Further, the model is solved by using the algebraic Bethe ansatz method and the Bethe ansatz equations are obtained.

Three-dimensional aspects of fluid flows in channels. II. Effects of meniscus and thin film regimes on viscous fingers

We perform a three-dimensional study of steady state viscous fingers that develop in linear channels. By means of a three-dimensional lattice-Boltzmann scheme that mimics the full macroscopic equations of motion of the fluid momentum and order parameter, we study the effect of the thickness of the channel in two cases. First, for total displacement of the fluids in the channel thickness direction, we find that the steady state finger is effectively two-dimensional and that previous two-dimensional results can be recovered by taking into account the effect of a curved meniscus across the channel thickness as a contribution to surface stresses. Second, when a thin film develops in the channel thickness direction, the finger narrows with increasing channel aspect ratio in agreement with experimental results. The effect of the thin film renders the problem three-dimensional and results deviate from the two-dimensional prediction.

Three-dimensional aspects of fluid flows in channels. II. Effects of meniscus and thin film regimes on viscous fingers

We perform a three-dimensional study of steady state viscous fingers that develop in linear channels. By means of a three-dimensional lattice-Boltzmann scheme that mimics the full macroscopic equations of motion of the fluid momentum and order parameter, we study the effect of the thickness of the channel in two cases. First, for total displacement of the fluids in the channel thickness direction, we find that the steady state finger is effectively two-dimensional and that previous two-dimensional results can be recovered by taking into account the effect of a curved meniscus across the channel thickness as a contribution to surface stresses. Second, when a thin film develops in the channel thickness direction, the finger narrows with increasing channel aspect ratio in agreement with experimental results. The effect of the thin film renders the problem three-dimensional and results deviate from the two-dimensional prediction.

Families of periodic orbits for the spatial isosceles 3-body problem

We study the families of periodic orbits of the spatial isosceles 3-body problem (for small enough values of the mass lying on the symmetry axis) coming via the analytic continuation method from periodic orbits of the circular Sitnikov problem. Using the first integral of the angular momentum, we reduce the dimension of the phase space of the problem by two units. Since periodic orbits of the reduced isosceles problem generate invariant two-dimensional tori of the nonreduced problem, the analytic continuation of periodic orbits of the (reduced) circular Sitnikov problem at this level becomes the continuation of invariant two-dimensional tori from the circular Sitnikov problem to the nonreduced isosceles problem, each one filled with periodic or quasi-periodic orbits. These tori are not KAM tori but just isotropic, since we are dealing with a three-degrees-of-freedom system. The continuation of periodic orbits is done in two different ways, the first going directly from the reduced circular Sitnikov problem to the reduced isosceles problem, and the second one using two steps: first we continue the periodic orbits from the reduced circular Sitnikov problem to the reduced elliptic Sitnikov problem, and then we continue those periodic orbits of the reduced elliptic Sitnikov problem to the reduced isosceles problem. The continuation in one or two steps produces different results. This work is merely analytic and uses the variational equations in order to apply Poincar´e’s continuation method.

Prenatal diagnosis of Beckwith-Wiedemann syndrome by two- and three-dimensional ultrasonography

Beckwith-Wiedemann syndrome is a genetic syndrome characterized by macroglossia, omphalocele, fetal gigantism and neonatal hypoglycemia. The authors report a case of Beckwith-Wiedemann syndrome diagnosed in a 32-year-old primigravida in whom two-dimensional ultrasonography revealed the presence of abdominal wall cyst, macroglossia and polycystic kidneys. Three-dimensional ultrasonography in rendering mode was of great importance to confirm the previous two-dimensional ultrasonography findings.

Comparison of Two- and Three-dimensional Ultrasonography in the Evaluation of Lesion Level in Fetuses with Spina Bifida

Purpose To evaluate the precision of both two- and three-dimensional ultrasonography in determining vertebral lesion level (the first open vertebra) in patients with spina bifida. Methods This was a prospective longitudinal study comprising of fetuses with open spina bifida who were treated in the fetal medicine division of the department of obstetrics of Hospital das Clínicas of the Universidade de São Paulo between 2004 and 2013. Vertebral lesion level was established by using both two- and three-dimensional ultrasonography in 50 fetuses (two examiners in each method). The lesion level in the neonatal period was established by radiological assessment of the spine. All pregnancies were followed in our hospital prenatally, and delivery was scheduled to allow immediate postnatal surgical correction. Results Two-dimensional sonography precisely estimated the spina bifida level in 53% of the cases. The estimate error was within one vertebra in 80% of the cases, in up to two vertebrae in 89%, and in up to three vertebrae in 100%, showing a good interobserver agreement. Three-dimensional ultrasonography precisely estimated the lesion level in 50% of the cases. The estimate error was within one vertebra in 82% of the cases, in up to two vertebrae in 90%, and in up to three vertebrae in 100%, also showing good interobserver agreement. Whenever an estimate error was observed, both two- and three-dimensional ultrasonography scans tended to underestimate the true lesion level (55.3% and 62% of the cases, respectively). Conclusions No relevant difference in diagnostic performance was observed between the two- and three-dimensional ultrasonography. The use of three-dimensional ultrasonography showed no additional benefit in diagnosing the lesion level in the fetuses with spina bifida. Errors in both methods showed a tendency to underestimate lesion level.

From inference to affordance : the problem of visual depth-perception in the optical writings of Descartes, Berkeley, and Gibson

This thesis explores the debate and issues regarding the status of visual ;,iferellces in the optical writings of Rene Descartes, George Berkeley and James 1. Gibson. It gathers arguments from across their works and synthesizes an account of visual depthperception that accurately reflects the larger, metaphysical implications of their philosophical theories. Chapters 1 and 2 address the Cartesian and Berkelean theories of depth-perception, respectively. For Descartes and Berkeley the debate can be put in the following way: How is it possible that we experience objects as appearing outside of us, at various distances, if objects appear inside of us, in the representations of the individual's mind? Thus, the Descartes-Berkeley component of the debate takes place exclusively within a representationalist setting. Representational theories of depthperception are rooted in the scientific discovery that objects project a merely twodimensional patchwork of forms on the retina. I call this the "flat image" problem. This poses the problem of depth in terms of a difference between two- and three-dimensional orders (i.e., a gap to be bridged by one inferential procedure or another). Chapter 3 addresses Gibson's ecological response to the debate. Gibson argues that the perceiver cannot be flattened out into a passive, two-dimensional sensory surface. Perception is possible precisely because the body and the environment already have depth. Accordingly, the problem cannot be reduced to a gap between two- and threedimensional givens, a gap crossed with a projective geometry. The crucial difference is not one of a dimensional degree. Chapter 3 explores this theme and attempts to excavate the empirical and philosophical suppositions that lead Descartes and Berkeley to their respective theories of indirect perception. Gibson argues that the notion of visual inference, which is necessary to substantiate representational theories of indirect perception, is highly problematic. To elucidate this point, the thesis steps into the representationalist tradition, in order to show that problems that arise within it demand a tum toward Gibson's information-based doctrine of ecological specificity (which is to say, the theory of direct perception). Chapter 3 concludes with a careful examination of Gibsonian affordallces as the sole objects of direct perceptual experience. The final section provides an account of affordances that locates the moving, perceiving body at the heart of the experience of depth; an experience which emerges in the dynamical structures that cross the body and the world.

Response curves of deterministic and probabilistic cellular automata in one and two dimensions

One of the most important problems in the theory of cellular automata (CA) is determining the proportion of cells in a specific state after a given number of time iterations. We approach this problem using patterns in preimage sets - that is, the set of blocks which iterate to the desired output. This allows us to construct a response curve - a relationship between the proportion of cells in state 1 after niterations as a function of the initial proportion. We derive response curve formulae for many two-dimensional deterministic CA rules with L-neighbourhood. For all remaining rules, we find experimental response curves. We also use preimage sets to classify surjective rules. In the last part of the thesis, we consider a special class of one-dimensional probabilistic CA rules. We find response surface formula for these rules and experimental response surfaces for all remaining rules.

Scale-invariant moving finite elements for nonlinear partial differential equations in two dimensions

A scale-invariant moving finite element method is proposed for the adaptive solution of nonlinear partial differential equations. The mesh movement is based on a finite element discretisation of a scale-invariant conservation principle incorporating a monitor function, while the time discretisation of the resulting system of ordinary differential equations is carried out using a scale-invariant time-stepping which yields uniform local accuracy in time. The accuracy and reliability of the algorithm are successfully tested against exact self-similar solutions where available, and otherwise against a state-of-the-art h-refinement scheme for solutions of a two-dimensional porous medium equation problem with a moving boundary. The monitor functions used are the dependent variable and a monitor related to the surface area of the solution manifold. (c) 2005 IMACS. Published by Elsevier B.V. All rights reserved.