Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

Suppressing Fermi acceleration in a two-dimensional non-integrable time-dependent oval-shaped billiard with inelastic collisions

Some dynamical properties of a classical particle confined inside a closed region with an oval-shaped boundary are studied. We have considered both the static and time-dependent boundaries. For the static case, the condition that destroys the invariant spanning curves in the phase space was obtained. For the time-dependent perturbation, two situations were considered: (i) non-dissipative and (ii) dissipative. For the non-dissipative case, our results show that Fermi acceleration is observed. When dissipation, via inelastic collisions, is introduced Fermi acceleration is suppressed. The behaviour of the average velocity for both the dissipative as well as the non-dissipative dynamics is described using the scaling approach. (C) 2009 Elsevier B.V. All rights reserved.

Boundary crisis and suppression of Fermi acceleration in a dissipative two-dimensional non-integrable time-dependent billiard

Some dynamical properties for a dissipative time-dependent oval-shaped billiard are studied. The system is described in terms of a four-dimensional nonlinear mapping. Dissipation is introduced via inelastic collisions of the particle with the boundary, thus implying that the particle has a fractional loss of energy upon collision. The dissipation causes profound modifications in the dynamics of the particle as well as in the phase space of the non-dissipative system. In particular, inelastic collisions can be assumed as an efficient mechanism to suppress Fermi acceleration of the particle. The dissipation also creates attractors in the system, including chaotic. We show that a slightly modification of the intensity of the damping coefficient yields a drastic and sudden destruction of the chaotic attractor, thus leading the system to experience a boundary crisis. We have characterized such a boundary crisis via a collision of the chaotic attractor with its own basin of attraction and confirmed that inelastic collisions do indeed suppress Fermi acceleration in two-dimensional time-dependent billiards. (C) 2010 Elsevier B.V. All rights reserved.

A two-dimensional analytical solution of groundwater responses to tidal loading in an estuary and ocean

Previous studies on tidal dynamics of coastal aquifers have focussed on the inland propagation of oceanic tides in the cross-shore direction, a configuration that is essentially one-dimensional. Aquifers at natural coasts can also be influenced by tidal waves in nearby estuaries, resulting in a more complex behaviour of head fluctuations in the aquifers. We present an analytical solution to the two-dimensional depth-averaged groundwater flow equation for a semi-infinite aquifer subject to oscillating head conditions at the boundaries. The solution describes the tidal dynamics of a coastal aquifer that is adjacent to a cross-shore estuary. Both the effects of oceanic and estuarine tides on the aquifer are included in the solution. The analytical prediction of the head fluctuations is verified by comparison with numerical solutions computed using a standard finite-difference method. An essential feature of the present analytical solution is the interaction between the cross- and along-shore tidal waves in the aquifer area near the estuary's entry. As the distance from the estuary or coastline increases, the wave interaction is weakened and the aquifer response is reduced, respectively, to the one-dimensional solution for oceanic tides or the solution of Sun (Sun H. A two-dimensional analytical solution of groundwater response to tidal loading in an estuary, Water Resour Res 1997;33:1429-35) for two-dimensional non-interacting tidal waves. (C) 2000 Elsevier Science Ltd. All rights reserved.

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50 000 instances). It is also effective for solving the instances of problem set Cover III (almost 100 000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes. Journal of the Operational Research Society (2010) 61, 306-320. doi: 10.1057/jors.2008.141 Published online 4 February 2009

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.

Two-Dimensional Bin Packing Problem with Guillotine Restrictions

This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed. A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective. Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.

Non-covalent and covalent protein labeling in two-dimensional gel electrophoresis.

Over the past decades, several sensitive post-electrophoretic stains have been developed for an identification of proteins in general, or for a specific detection of post-translational modifications such as phosphorylation, glycosylation or oxidation. Yet, for a visualization and quantification of protein differences, the differential two-dimensional gel electrophoresis, termed DIGE, has become the method of choice for a detection of differences in two sets of proteomes. The goal of this review is to evaluate the use of the most common non-covalent and covalent staining techniques in 2D electrophoresis gels, in order to obtain maximal information per electrophoresis gel and for an identification of potential biomarkers. We will also discuss the use of detergents during covalent labeling, the identification of oxidative modifications and review influence of detergents on finger prints analysis and MS/MS identification in relation to 2D electrophoresis.

A fully adaptive numerical approximation for a two-dimensional epidemic model with nonlinear cross-diffusion

An epidemic model is formulated by a reactionâeuro"diffusion system where the spatial pattern formation is driven by cross-diffusion. The reaction terms describe the local dynamics of susceptible and infected species, whereas the diffusion terms account for the spatial distribution dynamics. For both self-diffusion and cross-diffusion, nonlinear constitutive assumptions are suggested. To simulate the pattern formation two finite volume formulations are proposed, which employ a conservative and a non-conservative discretization, respectively. An efficient simulation is obtained by a fully adaptive multiresolution strategy. Numerical examples illustrate the impact of the cross-diffusion on the pattern formation.

A numerical scheme for two-dimensional, open channel flows with non-rectangular geometries

An algorithm based on flux difference splitting is presented for the solution of two-dimensional, open channel flows. A transformation maps a non-rectangular, physical domain into a rectangular one. The governing equations are then the shallow water equations, including terms of slope and friction, in a generalized coordinate system. A regular mesh on a rectangular computational domain can then be employed. The resulting scheme has good jump capturing properties and the advantage of using boundary/body-fitted meshes. The scheme is applied to a problem of flow in a river whose geometry induces a region of supercritical flow.

Non-ergodicity of inviscid two-dimensional flow on a beta-plane and on the surface of a rotating sphere

It is shown that, for a sufficiently large value of β, two-dimensional flow on a doubly-periodic beta-plane cannot be ergodic (phase-space filling) on the phase-space surface of constant energy and enstrophy. A corresponding result holds for flow on the surface of a rotating sphere, for a sufficiently rapid rotation rate Ω. This implies that the higher-order, non-quadratic invariants are exerting a significant influence on the statistical evolution of the flow. The proof relies on the existence of a finite-amplitude Liapunov stability theorem for zonally symmetric basic states with a non-vanishing absolute-vorticity gradient. When the domain size is much larger than the size of a typical eddy, then a sufficient condition for non-ergodicity is that the wave steepness ε < 1, where ε = 2[surd radical]2Z/βU in the planar case and $\epsilon = 2^{\frac{1}{4}} a^{\frac{5}{2}}Z^{\frac{7}{4}}/\Omega U^{\frac{5}{2}}$ in the spherical case, and where Z is the enstrophy, U the r.m.s. velocity, and a the radius of the sphere. This result may help to explain why numerical simulations of unforced beta-plane turbulence (in which ε decreases in time) seem to evolve into a non-ergodic regime at large scales.

Non-Zeeman splitting for a spin-resolved STM with a Kondo adatom in a spin-polarized two-dimensional electron gas

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

The non-adiabatic hyperspherical approach to the two-dimensional D- ion in the presence of a magnetic field

We have used the adiabatic hyperspherical approach to determine the energies and wave functions of the ground state and first excited states of a two-dimensional D- ion in the presence of a magnetic field. Using a modified hyperspherical angular variable, potential energy curves are analytically obtained, allowing an accurate determination of the energy levels of this system. Upper and lower bounds for the ground-state energy have been determined by a non-adiabatic procedure, as the purpose is to improve the accuracy of method. The results are shown to be comparable to the best variational calculations reported in the literature.