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.

An algorithm for automatic checking of exercises in a dynamic geometry system: iGeom

One of the key issues in e-learning environments is the possibility of creating and evaluating exercises. However, the lack of tools supporting the authoring and automatic checking of exercises for specifics topics (e.g., geometry) drastically reduces advantages in the use of e-learning environments on a larger scale, as usually happens in Brazil. This paper describes an algorithm, and a tool based on it, designed for the authoring and automatic checking of geometry exercises. The algorithm dynamically compares the distances between the geometric objects of the student`s solution and the template`s solution, provided by the author of the exercise. Each solution is a geometric construction which is considered a function receiving geometric objects (input) and returning other geometric objects (output). Thus, for a given problem, if we know one function (construction) that solves the problem, we can compare it to any other function to check whether they are equivalent or not. Two functions are equivalent if, and only if, they have the same output when the same input is applied. If the student`s solution is equivalent to the template`s solution, then we consider the student`s solution as a correct solution. Our software utility provides both authoring and checking tools to work directly on the Internet, together with learning management systems. These tools are implemented using the dynamic geometry software, iGeom, which has been used in a geometry course since 2004 and has a successful track record in the classroom. Empowered with these new features, iGeom simplifies teachers` tasks, solves non-trivial problems in student solutions and helps to increase student motivation by providing feedback in real time. (c) 2008 Elsevier Ltd. 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.

Decay of geometry for Fibonacci critical covering maps of the circle

We study the growth of Df `` (f(c)) when f is a Fibonacci critical covering map of the circle with negative Schwarzian derivative, degree d >= 2 and critical point c of order l > 1. As an application we prove that f exhibits exponential decay of geometry if and only if l <= 2, and in this case it has an absolutely continuous invariant probability measure, although not satisfying the so-called Collet-Eckmann condition. (C) 2009 Elsevier Masson SAS. All rights reserved.

Periodic geodesics and geometry of compact Lorentzian manifolds with a Killing vector field

We study the geometry and the periodic geodesics of a compact Lorentzian manifold that has a Killing vector field which is timelike somewhere. Using a compactness argument for subgroups of the isometry group, we prove the existence of one timelike non self-intersecting periodic geodesic. If the Killing vector field is nowhere vanishing, then there are at least two distinct periodic geodesics; as a special case, compact stationary manifolds have at least two periodic timelike geodesics. We also discuss some properties of the topology of such manifolds. In particular, we show that a compact manifold M admits a Lorentzian metric with a nowhere vanishing Killing vector field which is timelike somewhere if and only if M admits a smooth circle action without fixed points.

COMPARISON RESULTS FOR CONJUGATE AND FOCAL POINTS IN SEMI-RIEMANNIAN GEOMETRY VIA MASLOV INDEX

We prove an estimate on the difference of Maslov indices relative to the choice of two distinct reference Lagrangians of a continuous path in the Lagrangian Grassmannian of a symplectic space. We discuss some applications to the study of conjugate and focal points along a geodesic in a semi-Riemannian manifold.

Understanding the Effect of Adsorption Geometry over Substrate Selectivity in the Surface-Enhanced Raman Scattering Spectra of Simazine and Atrazine

This paper studies the selectivity of Well-defined Au and Ag nanostructures as substrates for the SERS, (surface-enhanced Raman scattering) detection of simazine (6-chloro-N,N`-diethyl-1,3,5-triazine-2,4-diamine) and atrazine (6-chloro-N-ethyl-N`-isopropyl-1,3,5-triazine-2,4-diamine). Our data showed that simazine and atrazine displayed similar SERS spectra when the Au was employed as substrate. Conversely, distinct SERS signatures were obtained upon the utilization of Ag substrates. Density functional theory (DFT) calculations and vibrational assignments suggested that, while simazine and atrazine adsorbed on Au via the N3 position of the triazine ring, simazine adsorbed on Ag via N3 and atrazine via N5. The results presented herein demonstrated that the adsorption geometry of analyte molecules can play a central role over substrate selectivity in SERS, which is particularly important in applications involving ultrasensitive analysis of mixtures containing structurally similar molecules.

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.