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.

Dynamic Changes in the Mental Rotation Network Revealed by Pattern Recognition Analysis of fMRI Data

We investigated the temporal dynamics and changes in connectivity in the mental rotation network through the application of spatio-temporal support vector machines (SVMs). The spatio-temporal SVM [Mourao-Miranda, J., Friston, K. J., et al. (2007). Dynamic discrimination analysis: A spatial-temporal SVM. Neuroimage, 36, 88-99] is a pattern recognition approach that is suitable for investigating dynamic changes in the brain network during a complex mental task. It does not require a model describing each component of the task and the precise shape of the BOLD impulse response. By defining a time window including a cognitive event, one can use spatio-temporal fMRI observations from two cognitive states to train the SVM. During the training, the SVM finds the discriminating pattern between the two states and produces a discriminating weight vector encompassing both voxels and time (i.e., spatio-temporal maps). We showed that by applying spatio-temporal SVM to an event-related mental rotation experiment, it is possible to discriminate between different degrees of angular disparity (0 degrees vs. 20 degrees, 0 degrees vs. 60 degrees, and 0 degrees vs. 100 degrees), and the discrimination accuracy is correlated with the difference in angular disparity between the conditions. For the comparison with highest accuracy (08 vs. 1008), we evaluated how the most discriminating areas (visual regions, parietal regions, supplementary, and premotor areas) change their behavior over time. The frontal premotor regions became highly discriminating earlier than the superior parietal cortex. There seems to be a parcellation of the parietal regions with an earlier discrimination of the inferior parietal lobe in the mental rotation in relation to the superior parietal. The SVM also identified a network of regions that had a decrease in BOLD responses during the 100 degrees condition in relation to the 0 degrees condition (posterior cingulate, frontal, and superior temporal gyrus). This network was also highly discriminating between the two conditions. In addition, we investigated changes in functional connectivity between the most discriminating areas identified by the spatio-temporal SVM. We observed an increase in functional connectivity between almost all areas activated during the 100 degrees condition (bilateral inferior and superior parietal lobe, bilateral premotor area, and SMA) but not between the areas that showed a decrease in BOLD response during the 100 degrees condition.

Bioluminescent sensor for naphthalene in air: Cell immobilization and evaluation with a dynamic standard atmosphere generator

A dynamic atmosphere generator with a naphthalene emission source has been constructed and used for the development and evaluation of a bioluminescence sensor based on the bacteria Pseudomonas fluorescens HK44 immobilized in 2% agar gel (101 cell mL(-1)) placed in sampling tubes. A steady naphthalene emission rate (around 7.3 nmol min(-1) at 27 degrees C and 7.4 mLmin(-1) of purified air) was obtained by covering the diffusion unit containing solid naphthalene with a PTFE filter membrane. The time elapsed from gelation of the agar matrix to analyte exposure (""maturation time"") was found relevant for the bioluminescence assays, being most favorable between 1.5 and 3 h. The maximum light emission, observed after 80 min, is dependent on the analyte concentration and the exposure time (evaluated between 5 and 20 min), but not on the flow rate of naphthalene in the sampling tube, over the range of 1.8-7.4 nmol min(-1). A good linear response was obtained between 50 and 260 nmol L-1 with a limit of detection estimated in 20 nmol L-1 far below the recommended threshold limit value for naphthalene in air. (c) 2008 Elsevier B.V. All rights reserved.

Sample stacking in CZE using dynamic thermal junctions I. Analytes with low dpK(a)/dT crossing a single thermally induced pH junction in a BGE with high dpH/dT

The possibility to compress analyte bands at the beginning of CE runs has many advantages. Analytes at low concentration can be analyzed with high signal-to-noise ratios by using the so-called sample stacking methods. Moreover, sample injections with very narrow initial band widths (small initial standard deviations) are sometimes useful, especially if high resolutions among the bands are required in the shortest run time. In the present work, a method of sample stacking is proposed and demonstrated. It is based on BGEs with high thermal sensitive pHs (high dpH/dT) and analytes with low dpK(a)/dT. High thermal sensitivity means that the working pK(a) of the BGE has a high dpK(a)/dT in modulus. For instance, Tris and Ethanolamine have dpH/dT = -0.028/degrees C and -0.029/degrees C, respectively, whereas carboxylic acids have low dpK(a)/dT values, i.e. in the -0.002/degrees C to+0.002/degrees C range. The action of cooling and heating sections along the capillary during the runs affects also the local viscosity, conductivity, and electric field strength. The effect of these variables on electrophoretic velocity and band compression is theoretically calculated using a simple model. Finally, this stacking method was demonstrated for amino acids derivatized with naphthalene-2,3-dicarboxaldehyde and fluorescamine using a temperature difference of 70 degrees C between two neighbor sections and Tris as separation buffer. In this case, the BGE has a high pH thermal coefficient whereas the carboxylic groups of the analytes have low pK(a) thermal coefficients. The application of these dynamic thermal gradients increased peak height by a factor of two (and decreased the standard deviations of peaks by a factor of two) of aspartic acid and glutamic acid derivatized with naphthalene-2,3-dicarboxaldehyde and serine derivatized with fluorescamine. The effect of thermal compression of bands was not observed when runs were accomplished using phosphate buffer at pH 7 (negative control). Phosphate has a low dpH/dT in this pH range, similar to the dK(a)/dT of analytes. It is shown that vertical bar dK(a)/dT-dpH/dT vertical bar >> 0 is one determinant factor to have significant stacking produced by dynamic thermal junctions.

Real-Time Flood Forecasting Systems In Flanders

As a highly urbanized and flood prone region, Flanders has experienced multiple floods causing significant damage in the past. In response to the floods of 1998 and 2002 the Flemish Environment Agency, responsible for managing 1 400 km of unnavigable rivers, started setting up a real time flood forecasting system in 2003. Currently the system covers almost 2 000 km of unnavigable rivers, for which flood forecasts are accessible online (www.waterinfo.be). The forecasting system comprises more than 1 000 hydrologic and 50 hydrodynamic models which are supplied with radar rainfall, rainfall forecasts and on-site observations. Forecasts for the next 2 days are generated hourly, while 10 day forecasts are generated twice a day. Additionally, twice daily simulations based on percentile rainfall forecasts (from EPS predictions) result in uncertainty bands for the latter. Subsequent flood forecasts use the most recent rainfall predictions and observed parameters at any time while uncertainty on the longer-term is taken into account. The flood forecasting system produces high resolution dynamic flood maps and graphs at about 200 river gauges and more than 3 000 forecast points. A customized emergency response system generates phone calls and text messages to a team of hydrologists initiating a pro-active response to prevent upcoming flood damage. The flood forecasting system of the Flemish Environment Agency is constantly evolving and has proven to be an indispensable tool in flood crisis management. This was clearly the case during the November 2010 floods, when the agency issued a press release 2 days in advance allowing water managers, emergency services and civilians to take measures.

A study on time-varying quantile and its applications

This Thesis is the result of my Master Degree studies at the Graduate School of Economics, Getúlio Vargas Foundation, from January 2004 to August 2006. am indebted to my Thesis Advisor, Professor Luiz Renato Lima, who introduced me to the Econometrics' world. In this Thesis, we study time-varying quantile process and we develop two applications, which are presented here as Part and Part II. Each of these parts was transformed in paper. Both papers were submitted. Part shows that asymmetric persistence induces ARCH effects, but the LMARCH test has power against it. On the other hand, the test for asymmetric dynamics proposed by Koenker and Xiao (2004) has correct size under the presence of ARCH errors. These results suggest that the LM-ARCH and the Koenker-Xiao tests may be used in applied research as complementary tools. In the Part II, we compare four different Value-at-Risk (VaR) methodologies through Monte Cario experiments. Our results indicate that the method based on quantile regression with ARCH effect dominates other methods that require distributional assumption. In particular, we show that the non-robust method ologies have higher probability to predict VaRs with too many violations. We illustrate our findings with an empirical exercise in which we estimate VaR for returns of São Paulo stock exchange index, IBOVESPA, during periods of market turmoil. Our results indicate that the robust method based on quantile regression presents the least number of violations.

Solving the non-convexity problem in some shopping-time and human-capital models

Several works in the shopping-time and in the human-capital literature, due to the nonconcavity of the underlying Hamiltonian, use Örst-order conditions in dynamic optimization to characterize necessity, but not su¢ ciency, in intertemporal problems. In this work I choose one paper in each one of these two areas and show that optimality can be characterized by means of a simple aplication of Arrowís (1968) su¢ ciency theorem.

Um estudo da gênese das dynamic capabilities: o caso da tecnologia bancária no Brasil

Este trabalho analisa o desenvolvimento de dynamic capabilities em um contexto de turbulência institucional, diferente das condições em que esta perspectiva teórica costuma ser estudada. É feito um estudo de caso histórico e processual que analisa o surgimento das Dynamic Capabilities nos bancos brasileiros, a partir do desenvolvimento da tecnologia bancária que se deu entre os anos 1960 e 1990. Baseando-se nas proposições da Estratégia que analisam as vantagens competitivas das empresas através de seus recursos, conhecimentos e Dynamic Capabilities, é construído um framework com o qual são analisados diversos depoimentos dados ao livro “Tecnologia bancária no Brasil: uma história de conquistas, uma visão de futuro” (FONSECA; MEIRELLES; DINIZ, 2010) e em entrevistas feitas para este trabalho. Os depoimentos mostram que os bancos fizeram fortes investimentos em tecnologia a partir da reforma financeira de 1964, época em que se iniciou uma sequência de períodos com características próprias do ponto de vista institucional. Conforme as condições mudavam a cada período, os bancos também mudavam seu processo de informatização. No início, os projetos eram executados ad hoc, sob o comando direto dos líderes dos bancos. Com o tempo, à medida que a tecnologia evoluía, a infraestrutura tecnológica crescia e surgiam turbulências institucionais, os bancos progressivamente desenvolveram parcerias entre si e com fornecedores locais, descentralizaram a área de tecnologia, tornaram-se mais flexíveis, fortaleceram a governança corporativa e adotaram uma série de rotinas para cuidar da informática, o que levou ao desenvolvimento gradual das microfundações das Dynamic Capabilties nesses períodos. Em meados dos anos 1990 ocorreram a estabilização institucional e a abertura da economia à concorrência estrangeira, e assim o país colocou-se nas condições que a perspectiva teórica adotada considera ideais para que as Dynamic Capabilities sejam fontes de vantagem competitiva. Os bancos brasileiros mostraram-se preparados para enfrentar essa nova fase, o que é uma evidência de que eles haviam desenvolvido Dynamic Capabilities nas décadas precedentes, sendo que parte desse desenvolvimento podia ser atribuído às turbulências institucionais que eles haviam enfrentado.

A time-varying markov-switching model for economic growth

This paper investigates economic growth’s pattern of variation across and within countries using a Time-Varying Transition Matrix Markov-Switching Approach. The model developed follows the approach of Pritchett (2003) and explains the dynamics of growth based on a collection of different states, each of which has a sub-model and a growth pattern, by which countries oscillate over time. The transition matrix among the different states varies over time, depending on the conditioning variables of each country, with a linear dynamic for each state. We develop a generalization of the Diebold’s EM Algorithm and estimate an example model in a panel with a transition matrix conditioned on the quality of the institutions and the level of investment. We found three states of growth: stable growth, miraculous growth, and stagnation. The results show that the quality of the institutions is an important determinant of long-term growth, whereas the level of investment has varying roles in that it contributes positively in countries with high-quality institutions but is of little relevance in countries with medium- or poor-quality institutions.

Development of a dynamic headspace solid-phase microextraction procedure coupled to GC–qMSD for evaluation the chemical profile in alcoholic beverages

In the present study, a simple and sensitive methodology based on dynamic headspace solid-phase microextraction (HS-SPME) followed by thermal desorption gas chromatography with quadrupole mass detection (GC–qMSD), was developed and optimized for the determination of volatile (VOCs) and semi-volatile (SVOCs) compounds from different alcoholic beverages: wine, beer and whisky. Key experimental factors influencing the equilibrium of the VOCs and SVOCs between the sample and the SPME fibre, as the type of fibre coating, extraction time and temperature, sample stirring and ionic strength, were optimized. The performance of five commercially available SPME fibres was evaluated and compared, namely polydimethylsiloxane (PDMS, 100 μm); polyacrylate (PA, 85 μm); polydimethylsiloxane/divinylbenzene (PDMS/DVB, 65 μm); carboxen™/polydimethylsiloxane (CAR/PDMS, 75 μm) and the divinylbenzene/carboxen on polydimethylsiloxane (DVB/CAR/PDMS, 50/30 μm) (StableFlex). An objective comparison among different alcoholic beverages has been established in terms of qualitative and semi-quantitative differences on volatile and semi-volatile compounds. These compounds belong to several chemical families, including higher alcohols, ethyl esters, fatty acids, higher alcohol acetates, isoamyl esters, carbonyl compounds, furanic compounds, terpenoids, C13-norisoprenoids and volatile phenols. The optimized extraction conditions and GC–qMSD, lead to the successful identification of 44 compounds in white wines, 64 in beers and 104 in whiskys. Some of these compounds were found in all of the examined beverage samples. The main components of the HS-SPME found in white wines were ethyl octanoate (46.9%), ethyl decanoate (30.3%), ethyl 9-decenoate (10.7%), ethyl hexanoate (3.1%), and isoamyl octanoate (2.7%). As for beers, the major compounds were isoamyl alcohol (11.5%), ethyl octanoate (9.1%), isoamyl acetate (8.2%), 2-ethyl-1-hexanol (5.9%), and octanoic acid (5.5%). Ethyl decanoate (58.0%), ethyl octanoate (15.1%), ethyl dodecanoate (13.9%) followed by 3-methyl-1-butanol (1.8%) and isoamyl acetate (1.4%) were found to be the major VOCs in whisky samples.

Volatile flavour constituent patterns of terras madeirenses red wines extracted by dynamic headspace solid‐phase microextraction

A suitable analytical procedure based on static headspace solid-phase microextraction (SPME) followed by thermal desorption gas chromatography–ion trap mass spectrometry detection (GC–ITDMS), was developed and applied for the qualitative and semi-quantitative analysis of volatile components of Portuguese Terras Madeirenses red wines. The headspace SPME method was optimised in terms of fibre coating, extraction time, and extraction temperature. The performance of three commercially available SPME fibres, viz. 100 lm polydimethylsiloxane; 85 lm polyacrylate, PA; and 50/30 lm divinylbenzene/carboxen on polydimethylsiloxane, was evaluated and compared. The highest amounts extracted, in terms of the maximum signal recorded for the total volatile composition, were obtained with a PA coating fibre at 308C during an extraction time of 60 min with a constant stirring at 750 rpm, after saturation of the sample with NaCl (30%, w/v). More than sixty volatile compounds, belonging to different biosynthetic pathways, have been identified, including fatty acid ethyl esters, higher alcohols, fatty acids, higher alcohol acetates, isoamyl esters, carbonyl compounds, and monoterpenols/C13-norisoprenoids.

Dynamic headspace solid-phase microextraction combined with one-dimensional gas chromatography–mass spectrometry as a powerful tool to differentiate banana cultivars based on their volatile metabolite profile

In this study the effect of the cultivar on the volatile profile of five different banana varieties was evaluated and determined by dynamic headspace solid-phase microextraction (dHS-SPME) combined with one-dimensional gas chromatography–mass spectrometry (1D-GC–qMS). This approach allowed the definition of a volatile metabolite profile to each banana variety and can be used as pertinent criteria of differentiation. The investigated banana varieties (Dwarf Cavendish, Prata, Maçã, Ouro and Platano) have certified botanical origin and belong to the Musaceae family, the most common genomic group cultivated in Madeira Island (Portugal). The influence of dHS-SPME experimental factors, namely, fibre coating, extraction time and extraction temperature, on the equilibrium headspace analysis was investigated and optimised using univariate optimisation design. A total of 68 volatile organic metabolites (VOMs) were tentatively identified and used to profile the volatile composition in different banana cultivars, thus emphasising the sensitivity and applicability of SPME for establishment of the volatile metabolomic pattern of plant secondary metabolites. Ethyl esters were found to comprise the largest chemical class accounting 80.9%, 86.5%, 51.2%, 90.1% and 6.1% of total peak area for Dwarf Cavendish, Prata, Ouro, Maçã and Platano volatile fraction, respectively. Gas chromatographic peak areas were submitted to multivariate statistical analysis (principal component and stepwise linear discriminant analysis) in order to visualise clusters within samples and to detect the volatile metabolites able to differentiate banana cultivars. The application of the multivariate analysis on the VOMs data set resulted in predictive abilities of 90% as evaluated by the cross-validation procedure.

Stochastic simulation of time-series models combined with geostatistics to predict water-table scenarios in a Guarani Aquifer System outcrop area, Brazil

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Effect of steeping conditions (sulfur dioxide, lactic acid, and temperature) on starch yield, starch quality, and germ quality from the Intermittent Milling and Dynamic Steeping process (IMDS) for a Brazilian corn hybrid

Effect of lactic acid, SO2, temperature, and their interactions were assessed on the dynamic steeping of a Brazilian dent corn (hybrid XL 606) to determine the ideal relationship among these variables to improve the wet-milling process for starch and corn by-products production. A 2x2x3 factorial experimental design was used with SO2 levels of 0.05 and 0.1% (w/v), lactic acid levels of 0 and 0.5% (v/v), and temperatures of 52, 60, and 68degreesC. Starch yield was used as deciding factor to choose the best treatment. Lactic acid added in the steep solution improved the starch yield by an average of 5.6 percentage points. SO2 was more available to break down the structural protein network at 0.1% than at the 0.05% level. Starch-gluten separation was difficult at 68degreesC. The lactic acid and SO2 concentrations and steeping temperatures for better starch recovery were 0.5, 0.1, and 52degreesC, respectively. The Intermittent Milling and Dynamic Steeping (IMDS) process produced, on average, 1.4% more starch than the conventional 36- hr steeping process. Protein in starch, oil content in germ, and germ damage were used as quality factors. Total steep time can be reduced from 36 hr for conventional wet-milling to 8 hr for the IMDS process.