[pt] Este trabalho apresenta uma proposta de aceleração da decomposição de Benders aplicada a uma versão mais geral e compacta (menos restrições e variáveis) do modelo de gestão de estoques, otimizado via programação estocástica de dois estágios que considera uma camada, um item, demanda incerta e política de controle (R, S). De maneira a ser possível considerar problemas de grande porte, foram aplicados os métodos L-Shaped tradicional com corte único e a sua forma estendida com múltiplos cortes. Resultados computacionais preliminares mostraram um substancial melhor desempenho computacional do método L-Shaped tradicional em relação à sua forma multi-cut L-Shaped, mesmo o primeiro necessitando de mais iterações para convergir na solução ótima. Tal observação motivou o desenvolvimento de uma nova técnica de aceleração da decomposição de Benders e de um conjunto de desigualdades válidas. Experimentos numéricos mostram que a abordagem proposta de combinar a técnica de aceleração elaborada com as desigualdades válidas desenvolvidas provê significativa redução do tempo computacional necessário para a solução de instâncias de grande porte. / [en] This dissertation presents a speed up proposal for the Benders decomposition applied to a more general and compact version (less constraints and variables) of inventory management model, optimized via two-stage stochastic programming, which considers one layer, one item, uncertain demand and control policy (R, S). In order to be possible to consider large scale problems, the L-Shaped traditional method with single cuts and its extended form with multiple cuts were applied. Preliminary computational results showed a substantially better computational performance of the traditional L-Shaped method in comparison to the multi-cut L-Shaped method, even with the first requiring more iterations to converge on optimum solutions. This observation led to the development of a new technique to accelerate the decomposition of Benders and a set of valid inequalities. Numerical experiments show that the proposed approach of combining the elaborate acceleration technique with the developed valid inequalities, provide significant reduction in the computational time required to solve large scale instances.

[pt] Atualmente, as malhas de simulação do fluxo em reservatórios naturais de petróleo (RNPs) são modelos compostos por centenas de milhares de células hexaédricas, cada uma podendo ser decomposta em 12 triângulos, de modo que a visualização interativa dessas malhas, através das estações gráficas atuais, ainda não é factível. À medida que os computadores e as placas gráficas aumentam sua capacidade de processamento, as malhas de simulação também crescem. A solução para esse tipo de problema passa, normalmente, por técnicas de aceleração, dentre as quais está a multi-resolução (MR). Ocorre, entretanto, que os modelos de multi-resolução atualmente conhecidos não são aplicáveis às malhas de simulação de RNPs, devido aos requisitos específicos da área, tais como a preservação do modelo de células hexaédricas e a descontinuidade entre células. Na realidade, as técnicas de multi-resolução tendem a enfocar a Visualização Realista, enquanto o problema de RNPs é de Visualização Científica, para a qual ainda não existem soluções genéricas. Esta dissertação propõe um modelo de MR específico para o problema de visualização das malhas de simulação em RNPs, no qual a partição descontínua do espaço, a semântica baseada em células hexaédricas e as características de visualização do problema são pontos considerados. O modelo proposto permite uma construção eficiente da estrutura de MR, a partir da qual, em tempo real, são extraídas malhas adaptativas dependentes: (a) do erro geométrico da aproximação, (b) da câmera e (c) do número desejado de polígonos na malha. Além disso, o modelo permite a utilização conjunta de outra técnica de aceleração, o descarte, possibilitando o descarte hierárquico de regiões da malha que estão fora do volume de visão. O modelo proposto foi implementado em um sistema que permitiu uma extensa bateria de testes, cujos resultados permitiram traçar algumas conclusões e recomendações. / [en] Current flow-simulation meshes of natural oil reservoirs (NOR) are composed of hundreds of thousands of hexahedral cells. The visualization of the geometry of these cells superimposed with color attributes to represent properties and flow results requires the rendering of an unstructured mesh of millions of triangles. Current graphics hardware does not allow for an interactive visualization of such meshes. As computers and graphics boards increase their processing capacity, simulation meshes also grow and the solution to the rendering problem usually includes acceleration techniques, one of which is multi-resolution (MR). However, currently known MR models are not applicable to NOR simulation meshes due to this field`s specific requirements, such as the preservation of the hexahedral- cell model and discontinuities among cells. In fact, MR techniques tend to focus on Realistic Visualization, while the NOR problem is one of Scientific Visualization, for which generic solutions still do not exist. The present work proposes a specific MR model for the visualization problem concerning NOR simulation meshes, in which discontinuous space partition, hexahedral-cell-based semantics and the problem`s visualization characteristics are taken into account. The proposed model allows an efficient construction of a MR structure, from which, in real time, adaptive meshes can be extracted that depend on: (a) the geometric error approximation, (b) the view, and (c) the polygon budget. This model can also be used combined with another acceleration technique, frustum culling, which allows for the hierarchical elimination of regions in the mesh that are out of the view volume. The proposed model was implemented in a system on which extensive testing was performed, providing results that allowed us to draw some conclusions and recommendations.