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.

Density-Profile Processes Describing Biological Signaling Networks: Almost Sure Convergence to Deterministic Trajectories

We introduce jump processes in R(k), called density-profile processes, to model biological signaling networks. Our modeling setup describes the macroscopic evolution of a finite-size spin-flip model with k types of spins with arbitrary number of internal states interacting through a non-reversible stochastic dynamics. We are mostly interested on the multi-dimensional empirical-magnetization vector in the thermodynamic limit, and prove that, within arbitrary finite time-intervals, its path converges almost surely to a deterministic trajectory determined by a first-order (non-linear) differential equation with explicit bounds on the distance between the stochastic and deterministic trajectories. As parameters of the spin-flip dynamics change, the associated dynamical system may go through bifurcations, associated to phase transitions in the statistical mechanical setting. We present a simple example of spin-flip stochastic model, associated to a synthetic biology model known as repressilator, which leads to a dynamical system with Hopf and pitchfork bifurcations. Depending on the parameter values, the magnetization random path can either converge to a unique stable fixed point, converge to one of a pair of stable fixed points, or asymptotically evolve close to a deterministic orbit in Rk. We also discuss a simple signaling pathway related to cancer research, called p53 module.

Comparison of three vascular endothelial markers in the evaluation of microvessel density in breast cancer

Purpose: To evaluate the microvessel density by comparing the performance of anti-factor VIII-related antigen, anti-CD31 and, anti-CD34 monoclonal antibodies in breast cancer. Methods: Twenty-three postmenopausal women diagnosed with Stage II breast cancer submitted to definitive surgical treatment were evaluated. The monoclonal antibodies used were anti-factor VIII, anti-CD31 and anti-CD34. Microvessels were counted in the areas of highest microvessel density in ten random fields (200 x). The data were analyzed using the Kruskal-Wallis nonparametric test (p < 0.05). Results: Mean microvessel densities with anti-factor VIII, anti-CD31 and anti-CD34 were 4.16 +/- 0.38, 4.09 +/- 0.23 and 6.59 +/- 0.42, respectively. Microvessel density as assessed by anti-CD34 was significantly greater than that detected by anti-CD31 or anti-factor VIII (p < 0.0001). There was no statistically significant difference between anti-CD31 and anti-factor VIII (p = 0.4889). Conclusion: The density of stained microvessels was greater and staining was more intense with anti-CD34 compared to anti-CD31 and anti-factor VII-related antigen.

Bayesian density estimation using Skew Student-t-Normal mixtures

We present a Bayesian approach for modeling heterogeneous data and estimate multimodal densities using mixtures of Skew Student-t-Normal distributions [Gomez, H.W., Venegas, O., Bolfarine, H., 2007. Skew-symmetric distributions generated by the distribution function of the normal distribution. Environmetrics 18, 395-407]. A stochastic representation that is useful for implementing a MCMC-type algorithm and results about existence of posterior moments are obtained. Marginal likelihood approximations are obtained, in order to compare mixture models with different number of component densities. Data sets concerning the Gross Domestic Product per capita (Human Development Report) and body mass index (National Health and Nutrition Examination Survey), previously studied in the related literature, are analyzed. (c) 2008 Elsevier B.V. All rights reserved.

An indecomposable Banach space of continuous functions which has small density

Using the method of forcing we construct a model for ZFC where CH does not hold and where there exists a connected compact topological space K of weight omega(1) < 2(omega) such that every operator on the Banach space of continuous functions on K is multiplication by a continuous function plus a weakly compact operator. In particular, the Banach space of continuous functions on K is indecomposable.

Detailed analysis of the charge transfer complex N,N-dimethylaniline-SO(2) by Raman spectroscopy and density functional theory calculations

Although the amine sulfur dioxide chemistry was well characterized in the past both experimentally and theoretically, no systematic Raman spectroscopic study describes the interaction between N,N-dimethylaniline (DMA) and sulfur dioxide (SO(2)). The formation of a deep red oil by the reaction of SO(2) with DMA is an evidence of the charge transfer (CT) nature of the DMA-SO(2) interaction. The DMA -SO(2) normal Raman spectrum shows the appearance of two intense bands at 1110 and 1151 cm(-1), which are enhanced when resonance is approached. These bands are assigned to nu(s)(SO(2)) and nu(phi-N) vibrational modes, respectively, confirming the interaction between SO(2) and the amine via the nitrogen atom. The dimethyl group steric effect favors the interaction of SO(2) with the ring pi electrons, which gives rise to a pi-pi* low-energy CT electronic transition, as confirmed by time-dependent density functional theory (TDDFT) calculations. In addition, the calculated Raman DMA-SO(2) spectrum at the B3LYP/6-311++g(3df,3pd) level shows good agreement with the experimental results (vibrational wavenumbers and relative intensities), allowing a complete assignment of the vibrational modes. A better understanding of the intermolecular interactions in this model system can be extremely useful in designing new materials to absorb, detect, or even quantify SO(2). Copyright (C) 2009 John Wiley & Sons, Ltd.

Spectroscopic and theoretical studies of some N,N-diethyl-2-[(4 `-substituted)phenylsulfonyl]acetamides

The analysis of the IR carbonyl band of the N,N-diethyl-2-[(4`-substituted)phenylsulfonyl]acetamides Et(2)NC(O)CH(2)S(O)(2)-C(6)H(4)-Y (Y = OMe 1, Me 2,1-13, Cl 4, Br 5, NO(2) 6) supported by B3LYP/6-31G(d,p) calculations for 3, indicated the existence of three pairs (anti and syn) of cis (c) and gauche (g(1) and g(2)) conformers in the gas phase, being the gauche conformers significantly more stable than the cis ones. The anti geometry is more stable than the syn one, for each pair of cis and gauche conformers. The summing up of the orbital (NBO analysis) and electrostatic interactions justifies quite well the populations and the v(CO) frequencies of the anti and syn pairs of c, g(1) and g(2) conformers. The IR higher carbonyl frequency component whose population is ca. 10%, in CCl(4), may be ascribed to the least stable and most polar cis conformer pair (in the gas phase) and the lower frequency component whose population is ca. 90%, to the summing up of the populations of the two most stable and least polar gauche conformer pairs (g(1) and g(2)) (in the gas phase). The reversal of the cis(c)/gauche (g(1) + g(2)) population ratio observed in chloroform ca. 60% (cis)/40% (gauche) and the occurrence of the most polar cis(c) conformer only, in acetonitrile, strongly suggests the coalescence of the two gauche components in a unique carbonyl band in solution. A further support to this rationalization is given by the single point PCM solvation model performed by HF/6-31G(d,p) method, which showed a progressive increase of the c/(g(1) + g(2)) ratio going from gas to CCl(4), to CHCl(3) and to CH(3)CN. X-ray single crystal analysis of 4 indicates that this compound assumes, in the solid state, the syn-clinal (gauche) conformation with respect to the [O=C-CH(2)-S] moiety, and the most stable anti geometry relative to the [C(O)N(CH(2)CH(3))(2)] fragment. In order to obtain larger energy gain from the crystal packing the molecules of 4 are linked in centrosymmetric dimers through two C-H center dot center dot center dot O interactions (C-H([O-Ph])center dot center dot center dot O([SO2])) forming a step ladder. (C) 2011 Elsevier B.V. All rights reserved.

FT-Raman, FTIR and density functional theory studies of a hydrogen-bonded formamide: pyridine complex

Raman and IR experiments have been carried out on formamide (FA) and pyridine (Py) mixtures at different compositions. The appearance of a new Raman band at 996 cm(-1) (nu(1) region of Py), whose intensity depends on the FA concentration, is assigned to an FA: Py adduct and this result is in excellent agreement with those of other authors who employed noisy light-based coherent Raman scattering spectroscopy (I((2)) CARS). Another band at 1587 cm(-1) (nu(8) region of Py) has been observed for the first time by using Raman and IR spectroscopies. Its intensity shows the same dependence on the FA concentration and this fact allows us to also attribute it to an FA: Py adduct. The good relationship between the Raman and IR data demonstrates the potential of the vibrational spectroscopy for this kind of study. Owing to higher absolute Raman scattering cross section, the nu(1) region of Py has been chosen for the quantitative analysis and a stoichiometry of 1 : 1 FA: Py is reported. The experimental data are very well supported by the density functional theory (OFT) calculation, which was employed for the first time to the present system. Furthermore, the actual investigation shows an excellent agreement with those reported from computational calculations for similar systems. A comparison with our previous studies confirms that: the solvent dielectric constant determines the stoichiometry of a given Lewis acid-base adduct in the infinite dilution limit. Copyright (C) 2009 John Wiley & Sons, Ltd.

Surface esterification of cellulose fibres: Processing and characterisation of low-density polyethylene/cellulose fibres composites

Low-density polyethylene was filled with cellulose fibres from sugar cane bagasse obtained from organosolv/supercritical carbon dioxide pulping process. The fibres were also used after chemical modification with octadecanoyl and dodecanoyl chloride acids. The morphology, thermal properties, mechanical properties in both the linear and nonlinear range, and the water absorption behaviour of ensuing composites were tested. The evidence of occurrence of the chemical modification was checked by X-ray photoelectron spectrometry. The degree of polymerisation of the fibres and their intrinsic properties (zero tensile strength) were determined. It clearly appeared that the surface chemical modification of cellulose fibres resulted in improved interfacial adhesion with the matrix and higher dispersion level. However, composites did not show improved mechanical performances when compared to unmodified fibres. This surprising result was ascribed to the strong lowering of the degree of polymerisation of cellulose fibres (as confirmed by the drastic decrease of their zero tensile strength) after chemical treatment despite the mild conditions used. (c) 2007 Elsevier Ltd. All rights reserved.

Axial ligand influence on geometries, charge distributions and electronic structures of iron tetraazamacrocycle [Fe((II))TIM(X)(Y)](2+) complexes assessed by Density Functional Theory

We employed the Density Functional Theory along with small basis sets, B3LYP/LANL2DZ, for the study of FeTIM complexes with different pairs of axial ligands (CO, H(2)O, NH(3), imidazole and CH(3)CN). These calculations did not result in relevant changes of molecular quantities as bond lengths, vibrational frequencies and electronic populations supporting any significant back-donation to the carbonyl or acetonitrile axial ligands. Moreover, a back-donation mechanism to the macrocycle cannot be used to explain the observed changes in molecular properties along these complexes with CO or CH(3)CN. This work also indicates that complexes with CO show smaller binding energies and are less stable than complexes with CH(3)CN. Further, the electronic band with the largest intensity in the visible region (or close to this region) is associated to the transition from an occupied 3d orbital on iron to an empty pi* orbital located at the macrocycle. The energy of this Metal-to-Ligand Charge Transfer (MLCT) transition shows a linear relation to the total charge of the macrocycle in these complexes as given by Mulliken or Natural Population Analysis (NPA) formalisms. Finally, the macrocycle total charge seems to be influenced by the field induced by the axial ligands. (C) 2011 Elsevier Ltd. All rights reserved.

Solvent assisted decomposition of the tetrahedral intermediate of the transesterification reaction to biodiesel production. A density functional study

B3LYP/6-31 + G(d) calculations were employed to investigate the mechanism of the transesterification reaction between a model monoglyceride and the methoxide and ethoxide anions. The gas-phase results reveal that both reactions have essentially the same activation energy (5.9 kcal mol(-1)) for decomposition of the key tetrahedral intermediate. Solvent effects were included by means of both microsolvation and the polarizable continuum solvation model CPCM. Both solvent approaches reduce the activation energy, however, only the microsolvation model is able to introduce some differentiation between methanol and ethanol, yielding a lower activation energy for decomposition of the tetrahedral intermediate in the reaction with methanol (1.1 kcal mol(-1)) than for the corresponding reaction with ethanol (2.8 kcal mol(-1)), in line with experimental evidences. Analysis of the individual energy components within the CPCM approach reveals that electrostatic interactions are the main contribution to stabilization of the transition state. (C) 2009 Elsevier Ltd. All rights reserved.