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.

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

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.

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.

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.

ESTIMATING SENSORY SHELF LIFE OF CHOCOLATE AND CARROT CUPCAKES USING ACCEPTANCE TESTS

This study determined the sensory shelf life of a commercial brand of chocolate and carrot cupcakes, aiming at increasing the current 120 days of shelf life to 180. Appearance, texture, flavor and overall quality of cakes stored at six different storage times were evaluated by 102 consumers. The data were analyzed by analysis of variance and linear regression. For both flavors, the texture presented a greater loss in acceptance during the storage period, showing an acceptance mean close to indifference on the hedonic scale at 120 days. Nevertheless, appearance, flavor and overall quality stayed acceptable up to 150 days. The end of shelf life was estimated at about 161 days for chocolate cakes and 150 days for carrot cakes. This study showed that the current 120 days of shelf life can be extended to 150 days for carrot cake and to 160 days for chocolate cake. However, the 180 days of shelf life desired by the company were not achieved. PRACTICAL APPLICATIONS This research shows the adequacy of using sensory acceptance tests to determine the shelf life of two food products (chocolate and carrot cupcakes). This practical application is useful because the precise determination of the shelf life of a food product is of vital importance for its commercial success. The maximum storage time should always be evaluated in the development or reformulation of new products, changes in packing or storage conditions. Once the physical-chemical and microbiological stability of a product is guaranteed, sensorial changes that could affect consumer acceptance will determine the end of the shelf life of a food product. Thus, the use of sensitive and reliable methods to estimate the sensory shelf life of a product is very important. Findings show the importance of determining the shelf life of each product separately and to avoid using the shelf time estimated for a specific product on other, similar products.

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

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.

A coupling cutting stock-lot sizing problem in the paper industry

An important production programming problem arises in paper industries coupling multiple machine scheduling with cutting stocks. Concerning machine scheduling: how can the production of the quantity of large rolls of paper of different types be determined. These rolls are cut to meet demand of items. Scheduling that minimizes setups and production costs may produce rolls which may increase waste in the cutting process. On the other hand, the best number of rolls in the point of view of minimizing waste may lead to high setup costs. In this paper, coupled modeling and heuristic methods are proposed. Computational experiments are presented.

Liquid crystalline cellulosic elastomers: free standing anisotropic films under stretching

The structure and local ordering of 1,6-hexamethylenediisocyanate-(acetoxypropy1) cellulose (HDI-APC) liquid crystalline elastomer thin films are investigated by using X-ray diffraction and scattering techniques. Optical microscopy and mechanical essays are performed to complement the investigation. The study is performed in films subjected or not to an uniaxial stress. Our results indicate that the film is constituted by a bundle of helicoidal fiber-like structure, where the cellobiose block spins around the axis of the fiber, like a string-structure in a smectic-like packing, with the pitch defined by a smectic-like layer. The fibers are in average perpendicular to the smectic-like planes. Without the stretch, these bundles are warped, only with a residual orientation along the casting direction. The stretch orients the bundles along it, increasing the smectic-like and the nematic-like ordering of the fibers. Under stress, the network of molecules which connects the cellobiose blocs and forms the cellulosic matrix tends to organize their links in a hexagonal-like structure with lattice parameter commensurate to the smectic-like structure.

Laurdan Spectrum Decomposition as a Tool for the Analysis of Surface Bilayer Structure and Polarity: a Study with DMPG, Peptides and Cholesterol

The highly hydrophobic fluorophore Laurdan (6-dodecanoyl-2-(dimethylaminonaphthalene)) has been widely used as a fluorescent probe to monitor lipid membranes. Actually, it monitors the structure and polarity of the bilayer surface, where its fluorescent moiety is supposed to reside. The present paper discusses the high sensitivity of Laurdan fluorescence through the decomposition of its emission spectrum into two Gaussian bands, which correspond to emissions from two different excited states, one more solvent relaxed than the other. It will be shown that the analysis of the area fraction of each band is more sensitive to bilayer structural changes than the largely used parameter called Generalized Polarization, possibly because the latter does not completely separate the fluorescence emission from the two different excited states of Laurdan. Moreover, it will be shown that this decomposition should be done with the spectrum as a function of energy, and not wavelength. Due to the presence of the two emission bands in Laurdan spectrum, fluorescence anisotropy should be measured around 480 nm, to be able to monitor the fluorescence emission from one excited state only, the solvent relaxed state. Laurdan will be used to monitor the complex structure of the anionic phospholipid DMPG (dimyristoyl phosphatidylglycerol) at different ionic strengths, and the alterations caused on gel and fluid membranes due to the interaction of cationic peptides and cholesterol. Analyzing both the emission spectrum decomposition and anisotropy it was possible to distinguish between effects on the packing and on the hydration of the lipid membrane surface. It could be clearly detected that a more potent analog of the melanotropic hormone alpha-MSH (Ac-Ser(1)-Tyr(2)-Ser(3)-Met(4)-Glu(5)-His(6)-Phe(7)-Arg(8)-Trp(9)-Gly(10)-Lys(11)-Pro(12)-Val(13)-NH(2)) was more effective in rigidifying the bilayer surface of fluid membranes than the hormone, though the hormone significantly decreases the bilayer surface hydration.

DNA alters the bilayer structure of cationic lipid diC14-amidine: A spin label study

Cationic lipids-DNA complexes (lipoplexes) have been used for delivery of nucleic acids into cells in vitro and in vivo. Despite the fact that, over the last decade, significant progress in the understanding of the cellular pathways and mechanisms involved in lipoplexes-mediated gene transfection have been achieved, a convincing relationship between the structure of lipoplexes and their in vivo and in vitro transfection activity is still missing. How does DNA affect the lipid packing and what are the consequences for transfection efficiency is the point we want to address here. We investigated the bilayer organization in cationic liposomes by electron spin resonance (ESR). Phospholipids spin labeled at the 5th and 16th carbon atoms were incorporated into the DNA/diC14-amidine complex. Our data demonstrate that electrostatic interactions involved in the formation of DNA-cationic lipid complex modify the packing of the cationic lipid membrane. DNA rigidifies the amidine fluid bilayer and fluidizes the amidine rigid bilayer just below the gel-fluid transition temperature. These effects were not observed with single nucleotides and are clearly related to the repetitive charged motif present in the DNA chain and not to a charge-charge interaction. These modifications of the initial lipid packing of the cationic lipid may reorient its cellular pathway towards different routes. A better knowledge of the cationic lipid packing before and after interaction with DNA may therefore contribute to the design of lipoplexes capable to reach specific cellular targets. (c) 2009 Elsevier B.V. All rights reserved.

On the interaction of the anthraquinone barbaloin with negatively charged DMPG bilayers

Barbaloin is a bioactive glycosilated 1,8-dihydroxyanthraquinone present in several exudates from plants, Such as Aloe vera, which are used for cosmetic or food purposes. It has been shown that barbaloin interacts with DMPG (dimyristoylphosphatidylglycerol) model membranes, altering the bilayer structure (Alves, D. S.; Perez-Fons, L.; Estepa, A.; Micol, V. Biochem. Pharm. 2004, 68, 549). Considering that ESR (electron spin resonance) of spin labels is one of the best techniques to monitor structural properties at the molecular level, the alterations caused by the anthraquinone barbaloin on phospholipid bilayers will be discussed here via the ESR signal of phospholipid spin probes intercalated into the membranes. In DMPG at high ionic strength (10 mM Hepes pH 7.4 + 100 mM NaCl), a system that presents a gel-fluid transition around 23 degrees C, 20 mol % barbaloin turns the gel phase more rigid, does not alter much the fluid phase packing, but makes the lipid thermal transition less sharp. However, in a low-salt DMPG dispersion (10 mM Hepes pH 7.4 + 2 mM NaCl), which presents a rather complex gel-fluid thermal transition (Lamy-Freund, M. T.; Riske, K. A. Chem. Phys. Lipids 2003, 122, 19), barbaloin strongly affects bilayer structural properties, both in the gel and fluid phases, extending the transition region to much higher temperature values. The position of barbaloin in DMPG bilayers will be discussed on the basis of ESR results, in parallel with data from sample viscosity, DSC (differential scanning calorimetry), and SAXS (small-angle X-ray scattering).