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.

Skovgaard`s adjustment to likelihood ratio tests in exponential family nonlinear models

Likelihood ratio tests can be substantially size distorted in small- and moderate-sized samples. In this paper, we apply Skovgaard`s [Skovgaard, I.M., 2001. Likelihood asymptotics. Scandinavian journal of Statistics 28, 3-321] adjusted likelihood ratio statistic to exponential family nonlinear models. We show that the adjustment term has a simple compact form that can be easily implemented from standard statistical software. The adjusted statistic is approximately distributed as X(2) with high degree of accuracy. It is applicable in wide generality since it allows both the parameter of interest and the nuisance parameter to be vector-valued. Unlike the modified profile likelihood ratio statistic obtained from Cox and Reid [Cox, D.R., Reid, N., 1987. Parameter orthogonality and approximate conditional inference. journal of the Royal Statistical Society B49, 1-39], the adjusted statistic proposed here does not require an orthogonal parameterization. Numerical comparison of likelihood-based tests of varying dispersion favors the test we propose and a Bartlett-corrected version of the modified profile likelihood ratio test recently obtained by Cysneiros and Ferrari [Cysneiros, A.H.M.A., Ferrari, S.L.P., 2006. An improved likelihood ratio test for varying dispersion in exponential family nonlinear models. Statistics and Probability Letters 76 (3), 255-265]. (C) 2008 Elsevier B.V. All rights reserved.

Symmetry in biology: from genetic code to stochastic gene regulation

Mathematical models, as instruments for understanding the workings of nature, are a traditional tool of physics, but they also play an ever increasing role in biology - in the description of fundamental processes as well as that of complex systems. In this review, the authors discuss two examples of the application of group theoretical methods, which constitute the mathematical discipline for a quantitative description of the idea of symmetry, to genetics. The first one appears, in the form of a pseudo-orthogonal (Lorentz like) symmetry, in the stochastic modelling of what may be regarded as the simplest possible example of a genetic network and, hopefully, a building block for more complicated ones: a single self-interacting or externally regulated gene with only two possible states: ` on` and ` off`. The second is the algebraic approach to the evolution of the genetic code, according to which the current code results from a dynamical symmetry breaking process, starting out from an initial state of complete symmetry and ending in the presently observed final state of low symmetry. In both cases, symmetry plays a decisive role: in the first, it is a characteristic feature of the dynamics of the gene switch and its decay to equilibrium, whereas in the second, it provides the guidelines for the evolution of the coding rules.

Maslov index in semi-Riemannian submersions

We study focal points and Maslov index of a horizontal geodesic gamma : I -> M in the total space of a semi-Riemannian submersion pi : M -> B by determining an explicit relation with the corresponding objects along the projected geodesic pi omicron gamma : I -> B in the base space. We use this result to calculate the focal Maslov index of a (spacelike) geodesic in a stationary spacetime which is orthogonal to a timelike Killing vector field.

Pseudo Focal Points Along Lorentzian Geodesics and Morse Index

Given a Lorentzian manifold (M,g), a geodesic gamma in M and a timelike Jacobi field Y along gamma, we introduce a special class of instants along gamma that we call Y-pseudo conjugate (or focal relatively to some initial orthogonal submanifold). We prove that the Y-pseudo conjugate instants form a finite set, and their number equals the Morse index of (a suitable restriction of) the index form. This gives a Riemannian-like Morse index theorem. As special cases of the theory, we will consider geodesics in stationary and static Lorentzian manifolds, where the Jacobi field Y is obtained as the restriction of a globally defined timelike Killing vector field.

Contravariantly finite subcategories closed under predecessors

Let A be an Artin algebra and mod A be the category of finitely generated right A-modules. We prove that an additive full subcategory C of mod A closed under predecessors is contravariantly finite if and only if its right Ext-orthogonal is covariantly finite, or if and only if the Ext-injectives in C define a cotilting module (over the support algebra of C) or, equivalently, if and only if C is the support of the representable functors given by the Ext-injectives. (C) 2009 Elsevier Inc. All rights reserved.

Traffic and Road Sign Recognition

This thesis presents a system to recognise and classify road and traffic signs for the purpose of developing an inventory of them which could assist the highway engineers’ tasks of updating and maintaining them. It uses images taken by a camera from a moving vehicle. The system is based on three major stages: colour segmentation, recognition, and classification. Four colour segmentation algorithms are developed and tested. They are a shadow and highlight invariant, a dynamic threshold, a modification of de la Escalera’s algorithm and a Fuzzy colour segmentation algorithm. All algorithms are tested using hundreds of images and the shadow-highlight invariant algorithm is eventually chosen as the best performer. This is because it is immune to shadows and highlights. It is also robust as it was tested in different lighting conditions, weather conditions, and times of the day. Approximately 97% successful segmentation rate was achieved using this algorithm.Recognition of traffic signs is carried out using a fuzzy shape recogniser. Based on four shape measures - the rectangularity, triangularity, ellipticity, and octagonality, fuzzy rules were developed to determine the shape of the sign. Among these shape measures octangonality has been introduced in this research. The final decision of the recogniser is based on the combination of both the colour and shape of the sign. The recogniser was tested in a variety of testing conditions giving an overall performance of approximately 88%.Classification was undertaken using a Support Vector Machine (SVM) classifier. The classification is carried out in two stages: rim’s shape classification followed by the classification of interior of the sign. The classifier was trained and tested using binary images in addition to five different types of moments which are Geometric moments, Zernike moments, Legendre moments, Orthogonal Fourier-Mellin Moments, and Binary Haar features. The performance of the SVM was tested using different features, kernels, SVM types, SVM parameters, and moment’s orders. The average classification rate achieved is about 97%. Binary images show the best testing results followed by Legendre moments. Linear kernel gives the best testing results followed by RBF. C-SVM shows very good performance, but ?-SVM gives better results in some case.

Reservoir Management For Flood And Drought Protection Using Infinite Horizon Model Predictive Control

Model Predictive Control (MPC) is a control method that solves in real time an optimal control problem over a finite horizon. The finiteness of the horizon is both the reason of MPC's success and its main limitation. In operational water resources management, MPC has been in fact successfully employed for controlling systems with a relatively short memory, such as canals, where the horizon length is not an issue. For reservoirs, which have generally a longer memory, MPC applications are presently limited to short term management only. Short term reservoir management can be effectively used to deal with fast process, such as floods, but it is not capable of looking sufficiently ahead to handle long term issues, such as drought. To overcome this limitation, we propose an Infinite Horizon MPC (IH-MPC) solution that is particularly suitable for reservoir management. We propose to structure the input signal by use of orthogonal basis functions, therefore reducing the optimization argument to a finite number of variables, and making the control problem solvable in a reasonable time. We applied this solution for the management of the Manantali Reservoir. Manantali is a yearly reservoir located in Mali, on the Senegal river, affecting water systems of Mali, Senegal, and Mauritania. The long term horizon offered by IH-MPC is necessary to deal with the strongly seasonal climate of the region.

Análise dinâmica de solos submetidos à ação simultânea das três componentes da excitação na base rochosa

Durante a análise sísmica de estruturas complexas, o modelo matemático empregado deveria incluir não só as distribuicões irregulares de massas e de rigidezes senão também à natureza tridimensional da ecitação sísmica. Na prática, o elevado número de graus de liberdade involucrado limita este tipo de análise à disponibilidade de grandes computadoras. Este trabalho apresenta um procedimento simplificado, para avaliar a amplificação do movimento sísmico em camadas de solos. Sua aplicação permitiria estabelecer critérios a partir dos quais avalia-se a necessidade de utilizar modelos de interação solo-estrutura mais complexos que os utilizados habitualmente. O procedimento proposto possui as seguientes características : A- Movimento rígido da rocha definido em termos de três componentes ortagonais. Direção de propagação vertical. B- A ecuação constitutiva do solo inclui as características de não linearidade, plasticidade, dependência da história da carga, dissipação de energia e variação de volume. C- O perfil de solos é dicretizado mediante um sistema de massas concentradas. Utiliza-se uma formulação incremental das equações de movimento com integração directa no domínio do tempo. As propriedades pseudo-elásticas do solo são avaliadas em cada intervalo de integração, em função do estado de tensões resultante da acção simultânea das três componentes da excitação. O correcto funcionamento do procedimento proposto é verificado mediante análises unidimensionais (excitação horizontal) incluindo estudos comparativos com as soluções apresentadas por diversos autores. Similarmente apresentam-se análises tridimensionais (acção simultânea das três componentes da excitação considerando registros sísmicos reais. Analisa-se a influência que possui a dimensão da análise (uma análise tridimensional frente a três análises unidimensionais) na resposta de camadas de solos submetidos a diferentes níveis de exçitação; isto é, a limitação do Princípio de Superposisão de Efeitos.

Volatilidade implícita versus volatilidade estatística : uma avaliação para o mercado brasileiro a partir dos dados de opções e ações da Telemar S.A.

A partir de uma base de dados de ações da Telemar S.A., do período de 21/09/1998 a 21/10/2002, e de opções de 02/10/2000 a 21/10/2002, foi avaliado qual o previsor que prevê com maior precisão a volatilidade futura: o implícito ou o estatístico. A volatilidade implícita foi obtida por indução retroativa da fórmula de Black-Scholes. As previsões estatísticas da volatilidade foram obtidas pelos modelos de média móvel ponderada igualmente, modelo GARCH, EGARCH e FIGARCH. Os resultados das regressões do conteúdo de informação revelam que a volatilidade implícita ponderada possui substancial quantidade de informações sobre a volatilidade um passo à frente, pois apresenta o maior R2 ajustado de todas as regressões. Mesmo sendo eficiente, os testes indicam que ela é viesada. Porém, a estatística Wald revela que os modelos EGARCH e FIGARCH são previsores eficientes e não viesados da variação absoluta dos retornos da Telemar S.A. entre t e t + 1, apesar do R2 um pouco inferior a volatilidade implícita. Esse resultado a partir de parâmetros baseados em dados ex-post, de certo modo refuta a hipótese de que as opções possibilitam melhores informações aos participantes do mercado sobre as expectativas de risco ao longo do próximo dia Nas regressões do poder de previsão, que testam a habilidade da variável explicativa em prever a volatilidade ao longo do tempo de maturidade da opção, os resultados rejeitam a hipótese da volatilidade implícita ser um melhor previsor da volatilidade futura. Elas mostram que os coeficientes das volatilidades implícitas e incondicionais são estatisticamente insignificantes, além do R2 ajustado ser zero ou negativo. Isto, a princípio, conduz à rejeição da hipótese de que o mercado de opções é eficiente. Por outro lado, os resultados apresentados pelos modelos de volatilidade condicional revelam que o modelo EGARCH é capaz de explicar 60% da volatilidade futura. No teste de previsor eficiente e não viesado, a estatística Wald não rejeita esta hipótese para o modelo FIGARCH. Ou seja, um modelo que toma os dados ex-post consegue prever a volatilidade futura com maior precisão do que um modelo de natureza forward looking, como é o caso da volatilidade implícita. Desse modo, é melhor seguir a volatilidade estatística - expressa pelo modelo FIGARCH, para prever com maior precisão o comportamento futuro do mercado.

Desempenho de estimadores de volatilidade do Ibovespa

O objetivo deste trabalho é comparar diferentes métodos da volatilidade do Índice da Bolsa de Valores de São Paulo (IBOVESPA) utilizando uma nova metodologia proposta na literatura, denominada volatilidade realizada. Comparamos modelos da família GARCH com estimadores alternativos baseados em cotações de abertura, fechamento, máximo e mínimo. Concluímos que pode ser interessante a utilização de estimadores mais simples do que os derivados da família GARCH, que acabam sendo mais econômicos em termos de tempo dispendido no processo de estimação, sem perda de precisão.

Previsão de volatilidade para os vértices da estrutura a termo de taxa de juros em reais brasileira

Este trabalho compara diferentes metodologias de previsão de volatilidade para vértices da estrutura a termo de juros em reais e propõe um novo modelo, batizado como COPOM-GARCH, para estimação desta. O modelo COPOM-GARCH se utiliza de duas variáveis dummy, uma no dia de divulgação do resultado da Reunião do COPOM e outra no dia seguinte, para fazer uma melhor previsão da volatilidade tanto nestes dois dias quanto nos dias subseqüentes.

Volatility modelling in the forex market: an empirical evaluation

We compare three frequently used volatility modelling techniques: GARCH, Markovian switching and cumulative daily volatility models. Our primary goal is to highlight a practical and systematic way to measure the relative effectiveness of these techniques. Evaluation comprises the analysis of the validity of the statistical requirements of the various models and their performance in simple options hedging strategies. The latter puts them to test in a "real life" application. Though there was not much difference between the three techniques, a tendency in favour of the cumulative daily volatility estimates, based on tick data, seems dear. As the improvement is not very big, the message for the practitioner - out of the restricted evidence of our experiment - is that he will probably not be losing much if working with the Markovian switching method. This highlights that, in terms of volatility estimation, no clear winner exists among the more sophisticated techniques.

Evaluation of contagion or interdependence in the financial crises of Asia and Latin America, considering the macroeconomic fundamentals

This article investigates the existence of contagion between countries on the basis of an analysis of returns for stock indices over the period 1994-2003. The economic methodology used is that of multivariate GARCH family volatility models, particularly the DCC models in the form proposed by Engle and Sheppard (2001). The returns were duly corrected for a series of country-specific fundamentals. The relevance of this procedure is highlighted in the literature by the work of Pesaran and Pick (2003). The results obtained in this paper provide evidence favourable to the hypothesis of regional contagion in both Latin America and Asia. As a rule, contagion spread from the Asian crisis to Latin America but not in the opposite direction

“Ombro-cabeça-ombro”: testando a lucratividade do padrão gráfico de análise técnica no mercado de ações brasileiro

A partir de uma adaptação da metodologia de Osler e Chang (1995), este trabalho avalia, empiricamente, a lucratividade de estratégias de investimento baseadas na identificação do padrão gráfico de Análise Técnica Ombro-Cabeça-Ombro no mercado de ações brasileiro. Para isso, foram definidas diversas estratégias de investimento condicionais à identificação de padrões Ombro-Cabeça- Ombro (em suas formas padrão e invertida), por um algoritmo computadorizado, em séries diárias de preços de 47 ações no período de janeiro de 1994 a agosto de 2006. Para testar o poder de previsão de cada estratégia, foram construídos intervalos de confiança, a partir da técnica Bootstrap de inferência amostral, consistentes com a hipótese nula de que, baseado apenas em dados históricos, não é possível criar estratégias com retornos positivos. Mais especificamente, os retornos médios obtidos por cada estratégia nas séries de preços das ações, foram comparados àqueles obtidos pelas mesmas estratégias aplicadas a 1.000 séries de preços artificiais - para cada ação - geradas segundo dois modelos de preços de ações largamente utilizados: Random Walk e E-GARCH. De forma geral, os resultados encontrados mostram que é possível criar estratégias condicionais à realização dos padrões Ombro- Cabeça-Ombro com retornos positivos, indicando que esses padrões conseguem capturar nas séries históricas de preços de ações sinais a respeito da sua movimentação futura de preços, que não são explicados nem por um Random Walk e nem por um E-GARCH. No entanto, se levados em consideração os efeitos das taxas e dos custos de transação, dependendo das suas magnitudes, essas conclusões somente se mantêm para o padrão na sua forma invertida