Este trabalho propõe a aplicação de dois diferentes conceitos para a resolução do Problema de Estivagem de Unidades de Celulose - PEUC, que de acordo com Ribeiro e Lorena (2008) pode ser definido como um problema que busca alocar a máxima quantidade de unidades de celulose ao porão de cargas de um dado navio, respeitando as restrições físicas de dimensões, de posicionamento, de não-sobreposição das unidades e de capacidade máxima do porão do navio. Esse tipo de problema se encaixa, no contexto da Pesquisa Operacional, na classe de Corte e Empacotamento (Cutting and Packing - C&P) e pode ser classificado, de acordo com a tipologia de Wäscher, Haußner e Schumann (2007), como sendo um Single Large Object Placement Problem (SLOPP). Em última instância, o objetivo do PEUC é definir o melhor plano de estivagem para o carregamento de unidades de celulose em um dado porão de um navio, maximizando a área ocupada pelas unidades de celulose. Trata-se de um problema NP-Completo (DOWSLAND; DOWSLAND, 1992; BISCHOFF; WÄSCHER, 1995; MALAGUTI; DURáN; TOTH, 2013) e por isso foram propostas duas abordagens para buscar a melhoria das soluções encontradas e/ou redução do tempo computacional necessário. As abordagens propostas, o Modelo Matemático Modificado e o Método Iterativo de Solução, apresentaram bons resultados para instâncias experimentais, confirmando a efetividade de suas aplicações. Os resultados foram melhores tanto na qualidade das soluções (ocupação total do objeto), como no tempo computacional necessário. Também foram avaliadas quatro instâncias reais, com a comparação dos planos de estivagem resultantes da aplicação dos modelos matemáticos com os planos reais, elaborados manualmente por especialistas. Em três dos quatro casos os resultados das abordagens aqui propostas se mostraram melhores que os planos reais. / This work proposes the application of two different concepts to tackle the Woodpulp Stowage Problem - WSP, that according to Ribeiro e Lorena (2008) can be defined as a problem that seeks the allocation of the maximum quantity of woodpulp units inside the hold of a cargo vessel, always respecting the physical constraints, positioning constraints, non-overlapping of units and also the hold capacity. This kind of problem fits, in the context of Operational Research, into the class of Cutting & Packing and can be classified, according to Wäscher, Haußner e Schumann (2007) typology, as a Single Larga Object Placement Problem (SLOPP). Ultimately the objective of the WSP is to define the best stowage plan for the loading of woodpulp units inside a given hold of a given cargo vessel, maximizing the total area occupied by the woodpulp units. As it\'s a NP-Complete problem (DOWSLAND; DOWSLAND, 1992; BISCHOFF; WÄSCHER, 1995; MALAGUTI; DURáN; TOTH, 2013) two approaches were proposed to improve the quality of the resulting solutions and/or the reduction of the computational time needed. The proposed approaches, the Modified Mathematical Model and the Iterative Solution Method, showed good results for experimental instances, confirming the effectiveness of these approaches. The results were better regarding the quality of the solutions (total occupied area of the object) and also regarding the computational time needed. Also, four real instances were evaluated, comparing the results of the mathematical models with the real stowage plans, manually created by specialists. In three of the four instances, the proposed approaches showed better results than the real stowage plans.

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T17:05:58Z (GMT). No. of bitstreams: 1 Freitas_LucasIsmailyBezerra_M.pdf: 2067916 bytes, checksum: 77f11deab9d862fe9a10de2df94b447c (MD5) Previous issue date: 2014 / Resumo: Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação, nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contra-exemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K_5 / Abstract: In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza's conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K_5 minor / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T17:20:46Z (GMT). No. of bitstreams: 1 Silva_FabricioLuisSantosda_M.pdf: 657410 bytes, checksum: 65ac7a297f6547a9ac70dfa42604f1ce (MD5) Previous issue date: 2010 / Resumo: Neste trabalho lidamos com o problema de Empacotamento em Faixa Bidimensional considerando o caso em que os itens devem ser dispostos de forma a manter o empacotamento estável e satisfazer uma ordem de descarregamento imposta. Consideramos o caso em que a orientação dos itens é fixa. Definimos uma metodologia para analisar a estabilidade do empacotamento observando as condições de equilíbrio estático para corpos rígidos. Desenvolvemos heurísticas e formulamos um programa linear inteiro para o problema de Empacotamento em Faixa sujeito a tais restrições. A resolução da formulação inteira ocorre através de uma estratégia do tipo branch-and-cut. As restrições de estabilidade foram inseridas como planos de corte de maneira a remover empacotamentos que não são estáveis. Em nossos experimentos computacionais, vemos que o modelo proposto é adequado para lidar com instâncias de pequeno até médio porte, dentro de um tempo computacional razoável / Abstract: This paper investigates the Two-Dimensional Strip Packing Problem considering the case in which the items should be arranged to form a stable packing and satisfy an order of unloading, so that after unloading, the packing is still stable. We consider the case where the items are oriented and rotations are not allowed. We present a methodology to analyze the stability of the packing observing the conditions for static equilibrium of rigid bodies. We present heuristics and formulate an integer linear programming model for the Strip Packing problem considering such constraints. To solve the integer formulation, we develop a branch-and-cut approach. For each integer solution obtained during the branch-and-cut algorithm, corresponding to a non-stable packing, we insert a cutting plane for which this integer solution is not satisfied. In our computational experiments, we see that the proposed model is suitable to deal with small and mid-sized instances. Some optimal solutions were obtained after few hours of CPU processing / Mestrado / Mestre em Ciência da Computação

Made available in DSpace on 2014-06-12T18:06:06Z (GMT). No. of bitstreams: 2 arquivo7710_1.pdf: 1970770 bytes, checksum: 32db2284b5821407a424ede60f9fb4af (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O termo reptação está associado ao tipo de movimento executado por répteis, especificamente as serpentes, sendo empregado para descrever a difusão de objetos com a topologia da linha. A reptação de um fio injetado numa cavidade é estudada através de medidas do deslocamento quadrático médio <r2> de um ponto do fio, em função do comprimento h injetado. A espessura do fio é z = 0,1 cm e, o ponto escolhido corresponde ao centro de massa em uma dimensão (CM1D), também denominado por ponto central topológico. A cavidade é circular com raio R = 10 cm e de espessura pouco maior que z, de forma a permitir a existência de apenas uma camada de fio na cavidade. O fio é injetado manualmente à velocidade uniforme, por dois canais dispostos em ângulo de 180°. Foram realizados experimentos com fios de cobre, Sn0,6Pb0,4 (solda elétrica), alumínio, latão, náilon e aço duro. As medidas mostram que <r2> (exceto para fios de náilon e aço duro) passa por um regime transiente no terço inicial do experimento, e por regime quase-estável no tempo restante, por conta do confinamento do CM1D. Inspirando-se no modelo de Flory para polímeros, desenvolvemos um modelo de campo médio onde o ponto central é descrito por uma partícula sujeita a dois potenciais que simulam interações de auto-exclusão, a influência da fronteira e as flutuações devido às propriedades mecânicas do fio e ao ruído inerente ao processo de empacotamento. A lei de escala r~h1/5 prevista pelo modelo, é avaliada com base nos resultados experimentais. Por fim, os resultados obtidos para o fio de solda indicam um comportamento intermediário entre as dinâmicas de reptação de Rouse e de de Gennes

Orientador : Marcelo Firer / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-04T02:48:30Z (GMT). No. of bitstreams: 1 Faria_MercioBotelho_D.pdf: 4443274 bytes, checksum: 86dda25654f7eb724f654b696016fcf1 (MD5) Previous issue date: 2005 / Resumo: Este trabalho busca elementos para se determinar a densidade de empacotamento de esferas definida por reticulados no plano hiperbólico.Consideramos o espaço de teichmuller Tu de todas as superfícies orientadas com-pactas e fechadas de gênero 9 2: 2, as quais tem o plano hiperbólico como recobrimento universal riemanniano. É conhecido o sistema de coordenadas Fricke em Tu que associa a cada superfície um domínio fundamental de Voronoi-Dirichlet dado por um polígono convexo com 4g arestas. Sabemos que, fixado o gênero, a densidade cresce com o número de arestas do domínio de Voronoi-Dirichlet escolhido, de modo que é natural a busca por polígonos com um número máximo de arestas associado ao gênero dado, que é sempre limitado por 12g - 6.Neste trabalho, determinamos as coordenadas Fricke em Tu que associa a cada su-perfície um domínio de Voronoi-Dirichlet com 4g + 2 e 12g - 6 arestas. Além disso, determinamos e implementamos algoritmos para a determinação dos círculos inscrito e circunscrito de um polígono (em superfícies de curvatura constante). Estes algorit-mos, em sua generalidade tem complexidade O (n4) mas, restringindo os polígonos a vizinhanças abertas de um polígono dado, possui complexidade O (n), situação ótima.A determinação dos domínios de Voronoi-Dirichlet e dos círculos inscritos permitem definir a densidade de empacotamento diretamente nos espaços de teichmuller através de um sistema de equações polinomiais / Abstract: This work searches elements to determine the packing density of spheres defined by lattices in the hyperbolic plane. We consider the teichmüller space Tg of all closed compacts oriented surfaces of genus 9 ~ 2, which has the hyperbolic plane as universal covering rienmannian surface. It is known that the system of Fricke coordinates in Tg associates each surface to a fundamental of Voronoi-Dirichlet domain, given by convex polygon with 49 edges. We know that, with fixed genus, the density increases with the number of edges of the chosen Voronoi-Dirichlet domain. Thus it is naturallooking for polygons with a maximum number of edges associated to a given genus, which is always limited by 129 - 6.In this work, we determine Fricke coordinates in Tg which associates each surface to a Voronoi-Dirichlet domain with 49 + 2 and 129 - 6 edges. Furthermore, we determine and we program the algorithms for determination of the inscribed and circumscribed circles of a polygon (in surfaces of constant curvature). These algorithms, have com-plexity O (n4) , but when restricted to open neighbourhoods of a given polygon, have complexity O (n), best situation.The determination of the Voronoi-Dirichlet domain from the inscribed circles per-mits to define the packing of density directly on teichmüller spaces through a polyno-mials of system equations / Doutorado / Matematica / Doutor em Matemática

Orientador: Cristiano Torezzan / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-27T01:15:40Z (GMT). No. of bitstreams: 1 Miranda_FabianoBoaventurade_M.pdf: 1712497 bytes, checksum: 35928984d709d1154545670e07948f87 (MD5) Previous issue date: 2015 / Resumo: Neste trabalho estudamos o problema da quantização vetorial, com especial interesse no uso de códigos esféricos para quantização de fontes gaussianas. Este problema tem diversas aplicações envolvendo compressão de sinais, tais como de som e imagem, garantindo altas taxas de compressão. Nos três primeiros capítulos fazemos uma apresentação dos principais fundamentos teóricos do tema, procurando apresentar exemplos que valorizam a intuição e conceitos geométrico, no caso de dimensões 2 e 3, abordando a quantização vetorial com ênfase na técnica conhecida como forma/ganho. No último capítulo apresentamos uma proposta original que utiliza códigos em camadas de toros para a quantização vetorial. A proposta é exemplificada através da construção do esquema de quantização em dimensão 4 e alguns testes de desempenho são apresentados / Abstract: We study the vector quantization problem with a special interest in the use of spherical codes for Gaussian sources. This problem appears in several applications involving signal compression such as sound, images and data transmission. The first three chapters are devoted to basic concepts of quantization and also to presented some intuitive examples and geometrical interpretations. We focus our attention on the shape and gain vector quantization and we introduce a new approach to this problem using spherical codes constructed in layers of flat tori in dimension 4. Besides the construction, some results on computations simulations are presented / Mestrado / Matematica Aplicada e Computacional / Mestre em Matemática Aplicada e Computacional

Os problemas de corte e empacotamento são frequentes em diferentes processos produtivos, por exemplo, na produção de roupas, de calçados, de peças metálicas e de móveis. Seu objetivo mais frequente e a minimização do desperdício de matéria-prima. No entanto, em algumas situações, o problema de determinação do caminho de corte e fundamental para eciência do planejamento da produção. Este problema consiste em determinar a trajetória de corte que minimize, por exemplo, o tempo total de corte de um plano de corte previamente estabelecido. Devido a existência de poucas abordagens para este problema, nosso objetivo e propor modelos matemáticos para resolver o problema de determinação do caminho de corte. Além disso, uma variação do problema que considera a utilização de grafos dinâmicos também é abordada. Os resultados obtidos são comparados com resultados da literatura. / Cutting and packing problems are frequent in dierent productive process, for example, in the garment, shoe, metallic pieces and furniture production. Its most common objective is the minimization of the raw material waste. However, in some situations, the cutting path determination problem is fundamental to the eciency of the production planning. This problem consists in determining the cutting trajectory that minimizes, for example, the total cutting time of a previously established cutting plane. Due to the few existing approaches to this problem, our objective is to propose mathematical models to solve the cutting path determination problem. Furthermore, a variation of the problem that considers the use of dynamic graphs is also adressed. The obtained results are compared with those from the literature.

The two-dimensional irregular cutting and packing problems (aka nesting problems) have been studied over the past six decades and consist in cutting (packing) convex and non-convex small pieces from (in) large boards without overlapping. There are several variants of this problem that are defined according to the board shapes and the objective of each problem. There are a number of heuristics proposed in the literature to solve irregular cutting and packing problems, but only few mixed-integer programming models. Specifically, these models were developed for the irregular strip packing problem, that consists in packing pieces into a single board with fixed width and length to be minimized. For the other problem variants, there is no exact methods presented in the literature. The main difficulty in solving irregular cutting and packing problems is how to handle with the geometric constraints. These constraints depend on the type of placement of the pieces on the board that can be continuous or discrete. In this thesis, we present two mixed-integer programming models for the irregular strip packing problem in which the pieces can be continuously placed on the board. These models do not demand complex structures to be built. We also present a new dot data structure to store the information on the placement of the pieces and overlapping positions bringing flexibility and efficiency to discrete approaches. Using this structure, a matheuristic is proposed, combining the advantages of the models with discrete and continuous placement positions for the pieces on the board. Furthermore, constraint programming models for several variants of irregular cutting and packing problems are exploited. For some variants, these models are the first modelling representation. A new global constraint is developed to eliminate the overlap among pieces. Computational experiments were conducted to evaluate the developed approaches. / Os problemas de corte e empacotamento de peças irregulares bidimensionais vêm sendo estudados há décadas e consistem em cortar (empacotar) peças menores, convexas e não convexas, a partir de (em) placas maiores de forma a não se sobreporem. Existem diversas variantes deste problema, definidas de acordo com o formato da placa e objetivo de cada problema. Na literatura, muitas heurísticas foram propostas para a resolução dos problemas de corte e empacotamento de peças irregulares, porém, poucos modelos de programação inteira mista podem ser encontrados. Especificamente, estes modelos foram desenvolvidos para o problema de empacotamento em faixa, que consiste em empacotar as peças em uma placa de largura fixa e comprimento a ser minimizado. Para as demais variantes do problema, não existem métodos exatos propostos na literatura. A principal dificuldade na resolução dos problemas de corte e empacotamento de peças irregulares está na manipulação das restrições geométricas. Estas restrições dependem do tipo de posicionamento das peças na placa, que pode ser discreto ou contínuo. Nesta tese, apresentamos dois modelos de programação inteira mista para o problema de empacotamento de peças em faixa, no qual cada peça pode ser alocada de forma contínua na placa. Estes modelos não demandam estruturas complexas para serem construídos. Também apresentamos uma nova estrutura de dados para armazenar informações sobre o posicionamento das peças e as posições de sobreposição, trazendo flexibilidade e eficiência para abordagens discretas. Utilizando esta estrutura, uma matheuristica foi proposta, combinando as vantagens dos modelos com alocação discreta e contínua das peças na placa. Além disso, modelos de programação por restrições para diversas variantes dos problemas de corte e empacotamento de peças irregulares foram explorados. Para algumas variantes, estes modelos são a primeira representação via modelagem. Uma nova restrição global foi desenvolvida para eliminar a sobreposição entre as peças. Experimentos computacionais foram realizados para avaliar as abordagens propostas.

Neste trabalho, consideramos uma nova parametrização para o problema de empacotar a maior quantidade possível de círculos idênticos uma região elíptica dada. Apresentamos algoritmos com propriedades de convergência global e algumas estratégias heurísticas. Ilustramos com experimentos numéricos extensivos cada uma das estratégias utilizadas / In this work we consider a new parametrization for the problem of packing the maximum number of identical circles within a given elliptical region. We present algorithms with global convergence properties and some heuristic strategies. We illustrate each described strategy with extensive numerical experiments

O número de contato do Rn (em inglês, kissing number) é o maior número de esferas de raio unitário e interiores dois-a-dois disjuntos que podem tocar simultaneamente uma esfera de raio unitário central. Nesta dissertação estudamos métodos que limitam o tamanho de tais configurações através de técnicas de otimização, como dualidade e programação semidefinida. O principal resultado obtido foi o cálculo de melhores limitantes para o número de contato nas dimensões 9 a 23; o que foi possível graças à exploração de simetrias dos polinômios presentes no limitante proposto por Bachoc e Vallentin (2008), levando à consideração de programas semidefinidos menores. Por fim, o limitante estudado é estendido para uma classe mais geral de problemas. / The kissing number of Rn is the maximum number of pairwise-nonoverlapping unit spheres that can simultaneously touch a central unit sphere. In this thesis we study methods to bound from above the size of such configurations using optimization techniques, like duality and semidefinite programming. The main result achieved is the computation of better bounds for the kissing number in dimensions 9 to 23; a result possible due to the exploitation of symmetries in the polynomials present in the bound proposed by Bachoc and Vallentin (2008), leading to the consideration of smaller semidefinite programs. Finally, the studied bound is extended to a bigger class of problems.