Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

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.

Deformed Gaussian-orthogonal-ensemble description of small-world networks

The study of spectral behavior of networks has gained enthusiasm over the last few years. In particular, random matrix theory (RMT) concepts have proven to be useful. In discussing transition from regular behavior to fully chaotic behavior it has been found that an extrapolation formula of the Brody type can be used. In the present paper we analyze the regular to chaotic behavior of small world (SW) networks using an extension of the Gaussian orthogonal ensemble. This RMT ensemble, coined the deformed Gaussian orthogonal ensemble (DGOE), supplies a natural foundation of the Brody formula. SW networks follow GOE statistics until a certain range of eigenvalue correlations depending upon the strength of random connections. We show that for these regimes of SW networks where spectral correlations do not follow GOE beyond a certain range, DGOE statistics models the correlations very well. The analysis performed in this paper proves the utility of the DGOE in network physics, as much as it has been useful in other physical systems.

LEACHATE TREATMENT PROCESS AT A MUNICIPAL STABILIZED LANDFILL BY CATALYTIC OZONATION: AN EXPLORATORY STUDY FROM TAGUCHI ORTHOGONAL ARRAY

Catalytic ozonation has been recognized in the scientific community as an efficient technique, reaching elevated rates of recalcitrant organic material mineralization, even at the presence of scavenger species of hydroxyl free radicals. This study presents the most significant factors involving the leachate treatment stabilized by the municipal landfill of the city of Guaratingueta, State of Sao Paulo, Brazil, by using a catalytic ozonation activated by metallic ions Fe(3+), Zn(2+), Mn(2+), Ni(2+) and Cr(3+). The Taguchi L(16) orthogonal array and its associated statistical methods were also used in this study. Among the researched ions, the most notable catalysis was obtained with ferric ion, statistically significant in the reduction of COD with a confidence level of 99.5%.

Performance evaluation of packing materials in the removal of hydrogen sulphide in gas-phase biofilters: Polyurethane foam, sugarcane bagasse, and coconut fibre

The main objective of this work was to investigate three packing materials (polyurethane foam, sugar-cane bagasse, and coconut fibre) for biofiltration of a gaseous mixture containing hydrogen sulphide (H(2)S). Mixed cultures were obtained from two sources, aerated submerged biofilters and activated sludge, and were utilised as inoculums. Biofilters reached 100% removal efficiency after two clays of operation. The empty bed residence time was 495 for each of the biofilters. The reactors were operated simultaneously, and the inlet concentrations of H(2)S varied between 184 and 644 ppmv during the long-term continuous operation of the biofilters (100 clays). Average removal efficiencies remained above 99.3%, taking into consideration the entire period of operation. Average elimination capacities reached by the biofilters packed with polyurethane foam, coconut fibre, and sugarcane bagasse were in the range of 17.8-66.6; 18.9-68.8, and 18.7-72.9g m(-3) h(-1), respectively. Finally, we concluded that the packing materials tested in this work are appropriate for the long-term biofiltration of hydrogen sulphide. (C) 2010 Elsevier B.V. All rights reserved.

Replacement of Trays by Packing To Increase the Absorption Capacity of Acetone during Cellulose Acetate Spinning

All textile uses of cellulose acetate involve acetone recovery, which, because of safety issues, results in large installations, in order to work with dilute streams. This compromises the efficiency of all of the involved unit operations, in this case, acetone absorption in cold water, acetone distillation, and water chilling, making them more expensive. The present article proposes the improvement of the absorption of acetone in water, traditionally performed with sieve trays, by using structured packing instead. The advantageous implementation was enabled through the utilization of a calculation methodology based on concepts of thermodynamic equilibrium of the binary acetone/water system and empirical relations that allow the evaluation of the hydrodynamics of the proposed modification.

New and improved results for packing identical unitary radius circles within triangles, rectangles and strips

The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of non-linear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/similar to egbirgin/packing/. (C) 2009 Elsevier 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

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.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. 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.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Polar orthogonal representations of real reductive algebraic groups

We prove that a polar orthogonal representation of a real reductive algebraic group has the same closed orbits as the isotropy representation of a pseudo-Riemannian symmetric space. We also develop a partial structural theory of polar orthogonal representations of real reductive algebraic groups which slightly generalizes some results of the structural theory of real reductive Lie algebras. (c) 2008 Elsevier Inc. All rights reserved.

Existence of orthogonal geodesic chords on Riemannian manifolds with concave boundary and homeomorphic to the N-dimensional disk

In this paper we give a proof of the existence of an orthogonal geodesic chord on a Riemannian manifold homeomorphic to a closed disk and with concave boundary. This kind of study is motivated by the link (proved in Giambo et al. (2005) [8]) of the multiplicity problem with the famous Seifert conjecture (formulated in Seifert (1948) [1]) about multiple brake orbits for a class of Hamiltonian systems at a fixed energy level. (C) 2010 Elsevier Ltd. All rights reserved.

On the Multiplicity of Orthogonal Geodesics in Riemannian Manifold With Concave Boundary. Applications to Brake Orbits and Homoclinics

Let (M, g) be a complete Riemannian Manifold, Omega subset of M an open subset whose closure is diffeomorphic to an annulus. If partial derivative Omega is smooth and it satisfies a strong concavity assumption, then it is possible to prove that there are at least two geometrically distinct geodesics in (Omega) over bar = Omega boolean OR partial derivative Omega starting orthogonally to one connected component of partial derivative Omega and arriving orthogonally onto the other one. The results given in [6] allow to obtain a proof of the existence of two distinct homoclinic orbits for an autonomous Lagrangian system emanating from a nondegenerate maximum point of the potential energy, and a proof of the existence of two distinct brake orbits for a. class of Hamiltonian systems. Under a further symmetry assumption, it is possible to show the existence of at least dim(M) pairs of geometrically distinct geodesics as above, brake orbits and homoclinics.