Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T17:56:16Z (GMT). No. of bitstreams: 1 Assis_IgorRibeirode_M.pdf: 5116531 bytes, checksum: 151d5c4293cb869d16ddf4c6f7bb8992 (MD5) Previous issue date: 2013 / Resumo: Aplicações desse problema incluem: máquina de controle numérico, inspeção automática e roteamento. Esta dissertação estuda soluções para o problema do recorte. Propomos um modelo de programação linear inteira e a partir deste desenvolvemos um algoritmo exato. Descrevemos um algoritmo 3.75 aproximado da literatura e propomos algumas melhorias heurísticas para o mesmo. Abandonando as garantias teóricas, projetamos duas heurísticas: a primeira utiliza uma ideia gulosa bastante simples complementada por técnicas da meta-heurística GRASP, especificamente aleatorização e busca local; e a segunda resolve um problema de cobertura mais simples e cuja sua solução pode ser adaptada para o problema original. Por fim propomos uma série de vizinhanças executadas em uma fase de busca local, que dada uma solução, faz mudanças locais que reduzem o custo do tour. As implementações dos algoritmos descritos são analisadas experimentalmente utilizando um benchmark de instâncias que construímos e deixamos público para comparações futuras / Abstract: In the orthogonal milling with turn costs problem is given an orthogonal polygon P that may contain holes. Our goal is to find a closed polygonal curve made of horizontal and vertical segments which when traversed by a unit square, the covered area is exactly P. Turn costs are assigned to direction changes and the objective is to minimize the sum of turn costs. This problem arises in many applications including: numerically controlled (NC) machining, automatic inspection and routing. This dissertation studies solutions for the milling problem. We propose an integer linear programming model and from which an exact algorithm is proposed. A 3.75- approximate algorithm from the literature is described for which heuristic improvements are proposed. Lifting the theoretical guarantees we project two heuristics: the first is based in a simple greedy idea supplemented with techniques of the GRASP meta-heuristic, specifically, randomization and local search; the latter solves a simpler covering problem whose its solution is adapted for the original problem. Finally, we propose a series of neighborhoods run in a local search step where, local changes are made to the solution such that the tour cost is reduced. All described algorithms are implemented and evaluated experimentally using a benchmark of instances that we built and made public for future comparisons / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T04:31:47Z (GMT). No. of bitstreams: 1 Braga_AndreideAlmeidaSampaio_M.pdf: 1060769 bytes, checksum: 789d9000e49ebe5d5a54a275c6018cb6 (MD5) Previous issue date: 2011 / Resumo: O problema de particionamento de conjuntos (SPP, do inglês set partitioning problem) é considerado um dos problemas de otimização combinatória com mais vasta gama de aplicações. Para solucioná-lo, utilizam-se comumente métodos tradicionais para a resolução de problemas NP - Difíceis. Nesta dissertação, estuda-se o uso da combinação de relaxação Lagrangiana com planos de corte. Relaxação Lagrangiana é uma técnica que tem sido usada com bastante sucesso para atacar vários problemas NP-Difíceis. Os algoritmos relax-and-cut, em especial, onde se adicionam dinamicamente planos de corte a relaxações Lagrangianas, têm ganhado bastante destaque nas últimas décadas. Em [15], Cavalcante et al. aplicam um algoritmo relax-and-cut ao SPP e obtém ótimos resultados. No entanto, tal algoritmo, bem como implementações em geral da citada combinação, são ainda passíveis de refinamentos e extensões. O estudo proposto aqui é realizado por meio das seguintes extensões do referido algoritmo: a implementação de uma partida quente para o multiplicador de uma inequação adicionada; a incorporação do algoritmo a uma enumeração, gerando, assim, um branch-and-cut baseado em relaxação Lagrangiana para o SPP; a implementação do citado branch-and-cut com o emprego de relaxações alternativas e a implementação de uma versão distribuída do algoritmo / Abstract: The set partitioning problem (SPP) is considered one of the combinatorial optimization problems with the widest range of applications. To solve the SPP, one commonly uses traditional methods for NP-Hard problem solving. In this dissertation, we study the use of the combination of Lagrangean relaxation with cutting planes. Lagrangean relaxation is a technique that has been used quite successfully to tackle several NP-Hard problems. In particular, relax-and-cut algorithms, in which cutting planes are added dynamically to Lagrangean relaxations, have gained much importance in the last decades. In [15], Cavalcante et al. applied a relax-and-cut algorithm to the SPP and obtained promising results. However, that algorithm, as well as implementations of the mentioned combination in general, are still subject to refinements and extensions. The study proposed here is carried out through the following extensions of that algorithm: the implementation of a warm start to the multiplier of an added inequality; the incorporation of the algorithm to an enumeration, thus generating a Lagrangean relaxation based branch-and-cut for the SPP; the implementation of that branch-and-cut with the use of alternative relaxations and the implementation of a distributed version of the algorithm / 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

Orientadores : Francisco Antonio Menezes, Renato Soliani / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil / Made available in DSpace on 2018-08-02T00:38:32Z (GMT). No. of bitstreams: 1 Cortes_CarlosFredericoMacedo_M.pdf: 3755377 bytes, checksum: 3f5b34b5f7ad03935bf8c7ab7c01d33d (MD5) Previous issue date: 2002 / Resumo: Diminuir os custos com a construção de estruturas tornou-se ainda mais importante com a globalização da economia. No caso de treliças, uma estrutura leve, de fácil e rápida execução, o menor custo será representado pelo menor peso que a treliça poderá ter. O presente trabalho trata da otimização de peso de treliças planas com geometria e topologia fixadas. O processo de otimização proposto consiste em submeter uma configuração inicial de treliça plana a um programa que primeiramente sujeitará a função objetivo a um otimizador de caráter contínuo e nãolinear, restritas por funções que representam tensões admissíveis das barras (calculadas segundo a norma norte-americana de tensões admissíveis AISC/ASD 1989), limites para os deslocamentos nodais, áreas das seções transversais, além de equações de equilíbrio estático; com a finalidade de minimizar a área da seção transversal, mantendo o layout sugerido inicialmente. De posse desses valores ótimos, submetese novamente as mesmas equações a um outro otimizador, de caráter discreto e não-linear, acrescentando o conjunto de restrições com equações para a escolha de perfis disponíveis no mercado. Foi escrito o programa pTRUSS, em linguagem Pascal, que prepara um arquivo com os comandos específicos da linguagem interpretada GAMS. Esse arquivo gerado pelo programa pTRUSS é submetido ao software de otimização GAMS, que resolve o problema em estudo. Permitem-se dois tipos de análise: análise contínua e análise discreta. No primeiro caso o GAMS utiliza rotinas internas do MINOS 5.1 e no segundo o GAMS utiliza o otimizador DICOPT. Apresentam-se alguns exemplos encontrados na literatura para efeito de comparação de resultados. Compararam-se também os resultados obtidos pela proposta da dissertação com valores calculados com os programas SAP2000 e AutoMetal / Abstract: Due to the globalization of the economy, cost reduction has become more important. Concerning to the truss, a light, easy and quick build structure, the minimum cost will be represented by minimum weight that the truss could have. In this his work plane truss optimization with fixed geometry and fixed topology is studied. The proposed optimization process consists in applying to an initial configuration plane truss a code where, firstly, the Weight Objective Function will be subjected to a continuum and nonlinear solver, constrained by functions which represent the allowable stress members (according to the AISC-ASD/1989 code), displacement nodal limits and cross section area limits, as well as static equilibrium equations; focusing on minimizing the cross section area and keeping the initial configuration proposed. The optimal values obtained by continuum analysis will be used to submit again the same equations to another solver, now discrete and nonlinear. New equations of restraint that permit to choose available commercial sections were increased on program. Using Pascal language, it was made a program named p TRUSS that prepares a file with specific commands of language interpreted by GAMS. This file created by the pTRUSS program is submitted to the optimization software GAMS, that solves the problem in analysis. Two types of analyses are permitted: continuum analysis and discret analyses. In the former, the software GAMS uses internal routines of MINOS 5.1 and in the latter, GAMS uses the solver DICOPT. Examples from the literature are presented in order to compare the results. Commercial softwares as SAP2000 and AutoMetal were used to validate the results obtained by the software GAMS with the values calculed. / Mestrado / Estruturas / Mestre em Engenharia Civil

Orientador : Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T00:48:43Z (GMT). No. of bitstreams: 1 Costa_AlyssonMachado_M.pdf: 694166 bytes, checksum: 446bf3769d5078fa5450d0342397fc40 (MD5) Previous issue date: 2002 / Mestrado

Orientadores : Ariovaldo Verandio Garcia, Alcir Jose Monticelli / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T15:20:48Z (GMT). No. of bitstreams: 1 Haffner_SergioLuis_D.pdf: 1949827 bytes, checksum: 29124be4430da943062df08dab1fce19 (MD5) Previous issue date: 2000 / Doutorado

Made available in DSpace on 2014-06-12T18:27:30Z (GMT). No. of bitstreams: 2 arquivo1642_1.pdf: 3240172 bytes, checksum: 20b51b421dc923f18b5115c1606bb545 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O trabalho aqui apresentado consiste de um modelo para automação de horários escolares, cujo problema está baseado no estudo de casos brasileiros, e também consiste de uma análise da relação entre as restrições do problema e sua complexidade. O problema automação de horários escolares é um problema NP-completo, mesmo nos casos mais simples, onde as restrições mantidas são o mínimo absolutamente necessário. Aqui são construídas ou apresentadas provas desta relação entre as restrições e o problema. O modelo usa programação inteira para encontrar uma solução viável inicial. Uma vez encontrada, é aplicada uma heurística desenvolvida para trabalhar com trocas locais via um grafo chamado grafo híbrido. A solução viável inicial também pode ser encontrada por uma heurística que usa trocas via o grafo híbrido. Estas heurísticas são essencialmente meta-heurísticas busca tabu. O grafo híbrido, que é facilmente construído dos dados do problema, permitiu a definição de movimentos (mudanças) que aplicados a uma solução preservam o atendimento a um grande número de restrições. A descoberta do grafo híbrido fez uma grande diferença em nosso trabalho: nenhuma outra estrutura de dados na literatura (tanto quanto sabemos) tem a flexibilidade de acompanhar uma troca de horários atribuídos a um par de encontros às suas últimas conseqüências. As trocas são rápidas e milhares de soluções viáveis podem ser facilmente geradas e comparadas. A idéia do grafo híbrido tem aplicações a uma grande variedade de problemas de horários e de restrições de conflitos

Made available in DSpace on 2014-06-12T18:29:06Z (GMT). No. of bitstreams: 2 arquivo4270_1.pdf: 3240198 bytes, checksum: 40ce23c71a96036f67deaa9c0522df1a (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O trabalho aqui apresentado consiste de um modelo para automação de horários escolares, cujo problema está baseado no estudo de casos brasileiros, e também consiste de uma análise da relação entre as restrições do problema e sua complexidade. O problema automação de horários escolares é um problema NP-completo, mesmo nos casos mais simples, onde as restrições mantidas são o mínimo absolutamente necessário. Aqui são construídas ou apresentadas provas desta relação entre as restrições e o problema. O modelo usa programação inteira para encontrar uma solução viável inicial. Uma vez encontrada, é aplicada uma heurística desenvolvida para trabalhar com trocas locais via um grafo chamado grafo híbrido. A solução viável inicial também pode ser encontrada por uma heurística que usa trocas via o grafo híbrido. Estas heurísticas são essencialmente meta-heurísticas busca tabu. O grafo híbrido, que é facilmente construído dos dados do problema, permitiu a definição de movimentos (mudanças) que aplicados a uma solução preservam o atendimento a um grande número de restrições. A descoberta do grafo híbrido fez uma grande diferença em nosso trabalho: nenhuma outra estrutura de dados na literatura (tanto quanto sabemos) tem a flexibilidade de acompanhar uma troca de horários atribuídos a um par de encontros às suas últimas conseqüências. As trocas são rápidas e milhares de soluções viáveis podem ser facilmente geradas e comparadas. A idéia do grafo híbrido tem aplicações a uma grande variedade de problemas de horários e de restrições de conflitos

Orientadores: Pedro Jussieu de Rezende, Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-26T19:09:30Z (GMT). No. of bitstreams: 1 Zambon_MauricioJosedeOliveira_M.pdf: 2774684 bytes, checksum: 1d0ed1f5c1ae01b7646e4bffea6a3736 (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação, apresentamos a primeira abordagem algorítmica e os primeiros resultados experimentais da literatura para tratamento do Problema Cromático Discreto da Galeria de Arte (DCAGP). Trata-se de um problema de natureza geométrica que consiste de uma variante do clássico Problema da Galeria de Arte. Neste, deseja-se encontrar um conjunto de guardas com cardinalidade mínima que consiga vigiar toda uma dada galeria. Já no DCAGP temos por objetivo obter um conjunto de observadores que cubra a galeria e que admita uma coloração válida com o menor número de cores. Uma coloração é válida se dois observadores que veem um mesmo ponto recebem cores distintas. Abordamos a resolução deste problema através de duas abordagens: uma exata e uma heurística. Inicialmente, apresentamos uma heurística primal que fornece limitantes superiores de boa qualidade e, em seguida, um modelo de programação linear inteira para resolução exata do DCAGP. Este método foi capaz de resolver todas as instâncias de um extenso conjunto de galerias, representadas por polígonos simples aleatoriamente gerados, de até 2500 vértices, em menos de um minuto. Já num outro conjunto de instâncias onde a representação inclui polígonos com buracos e polígonos fractais de von Koch com até 800 vértices, o método encontrou soluções comprovadamente ótimas para 80% das instâncias em menos de 30 minutos. No contexto dessas soluções, discutimos o uso de lazy-constraints e de técnicas de fortalecimento do modelo, assim como uma breve análise da dificuldade das instâncias. Reportamos ainda resultados da utilização de relaxação Lagrangiana, para obtenção de bons limitantes, principalmente superiores, e também resultados obtidos por meio de uma variação da técnica relax-and-fix. Finalmente, discutimos um processo de branch-and-price para resolução exata do DCAGP / Abstract: In this dissertation, we present the first algorithmic approach and the first experimental results in the literature for solving the Discrete Chromatic Art Gallery Problem (DCAGP). This problem is geometric in nature and consists of a variation of the classic Art Gallery Problem. In the latter, we want to find a minimum cardinality guard set that is able to watch over a given gallery. On the other hand, in the DCAGP, the objective is to find a set of watchers that covers the gallery and admits a valid coloring with a minimum number of colors. A coloring is valid if two watchers that observe a same point are assigned different colors. To solve this problem we apply two approaches: an exact and a heuristic one. Firstly, we present a primal heuristic able to provide good quality upper bounds, and subsequently an integer programming model that yields exact solutions for the DCAGP. This method was able to solve all instances from an extensive set of galleries, represented by randomly generated simple polygons, of up to 2500 vertices, in less than one minute. On another set of instances, where the representation includes polygons with holes and fractal von Koch polygons, with up to 800 vertices, this method found proven optimal solutions for 80% of the instances in less than 30 minutes. In the context of these solutions, we discuss the use of lazy constraints and techniques for strengthening the model, besides a brief analysis of the hardness of the instances. Moreover, we report on results obtained through a Lagrangian relaxation, mainly as a means to obtain good upper bounds, as well as from a variation of the relax-and-fix technique. Lastly, we discuss a branch-and-price process for solving the DCAGP to exactness / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

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.