Tese de doutoramento. Programa Doutoral em Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2012

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas. Programa de Pós-Graduação em Matemática e Computação Científica. / Made available in DSpace on 2012-10-23T16:31:05Z (GMT). No. of bitstreams: 1 258571.pdf: 4103462 bytes, checksum: e408cf9b53562ebbc62cffe0b1b88595 (MD5) / Neste trabalho ser´a apresentado o programa POLIEDRO V1 que tem como objetivo visualizar poliedros limitados (em R2 e R3), para auxiliar na compreens#ao da evoluc¸#ao dos algoritmos Simplex e Branch-and-Bound. Primeiramente, ser#ao estudados alguns conceitos fundamentais de otimizac¸ #ao irrestrita e restrita, as condic¸ #oes de otimalidade e o problema dual em Programac¸ #ao Linear (PL). A segunda fase do texto concentra-se no estudo te´orico de poliedros, formas de representar poliedros e caracterizac¸ #ao de faces. Ap´os, ´e apresentado o programa POLIEDRO V1 em linguagem Matlab, que consiste em visualizar politopos, gerando faces atrav´es da selec¸ #ao e ordenac¸ #ao de v´ertices. A ´ultima fase do trabalho concentra-se no estudo e desenvolvimento dos algoritmos Simplex e Branch-and-Bound. Aplica-se o programa POLIEDRO V1 em Programac¸ #ao Linear visualizando a regi#ao vi´avel como politopo e apresentase a evoluc¸ #ao, passo a passo, do m´etodo Simplex. J´a em Programac¸ #ao Inteira (PI) visualiza-se graficamente o m´etodo Branch-and-Bound, resolvendo o problema de Programac¸ #ao Linear Inteira (PLI) atrav´es de subproblemas gerados por planos de corte. Os subproblemas s#ao resolvidos recursivamente pelo m´etodo Simplex. This work presents the program POLIEDRO V1, whose objective is to visualize bounded polyhedra in R2 and R3, to help the understanding of the evolution of the simplex and branch and bound algorithms. Initially some fundamental concepts in unconstrained and constrained optimization are studied, including the optimality conditions and the dual problem in Linear Programming. The second part of the text is dedicated to the theoretical study of polyhedra, ways of representing polyhedra and the characterization of faces. The program POLIEDRO V1 is then presented in the languageMatlab, consisting in the visualization of polytopes by generating facets through the selection and ordering of vertices. The last phase of the work concentrates on the study and development of the Simplex and Branch-and-Bound algorithms. The program POLIEDRO V1 is applied to visualize the feasible region of a linear programming problem, on which the step by step evolution of the simplex method is drawn. In Integer Programming, the branch-and-bound algorithm is graphically represented by solving recursively the linear programming subproblems generated by adding cutting planes. These subproblems are solved by the simplex method and visualized.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica. / Made available in DSpace on 2012-10-22T11:04:36Z (GMT). No. of bitstreams: 1 244296.pdf: 635316 bytes, checksum: 0f00504d9a1fb149f3556a6e9cb5e254 (MD5) / A alocação ótima de gás de injeção busca taxas de injeção para poços de petróleo operados por gas-lift que otimize uma função objetivo, normalmente que maximize o lucro, em um campo de petróleo. Apesar do grande interesse nesta classe de problemas, a maioria dos trabalhos nesta área não os trata adequadamente, produzindo soluções sub-ótimas e não considerando explicitamente decisões discretas de ativação e desativação dos poços. Neste trabalho buscamos obter taxas ótimas de injeção de gás considerando restrições de capacidade máxima de gás disponível e restrições de precedência de ativação dos poços. Como a curva de performance do poço, que caracteriza sua resposta, é não-linear, aplicamos a ela um procedimento de linearização por partes. Então utilizamos programação linear inteira mista, que possui um grande ferramental teórico e algorítmico. Este problema pertence a classe NP-Difícil, então apresentamos um procedimento para obtenção de cortes que acelera a busca da resposta ótima. Experimentos computacionais mostraram que estes cortes podem reduzir o número de iterações do algoritmo de otimização. A programação inteira mista também nos garante que a solução ótima global seja obtida, e permite uma medida da qualidade da solução pelos limites primal-dual, caso a execução do algoritmo seja interrompida. Desenvolvemos também uma interface de otimização para o usuário, que permite que ele especifique uma instância de um problema de alocação de gás de injeção e obtenha a solução ótima, sem que para isto ele necessite conhecer detalhes do modelo e do algoritmo de resolução do problema. Optimum lift-gas allocation searches gas injection rates for wells in gas-lifted oil fields that optimizes an objective, generally profit. Despite the long interest, most of the literature lack rigor, producing sub-optimal solutions and not treating explicitly discrete decisions and well activation and deactivation. In this work, we present a formulation for optimum lift-gas allocation with maximum available gas and activation precedence constraints. We use mixed integer linear programming with piecewise linearization of the well performance curves, because of its great theoretical and algorithmic possibilities. This problem belongs to the NP-Hard class, thus we propose a procedure to obtain cutting planes that accelerates the search for the optimum allocation. Computational experiments showed that these cuts can reduce the number of algorithmic iterations. Mixed integer programming also produces globally optimum solutions and gives a measure of the solution quality by the primal-dual bounds, in case of the algorithmic execution is interrupted. We also have developed an optimization interface that allows the user to specify an instance of the lift-gas allocation problem and obtain its solution, without necessarily knowing details of the model and the resolution algorithm.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2015-05-20T18:18:24Z No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-05-20T19:03:59Z (GMT) No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Made available in DSpace on 2015-05-20T19:03:59Z (GMT). No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) Previous issue date: 2015 / Este trabalho explora a informação estrutural de relações entre variáveis binárias em problemas de Programação Inteira por meio de grafos de conflitos. Tal estrutura possui um papel fundamental na construção de métodos exatos e heurísticos de resolução. Nesse sentido, o presente trabalho propõe e desenvolve técnicas baseadas na análise de grafos de conflitos para obtenção de soluções factíveis e limites duais fortes para problemas de Programação Inteira. Foram desenvolvidas otimizações nas técnicas de detecção de conflitos, que permitiram a construção rápida de grafos densos mediante a análise de restrições. A obtenção de limites duais fortes para programas inteiros é realizada por uma rotina desenvolvida para geração de desigualdades válidas. Essa rotina é responsável por gerar cortes de clique e ciclo ímpar e inseri-los na relaxação linear, reforçando os limites duais e acelerando a convergência para a solução ótima. Para obter soluções factíveis para programas binários foi desenvolvido um resolvedor heurístico, que utiliza as relações lógicas entre variáveis para construir uma solução inicial e melhorá-la por meio de uma busca local. A busca local executa uma cadeia de movimentos a cada iteração, que permite corrigir a infactibilidade de uma solução ou, até mesmo, saltar de uma solução factível para outra. Considerando a produção de limites duais fortes, os resultados obtidos pela rotina de geração de desigualdades desenvolvida mostraram uma convergência mais rápida em relação à rotina de separação de cortes do resolvedor COINOR Branch-and-Cut. Em relação à obtenção de factibilidade, o resolvedor heurístico foi apto a gerar soluções para um número significativo de problemas de Programação Inteira Binária, considerando tempos restritos de execução. _________________________________________________________________________________ / ABSTRACT: This work explores the structural information of relations between binary variables in Integer Programming problems using conflict graphs. Such structure has a fundamental role in the construction of exact and heuristic solving methods. In this sense, the present work proposes and develops techniques based on the analysis of conflict graphs to obtain feasible solutions and strong dual bounds for Integer Programming problems. Optimizations were developed in the conflict detection techniques that allowed the fast construction of dense graphs through the constraints analysis. The obtaining of strong dual bounds for integer programs is performed by a routine developed for the generation of valid inequalities. This routine is responsible for generating clique and odd hole cuts and insert them into the linear relaxation, strengthening the dual bounds and accelerating the convergence to the optimal solution. To obtain feasible solutions for binary programs it was developed a heuristic solver, which uses the logical relations between variables to build an initial solution and improve it through a local search. Local search performs chains of movements at each iteration, which allows to fix infeasibilities of a solution or even jump from a feasible solution to another. Considering the production of strong dual bounds, the results obtained by the developed routine for generating inequalities showed a faster convergence compared with the cut separation routine of COIN-OR Branch-and-Cut solver. Regarding the production of feasible solutions, the heuristic solver was able to generate solutions to a significant number of Integer Binary Programming problems considering restricted runtimes.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T19:24:02Z (GMT). No. of bitstreams: 1 Meneses_ClaudioNogueirade_M.pdf: 3238026 bytes, checksum: bd3af0337218ec84f17c26c345abf4f8 (MD5) Previous issue date: 1997 / Resumo: Dado um retângulo R e um conjunto finito não vazio P de pontos no interior de R, estudamos o problema de particionar R em retângulos menores tal que nenhum ponto em P está no interior de qualquer retângulo da partição. O objetivo é minimizar a soma dos comprimentos dos segmentos de reta definindo a partição. Este problema é NP-difícil e uma generalização deste tem aplicação em projeto de circuitos VLSI. Neste trabalho implementamos os principais algoritmos de aproximação que têm sido propostos para este problema e propomos dois diferentes modelos de programação linear inteira. No primeiro modelo, onde variáveis são associadas a segmentos de reta, fazemos uma investigação do poliedro associado ao problema. Inequações lineares definindo facets são apresentadas e resultados computacionais para um algoritmo Branch-and-Cut baseado nestas inequações são reportados. O segundo modelo é baseado em uma redução do problema em questão para o problema set partitioning. Um algoritmo Branch-and-Price para este modelo foi implementando e os resultados são comparados com aqueles obtidos pelo algoritmo Branch-and-Cut. Os experimentos computacionais realizados mostraram a viabilidade da resolução exata deste problema através de técnicas de programação linear inteira, pelo menos para instâncias de médio porte (|P| = 200). / Abstract: Given a rectangle R in the plane and a non empty finite set P of points in the interior of R, we study the problem of partitioning R into smaller rectangles such that no point in P is interior to any rectangle of the partition. The goal is to minimize the sum of the lengths of the straight line segments defining the partition. This problem is NP-hard and a generalization of it have application in VLSI design. In this work we implement the main approximation algorithms that have been proposed for this problem and propose two different integer programming models. In the first one, the variables are associated to line segments and we investigate the polyhedron associated to this model. Facet defining inequalities are presented and computational results obtained by a Branch-and-Cut algorithm based on these inequalities are reported. The second model is based on a Set Partitioning formulation. A Branch-and-Price algorithm for this model has been implemented and the results are compared with those obtained by the Branch-and-Cut algorithm. The computational results show that, at least for medium sized instances (IPI = 200), the problem can be solved exactly using Integer Programming techniques. / Mestrado / Mestre em Ciência da Computação

Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T19:24:13Z (GMT). No. of bitstreams: 1 Barboza_EduardoUchoa_M.pdf: 2477337 bytes, checksum: a3047f5638be88ee13e8e89477e4f570 (MD5) Previous issue date: 1997 / Resumo: A classificação de dados consiste em separar um conjunto de objetos, descritos por um conjunto de dados, em classes, de forma a que objetos na mesma classe sejam semelhantes entre si. A classificação freqüentemente é usada como uma ferramenta de pesquisa científica. Os objetivos de uma classificação podem diferir de acordo com as necessidades e com a origem dos dados sobre os objetos a classificar. Em alguns contextos existe interesse em associar os objetos aos vértices de um grafo, de forma que a semelhança entre os objetos esteja relacionada a proximidade nesse grafo. Os métodos existentes, para aplicações nestes contextos~ obrigam cada classe a formar um único componente conexo dentro do grafo. Chamamos essa abordagem de conexidade estrita e propomos a idéia de classificação com conexidade flexibilizada, ou seja a concepção de métodos que permitam a um usuário especificar o número de componentes de cada classe no grafo e mostramos porque essa flexibilização é desejável. Em seguida, estudamos a resolução de um problema computacional resultante da flexibilização da conexidade, o Problema da Atribuição ?-Conexa (PAgC). Demonstramos a NP-completude desse problema e apontamos alguns casos polinomiais. Então, concentramo-nos no estudo de diferentes formas para modelar matematicamente a conexidade flexibilizada. Os resultados obtidos podem ser naturalmente aplicados a outros problemas onde tal conexidade é necessária. Finalmente, propomos dois algoritmos para resolver (PAgC). Um baseado na técnica de branch-and-bound e outro na de branch-and-price. Uma comparação dos resultados obtidos por cada técnica é apresentada na seqüência. em estudo de classes de desigualdades válidas, capazes de melhorar substancialmente ambos os algoritmos, conclui a dissertação. / Abstract: Classification of objects amounts to defining, say, K clusters on a set of N objects such that object in a same cluster are alike. Classification is often used as a tool for scientific research. Some important contexts of objects classification use enhanced methods where the objects are associated to vertices of a graph. Proximity between two objects in this graph usually means that the dissimilarity between them is small. The methods applied in such contexts require each cluster to define a single connected component on this graph. We call this strict connectivity approach and we propose the idea of flexible connectivity. This suggests the development of methods where the user may specify the number of connected components each cluster may form on the graph. We present reasons for this flexibilization. Next, we study the computational problem derived from the flexible connectivity, the y-Connected Assignment Problem (PAgC). We show this problem to be NP-complete and we point out some polynomial cases. Then, we concentrate our effort on deriving formulations for considering this flexible connectivity. Clearly, the conceived models can be applied to other problems where connectivity constraints are to be considered. Finally, we propose two algorithms to solve PAgC. One based on the branch-and-cut technique and other on the branch-and-price technique. A comparison between the results obtained with each technique is presented. We conclude this work studying classes of valid inequalities capable of improving the efficiency of both algorithms. / Mestrado / Mestre em Ciência da Computação

Orientadores : Cid Carvalho de Souza, Abilio Pereira de Lucena Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-31T15:05:43Z (GMT). No. of bitstreams: 1 Calheiros_FelipeCarneiro_M.pdf: 3990645 bytes, checksum: b967de7c86c5f19eb910cd59cf0cd246 (MD5) Previous issue date: 2001 / Resumo: Seja P um conjunto finito de pontos do plano localizados no interior de um retângulo R. Considere as partições de R em retângulos menores. Se nenhum ponto de P for interior a algum destes retângulos, então a partição é viável e seu custo é a soma do comprimento dos segmentos que a definem. O problema de partição retangular (RG-P) busca uma partição retangular de R de custo mínimo. Experimentos descritos na literatura envolvendo algoritmos exatos para esse problema indicam que instâncias do RG-P com pontos não corretilineares em P, chamado de RG-NLP, são as mais difíceis de serem resolvidas até a otimalidade. Esse trabalho apresenta propriedades geométricas de soluções ótimas do RGNLP, que permitem uma redução substancial do número de variáveis do modelo natural de programação inteira. Adicionalmente, essas propriedades levam a desigualdades satifeitas por todas as soluçoes ótimas. Tais desigualdades são usadas em um algoritmo de Relaxação Lagrangeana com Planos de Corte (Relax and Cut). Enquanto resolvedores de programação linear não conseguem computar o enorme modelo para instâncias do RG-NLP, o algoritmo lagrangeano produziu excelentes limitantes. Além disso, para as instâncias em que este algoritmo não foi capaz de provar otimalidade, o número de variáveis eliminadas durante a sua execução foi suficiente para permitir a execução do resolvedor de programação linear. O algoritmo híbrido combinando a Relaxação Lagrangeana e Programação Linear foi capaz de resolver instâncias mais do que duas vezes maiores que as apresentadas na literatura. Além disso, os grandes modelos de partição gerados e resolvidos neste trabalho figuram entre os maiores já resolvidos até a otimalidade / Abstract: Let P be a finite set of points in the plane lying in the interior of a rectangle R. Consider the partitions of R into smaller rectangles. Ir no point in P is interior to any such rectangle, the partition is feasible and its length is the sum of the lengths of the segments defining it. The Rectangular Partition Problem (RG-P) seeks for a feasible partition of R of minimum length. Experiments reported in the literature with exact algorithms based on Integer Programming (IP) indicate that RG-P instances with non corectilinear points in P, called RG-NLP, are the hardest to solve to optimality. This work presents structural properties of optimal RG-NLP solutions which allow for substantial reductions on the number of variables in the natural IP model of the problem. In addition, these properties led to inequalities that are satisfied by alI optimal solutions. Such inequalities are used in a Lagrangean Relax and Cut algorithm for RG-NLP. While commercial LP solvers cannot compute the huge models for RG-NLP instances in general, the Lagrangean algorithm produces very good bounds. For the few test instances where Lagrangean bounds alone are not enough to prove optimality, they allow enough variables to be fixed that an LP solver can now be applied. The hybrid algorithm combining the Lagrangean and the LP phases solves RG-NLP instances more than twice as large as those in the literature. Additionally, the large set partitioning instances solved with this algorithm figure among the biggest ever solved to prove optimality / Mestrado / Mestre em Ciência da Computação

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T14:25:03Z (GMT). No. of bitstreams: 1 Nascimento_JulianaMartinsdo_M.pdf: 4967741 bytes, checksum: 20ceacaab689704941f1f9d3ec41695a (MD5) Previous issue date: 2002 / Resumo: Problemas de otimização combinatória são classificados na grande maioria das vezes como NP-difíceis. Para estes problemas, não são conhecidos algoritmos polinomiais capazes de resolvê-los. Logo, é necessário o desenvolvimento de estratégias eficientes para tratá-los. O desenvolvimento de técnicas híbridas para a resolução destes problemas tem por objetivo valorizar os pontos fortes dos métodos que estão sendo empregados, para, desta forma, compensar os pontos mais fracos, criando um procedimento de qualidade superior. Este trabalho propõe um método híbrido que integra técnicas de Programação por Restrições com metaheurísticas de Busca Tabu para atacar o problema de escalonamento de atividades na produção de um campo petrolífero. Como não há resultados anteriores para serem comparados com os resultados obtidos para as instâncias consideradas neste trabalho, modelos de programação matemática foram utilizados para a obtenção de limitantes duais para a solução do problema. Além disso, para determinar quão robusta é a técnica proposta, uma análise de sensibilidade foi realizada sobre as instâncias consideradas / Abstract: Combinatorial optimization problems are generally NP-hard. As it is not known polinomial time algorithms to solve them, it is necessary to develop efficient strategies to treat them. The aim in developing hybrid techniques to solve combinatorial optimization problems is to strength the good features of the methods that are being combined to compensate for their weakness. In this paper, we propose a hybrid method that combines Constraint Programming techniques and Tabu Search metaheuristics to schedule the activities involved in the production process of an oil field. As there are no previous results to estabilish a comparision with the results obtained with the instances considered in this work, bounds were determined using mathematical programming models. Finally, to estabilish the robusteness of proposed method, a sensibility analysis was performed over the considered instances / Mestrado / Mestre em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T19:57:30Z (GMT). No. of bitstreams: 1 Teodoro_AlanAugusto_M.pdf: 1993309 bytes, checksum: eb9abfe2294e3e44de68abc5fba42be3 (MD5) Previous issue date: 2003 / Resumo: Neste trabalho é realizado um estudo experimental de técnicas de otimização para gerar soluções eficientes para o problema do corte bidimensional, que pode ser definido como: dado um número finito n de itens retangulares de largura li, comprimento Ci e demanda di, a serem obtidos de retângulos maiores de dimensão LxC, encontrar padrões de corte que atendam a uma demanda de itens utilizando o menor número possível de retângulos maiores. O problema foi formulado através de um modelo de programação linear inteira. Para obter soluções de custo reduzido para o problema, aplicamos o método de geração de colunas, obtendo então soluções viáveis para o problema relaxado do programa linear inteiro. Utilizamos um algoritmo de aproximação para obter uma solução inicial de qualidade e métodos de arredondamento com tratamento de problema residual para transformar a solução fracionária em soluções viáveis para o problema. Finalmente, diversos estudos são realizados através de testes computacionais / Abstract: In this work we describe an experimental study of optimization techniques to generate efficient results for the two-dimensional cutting stock problem which can be defined as follows: given a finite number n of rectangular items of width li, length Ci and demand di, to be cut from larger rectangles with dimensions LxC, find cutting pattems which attend the demand of the requested items minimizing the number of larger rectangles. The problem is formulated as an integer programming mode!. To obtain solutions with reduced cost to the problem, we apply the column generation method, obtaining feasible solutions for the relaxed integer programo We use an approximation algorithm to generate a good initial solution and rounding techniques with treatment of the residual problem to transform the fractional solution into feasible solutions to the problem. Finally, several studies are realized through computational experiments / Mestrado / Engenharia de Computação / Mestre em Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T19:56:42Z (GMT). No. of bitstreams: 1 Ramos_Luciana_M.pdf: 2723419 bytes, checksum: 9c82eed676fdf2e14f006a3a84c61941 (MD5) Previous issue date: 2003 / Mestrado / Engenharia de Computação / Mestre Profissional em Computação