Pessoas com deficiências possuem muitas dificuldades em participar do mercado de trabalho, possuindo uma taxa de desemprego bem maior do que a média populacional. Isso motiva o estudo de novos modos de produção que permitam incluir essas pessoas com baixo custo operacional. Neste trabalho é feito um estudo sobre a inclusão de pessoas com deficiências em flow shops com o objetivo de minimizar o makespan. Como flow shops normalmente possuem poucas máquinas, o foco do estudo é na inserção de um e dois trabalhadores. O problema é definido, são propostos modelos matemáticos e uma solução heurística para resolvê-lo, assim como instâncias de teste realistas. Nos testes computacionais a performance dos modelos e da heurística é avaliada e a utilidade prática deste modelo de inclusão é analisada. Nós concluímos que o problema pode ser resolvido de forma satisfatória e que a inclusão de trabalhadores com deficiêcia emn flow shops é economicamente viável. / Persons with disabilities have severe problems participating in the job market and their unemployment rate is usually much higher than the average of the population. This motivates the research of new modes of production which allow to include these persons at a low overhead. In this work we study the inclusion of persons with disabilities into flow shops with the objective of minimizing the makespan. Since flow shops usually have only a few machines, we focus on the inclusion of one and two workers. We define the problem, propose mathematical models and a heuristic solution, as well as realistic test instances. In computational tests we evaluate the performance of the models and the heuristic, and assess the utility of such a model of inclusion. We conclude that the problem can be solved satisfactorily, and that including workers with disabilities into flow shops is economically feasible.

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T02:29:56Z (GMT). No. of bitstreams: 1 Couto_MarceloCastilho_M.pdf: 3682547 bytes, checksum: 899151df78f8e6950ce90ea8215ded91 (MD5) Previous issue date: 2010 / Resumo: Nesta dissertação, faz-se um amplo estudo multidisciplinar sobre duas variantes de um problema geométrico NP-DIFÍCIL, o Problema da Galeria de Arte, que é analisado tanto pela ótica geométrica quanto combinatória. O objetivo consiste em minimizar o número de guardas suficientes para cobrir todo o interior de uma galeria de arte, representada por um polígono simples. Dentre as muitas variantes desse problema, o foco foi dado àquela onde os guardas são estacionários e restritos aos vértices do polígono, ortogonal ou simples, sem obstáculos. Propõe-se neste trabalho um algoritmo iterativo exato que é capaz de resolver ambas as variantes do problema. Nesse algoritmo, o problema original é discretizado, reduzido a um problema combinatório, o Problema da Cobertura de Conjuntos, e modelado por programação linear inteira. A redução entre os problemas que assegura a corretude do algoritmo e as provas de exatidão e convergência para uma solução ótima do problema original são detalhadas. Apresenta-se também uma extensa experimentação de uma implementação desse algoritmo com o intuito de validar seu uso prático e analisar as várias estratégias propostas aqui para a discretização inicial da galeria. São dados resultados para instâncias com até 2500 vértices, mais de dez vezes o tamanho das maiores instâncias resolvidas exatamente na literatura pré-existente. Mostra-se que o número de iterações executadas pelo algoritmo está extremamente relacionada com o modo como a galeria é inicialmente discretizada. Considerando a estratégia de discretização com o melhor desempenho geral, tem-se que, na prática, o algoritmo converge para uma solução ótima para o problema original em um baixo tempo computacional e em um número de iterações que é ordens de grandeza aquém do limite teórico resultante da análise de pior caso / Abstract: In this dissertation, a broad multidisciplinary study is done on two variants of a geometrical NP-HARD problem, the Art Gallery Problem, which is approached both from geometrical and combinatorics perspectives. The goal is to minimize the number of guards sufficient to cover the interior of an art gallery whose boundary is represented by a simple polygon. Among the many variants of the problem, the focus was on one where the guards are stationary and are restricted to vertices of the polygon, orthogonal or simple, without holes. We propose an iterative exact algorithm to solve both variants of the problem. In this algorithm, the original problem is discretized, reduced to a combinatorial problem, the Set Cover Problem, and modeled as an integer linear program. The reduction between the problems, which ensures the correctness of the algorithm, and the proofs of its exactness and convergence to an optimal solution are detailed. We also present an extensive experimentation of an implementation of this algorithm in order to validate its practical use and analyze the various strategies proposed here for the initial discretization of the gallery. Results are given for instances with up to 2500 vertices, more than ten times the size of the largest instances solved to optimality in prior literature. It is shown that the number of iterations performed by the algorithm is highly related to how the gallery is initially discretized. Considering the discretization strategy with the best performance in practice, the algorithm converges to an optimal solution for the original problem in a low computation time and in a number of iterations that is orders of magnitude below the theoretical bound arising from the worst case analysis / Mestrado / Geometria Computacional e Otimização Combinatória / Mestre em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T08:02:12Z (GMT). No. of bitstreams: 1 Andrade_CarlosEduardode_M.pdf: 1512396 bytes, checksum: aac3459428d8f61b130828587f727265 (MD5) Previous issue date: 2006 / Resumo: Problemas de corte e empacotamento aparecem freqüentemente na indústria e comércio, e sua solução de forma otimizada pode trazer grandes ganhos em diversos setores.Um problema muito comum, notadamente no setor têxtil e do papel, é o corte de um rolo ou faixa de um determinado material para obtenção de itens menores, onde temos por objetivo utilizar a menor extensão do rolo/faixa possível. Este problema, conhecido como Problema de Empacotamento Bidimensional em Faixas (PEBF), é tido como um problema de otimização combinatória de difícil resolução. Neste trabalho, apresentamos um algoritmo exato para o PEBF restrito a cortes de dois estágios (PEBF2). O algoritmo usa a técnica de branch-and-price, que utiliza, por sua vez, heurísticas baseadas em algoritmos aproximados para a obtenção de limitantes superiores. O algoritmo se mostrou eficaz na obtenção de soluções para instâncias de pequeno e médio porte / Abstract: Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances / Mestrado / 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-08T14:02:44Z (GMT). No. of bitstreams: 1 Santos_RafaelFranciscodos_M.pdf: 909075 bytes, checksum: b4d466696cb4f640a50eca288dfccd5c (MD5) Previous issue date: 2006 / Resumo: Nesta dissertação propomos um uso mais geral dos Cortes Canônicos (CCs) introduzidos por Balas e Jeroslow ([2]) no método de Ramificação Local (RamLoc) de Fischetti e Lodi ([6]). A ramificação local é uma heurística de propósito geral para Programação Inteira Mista (MIP) que explora vizinhanças definidas através da adição de inequações lineares ao modelo original. Estas inequações determinam subproblemas que são computados mais rapidamente pelos resolvedores de MIP. Uma análise da execução da RamLoc indicou que, em algumas situações, ela acrescenta cortes de ramificação local muito superficiais (i.e.,que descartam poucas soluções) e que estes cortes ocorrem com grande freqüência. Como os cortes de ramificações locais de Fischetti e Lodi são casos especiais dos CCs para programação inteira 0?1, n'os propomos a incorporação de CCs mais profundos (i.e.,que descartam mais soluções) à RamLoc. Executamos o algoritmo resultante sobre 25 das 29 instâncias testadas em [6] e obtivemos melhores resultados do aqueles alcançado pela RamLoc original e pelo resolvedor comercial de MIP XPRESS com seus parâmetros default. Uma outra investigação que empreendemos foi a inclusão dos CCs na heurística para modelos gerais de programação inteira mista RINS ([3]). Esta heurística surgiu durante o desenvolvimento desta dissertação e apresentou um bom desempenho. Realizamos alguns testes com as mesmas instâncias sobre as quais a RamLoc foi executada e obtivemos resultados promissores. Por fim, além da utilização dos CCs em heurísticas, criamos uma estratégia de ramificação que pode ser embutida nos algoritmos de branch-and-cut dos resolvedores de MIP. Denominamos esta estratégia de dive branching e a implementamos no resolvedor XPRESS. Em experimentos conduzidos com o mesmo conjunto de instâncias anteriores, obtivemos resultados de melhor qualidade do que aqueles produzidos pelo XPRESS com seus parâmetros default / Abstract: In this dissertation we propose a broader usage of the Canonical Cuts (CC) introduced by Balas and Jeroslow ([2]) in the Local Branching method (LB) of Fischetti and Lodi ([6]). The LB is a general purpose heuristic for Mixed Integer Programming (MIP) that explores neighborhoods defined by the addition of linear inequalities to the original model. These inequalities determine subproblems that are computed more quickly by MIP solvers. An analysis of the execution of LB indicated that, in some situations, it adds local branching cuts that are too superficial (i.e., chopping off few solutions) and that these cuts happen very often. Since the local branching cuts of Fischetti and Lodi are special cases of CCs for 0?1 integer programming, we propose to incorporate deeper CCs (i.e, chopping of more solutions) to LB. We executed the resulting algorithm on 25 out of the 29 instances tested in [6] and we obtained better results than those attained by the original LB and by the XPRESS commercial MIP solver under default settings. Another research that we carried out was the inclusion of CC to the RINS heuristics for general mixed integer programs ([3]). This heuristic appeared during the development of this dissertation and showed a good performance. We carried out some tests with the same instances on which LB was tested and the results are promising. Finally, besides using the CCs in heuristics, we created a branching strategy that can be embedded to the branch-and-cut algorithms of the MIP solvers. We called it dive branching and implemented it in the XPRESS solver. In experiments with the same set of instances as before, we obtained results of better quality than those produced by XPRESS with default settings / Mestrado / Mestre em Ciência da Computação

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T22:48:39Z (GMT). No. of bitstreams: 1 DalGallo_RodrigoMarchiori_M.pdf: 685835 bytes, checksum: 9e0e8765da2a5926a7a5952b31283ca5 (MD5) Previous issue date: 2008 / Resumo: O trabalho tem como objetivo a implementação de um método heurístico para a resolução de problemas de programação inteira com dimensão completa. Nos atemos aos problemas de corte e empacotamento, mas a aplicação pode ser estendida a qualquer outro problema dessa classe. No problema de programação linear relaxado aplicamos o Método de Gilmore & Gomory e a partir da solução contínua obtida através do método simplex, aplicamos o método heurístico e comparamos os resultados com as soluções exatas obtidas a partir de Branch & Bound / Abstract: The objective of this dissertation is the implementation of a heuristic method to solve integer linear programming problems with complete dimension. We worked specifically with cutting and stock problems, but it can be aplied to any other class of integer problems. We used the Gilmore & Gomory method of column generation and starting by the continuous solution obtained with simplex method, we aplied the heuristic method and made a comparation of results with the exact solutions obtained by the Branch&Bound method / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T20:54:55Z (GMT). No. of bitstreams: 1 Meira_LuisAugustoAngelotti_D.pdf: 974332 bytes, checksum: 7097ff3ed310db70e5026afabc41ceb6 (MD5) Previous issue date: 2007 / Resumo: O trabalho desenvolvido neste doutorado consistiu em conceber algoritmos para uma série de problemas NP-dificeis sob a abordagem de aproximabilidade, complementado com resultados heurísticos e também de programação inteira. O estudo foi focado em problemas de classificação e particionamento em grafos, como classificação métrica, corte balanceado e clusterização. Houve um equilíbrio entre teoria e aplicabilidade, ao obterse algoritmos com bons fatores de aproximação e algoritmos que obtiveram soluções de qualidade em tempo competitivo. O estudo concentrou-se em três problemas: o Problema da Classificação Métrica Uniforme, o Problema do Corte Balanceado e o Problema da Localização de Recursos na versão contínua. Inicialmente trabalhamos no Problema da Classificação Métrica Uniforme, para o qual propusemos um algoritmo O (logn)-aproximado. Na validação experimental, este algoritmo obteve soluções de boa qualidade em um espaço de tempo menor que os algoritmos tradicionais. Para o Problema do Corte Balanceado, propusemos heurísticas e um algoritmo exato. Experimentalmente, utilizamos um resolvedor de programação semidefinida para resolver a relaxação do problema e melhoramos substancialmente o tempo de resolução da relaxação ao construir um resolvedor próprio utilizando o método de inserção de cortes sobre um sistema de programação linear. Finalmente, trabalhamos com o problema de Localização de Recursos na variante contínua. Para este problema, apresentamos algoritmos de aproximação para as métricas l2 e l2 2. Este algoritmo foi aplicado para obter algoritmos de aproximação para o problema k-Means, que 'e um problema clássico de clusterização. Na comparação ao experimental com uma implementação conhecida da literatura, os algoritmos apresentados mostraram-se competitivos, obtendo, em vários casos, soluções de melhor qualidade em tempo equiparável. Os estudos relativos a estes problemas resultaram em três artigos, detalhados nos capítulos que compõem esta tese / Abstract: We present algorithms for combinatorial optimization NP-hard problems on classification and graph partitioning. The thesis concerns about theory and application and is guided by an approximation algorithms approach, complemented with heuristics and integer programming. We proposed good approximation factor algorithms as well as algorithms that find quality solutions in competitive time. We focus on three problems: the Metric Labeling Problem, the Sparsest Cut Problem and the Continuous Facility Location Problem. For the Metric Labeling Problem, we proposed an O(log n)-approximation algorithm. In the experimental analysis, this algorithm found high quality solutions in less time than other known algorithms. For the Sparsest Cut Problem we proposed heuristics and an exact algorithm. We built an SDP Solver to the relaxed formulation using a semi-infinity cut generation over linear programming. This approach considerably reduces the time used to solve the semi definite relaxation compared to an open source semi definite programming solver. Finally, for the Continuous Facility Location Problem we present approximation algorithms to the l2 and l2 2 distance function. These algorithms are used to obtain approximation algorithms to the k-Means Problem, which is a basic clustering problem. The presented algorithms are competitive since they obtain in many cases better solutions in equivalent time, compared to other known algorithms. The study of these problems results in three papers, which are detailed in chapters that make this thesis / Doutorado / Otimização Combinatoria / Doutor em Ciência da Computação

Nesta tese, estudamos o problema de Empacotamento de Bicliques. Um biclique é um grafo bipartido completo. No problema de Empacotamento de Bicliques são dados um inteiro k e um grafo bipartido G e deseja-se encontrar um conjunto de k bicliques, subgrafos de G, dois a dois disjuntos nos vértices, tal que a quantidade total de arestas dos bicliques escolhidos seja máxima. No caso em que k=1, temos o problema de Biclique máximo. Esses dois problemas possuem aplicações na área de Bioinformática. Mantemos neste trabalho um enfoque prático, no sentido de que nosso interesse é resolver instâncias desses dois problemas com tamanho razoavelmente grande. Para isso, utilizamos técnicas de Programação Linear Inteira. Para avaliar os métodos propostos aqui, mostramos resultados de experimentos computacionais feitos com instâncias vindas de aplicações e também com instâncias geradas aleatoriamente. / In this thesis, we study the Biclique Packing problem. A biclique is a complete bipartite graph. In the Biclique Packing problem we are given an integer k and a bipartite graph G and we want to find a set of k vertex disjoint bicliques of G, such that the total number of biclique\'s edges is maximum. When k=1, we have the Maximum Biclique problem. These two problems have applications in Bioinformatics. In this work we keep a practical focus, in the sense that we are interested in solving large size instances of these problems. To tackle these problems, we use Integer Linear Programming techniques. In order to evaluate the methods proposed here, we show results of computational experiments carried out with practical application\'s instances and also with randomly generated ones.

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T16:57:43Z (GMT). No. of bitstreams: 1 Tozoni_DaviColli_M.pdf: 4212278 bytes, checksum: afb91e202a72e28729ff14334901884f (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação, apresentamos nossa pesquisa sobre o Problema da Galeria de Arte (AGP), um dos problemas mais estudados em Geometria Computacional. O AGP, que é um problema NP-difícil, consiste em encontrar o número mínimo de guardas suficiente para garantir a cobertura visual de uma galeria de arte representada por um polígono. Na versão do problema tratada neste trabalho, usualmente chamada de Problema da Galeria de Arte com Guardas-Ponto, os guardas podem ser posicionados em qualquer lugar do polígono e o objetivo é cobrir toda a região, que pode ou não conter buracos. Nós estudamos como aplicar conceitos e algoritmos de Geometria Computacional, bem como Técnicas de Programação Inteira, com a finalidade de resolver o AGP de forma exata. Este trabalho culminou na criação de um novo algoritmo para o AGP, cuja ideia é gerar, de forma iterativa, limitantes superiores e inferiores para o problema através da resolução de versões discretizadas do AGP, que são reduzidas a instâncias do Problema de Cobertura de Conjuntos. O algoritmo foi implementado e testado em mais de 2800 instâncias, de diferentes tamanhos e classes. A técnica foi capaz de resolver, em minutos, mais de 90% de todas as instâncias consideradas, incluindo polígonos com milhares de vértices, e ampliou em muito o conjunto de casos para os quais são conhecidas soluções exatas. Até onde sabemos, apesar do extensivo estudo do AGP nas últimas quatro décadas, nenhum outro algoritmo demonstrou a capacidade de resolver o AGP de forma tão eficaz como a técnica aqui descrita / Abstract: In this dissertation, we present our research on the Art Gallery Problem (AGP), one of the most investigated problems in Computational Geometry. The AGP, which is a known NP-hard problem, consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented as a polygon. In the version of the problem treated in this work, usually called Art Gallery Problem with Point Guards, the guards can be placed anywhere in the polygon and the objective is to cover the whole region, which may or not have holes. We studied how to apply Computational Geometry concepts and algorithms as well as Integer Programming techniques in order to solve the AGP to optimality. This work culminated in the creation of a new algorithm for the AGP, whose idea is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. The algorithm was implemented and tested on more than 2800 instances of different sizes and classes of polygons. The technique was able to solve in minutes more than 90% of all instances considered, including polygons with thousands of vertices, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively as the one described here / 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-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