Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Automação e Sistemas, Florianópolis, 2016. / Made available in DSpace on 2017-05-23T04:10:14Z (GMT). No. of bitstreams: 1 345231.pdf: 9548916 bytes, checksum: 8d41b495c44f19df25a19bfa13d74723 (MD5) Previous issue date: 2016 / Abstract : The evolution of CMOS technology made possible integrated circuits with billions of transistors assembled into a single silicon chip, giving rise to the jargon Very-Large-Scale Integration (VLSI). The required clock frequency affects the performance of a VLSI circuit and induces timing constraints that must be properly handled by synthesis tools. During the physical synthesis of VLSI circuits, several optimization techniques are used to iteratively reduce the number of timing violations until the target clock frequency is met. The dramatic increase of interconnect delay under technology scaling represents one of the major challenges for the timing closure of modern VLSI circuits. In this scenario, effective interconnect synthesis techniques play a major role. That is why this thesis targets two timing optimization problems for effective interconnect synthesis: Incremental Timing-Driven Placement (ITDP) and Incremental Timing-Driven Layer Assignment (ITLA). For solving the ITDP problem, this thesis proposes a new Lagrangian Relaxation formulation that minimizes timing violations for both setup and hold timing constraints. This work also proposes a netbased technique that uses Lagrange multipliers as net-weights, which are dynamically updated using an accurate timing analyzer. The netbased technique makes use of a novel discrete search to relocate cells by employing the Euclidean distance to define a proper neighborhood. For solving the ITLA problem, this thesis proposes a network flow approach that handles simultaneously critical and non-critical segments, and exploits a few flow conservation conditions to extract timing information for each net segment individually, thereby enabling the use of an external timing engine. The experimental validation using benchmark suites derived from industrial circuits demonstrates the effectiveness of the proposed techniques when compared with state-of-the-art works.<br> / A evolução da tecnologia CMOS viabilizou a fabricação de circuitos integrados contendo bilhões de transistores em uma única pastilha de silício, dando origem ao jargão Very-Large-Scale Integration (VLSI). A frequência-alvo de operação de um circuito VLSI afeta o seu desempenho e induz restrições de timing que devem ser manipuladas pelas ferramentas de síntese. Durante a síntese física de circuitos VLSI, diversas técnicas de otimização são usadas para iterativamente reduzir o número de violações de timing até que a frequência-alvo de operação seja atingida. O aumento dramático do atraso das interconexões devido à evolução tecnológica representa um dos maiores desafios para o fluxo de timing closure de circuitos VLSI contemporâneos. Nesse cenário, técnicas de síntese de interconexão eficientes têm um papel fundamental. Por este motivo, esta tese aborda dois problemas de otimização de timing para uma síntese eficiente das interconexões de um circuito VLSI: Incremental Timing-Driven Placement (ITDP) e Incremental Timing-Driven Layer Assignment (ITLA). Para resolver o problema de ITDP, esta tese propõe uma nova formulação utilizando Relaxação Lagrangeana que tem por objetivo a minimização simultânea das violações de timing para restrições do tipo setup e hold. Este trabalho também propõe uma técnica que utiliza multiplicadores de Lagrange como pesos para as interconexões, os quais são atualizados dinamicamente através dos resultados de uma ferramenta de análise de timing. Tal técnica realoca as células do circuito por meio de uma nova busca discreta que adota a distância Euclidiana como vizinhança.Para resolver o problema de ITLA, esta tese propõe uma abordagem em fluxo em redes que otimiza simultaneamente segmentos críticos e não-críticos, e explora algumas condições de fluxo para extrair as informações de timing para cada segmento individualmente, permitindo assim o uso de uma ferramenta de timing externa. A validação experimental, utilizando benchmarks derivados de circuitos industriais, demonstra a eficiência das técnicas propostas quando comparadas com trabalhos estado da arte.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2014. / Made available in DSpace on 2015-03-18T21:02:06Z (GMT). No. of bitstreams: 1 332281.pdf: 4170079 bytes, checksum: c52c7417e7cc9dfabdf49d0d77f3d017 (MD5) Previous issue date: 2014 / Um grande número de problemas relacionados com o planejamento e a operação de sistemas de energia elétrica resultam em modelos de otimização de grande escala, não-lineares, inteiro-mistos e, consequentemente, não-convexos. Devido à presença de diversas restrições que acoplam o problema, a Relaxação Lagrangiana surge como uma abordagem natural como metodologia de solução, pois permite a decomposição do problema em subproblemas menores e independentes entre si. A teoria da dualidade garante que a função dual oferece limites inferiores para o problema primal de minimização. Além disso, a solução do problema dual fornece o melhor limite inferior possível e um bom ponto de partida para a etapa de recuperação primal. Como o problema dual é convexo mas não-diferenciável, algoritmos especializados de otimização precisam sem empregados. Os Métodos de Feixes estão entre os mais eficientes desses algoritmos e são tipicamente utilizados quando acurácia na solução e confiabilidade são uma preocupação. Nesta dissertação é realizada a análise comparativa de três variantes dos Métodos de Feixes para um problema de comissionamento de unidades geradoras termelétricas composto de 46 barras, 10 geradores e horizontes de planejamento de 24 a 168 horas. Resultados mostram que os Métodos de Feixes têm êxito na obtenção de uma boa solução para o problema dual.<br> / Abstract : A large number of problems related to the planning and operation of electrical power systems result in optimization models which are large-scale, nonlinear, mixed-integer, and thus nonconvex. Due to the presence of multiple coupling constraints, Lagrangian Relaxation appears as a natural approach for dealing with this kind of problems: it allows decomposing the problem into smaller and independent subproblems. Duality theory says that the resulting dual optimization problem gives lower bounds for the considered primal minimization problem. Moreover, solving the dual problem provides the best possible lower bound and a good starting point for primal recovery. Since the dual problem is convex but nonsmooth, specialized optimization algorithms need to be employed. Bundle methods are among the most efficient of these methods, and are used when accuracy in the solution and reliability are a concern. We assess the performance of three Bundle Methods variants using a Thermal Unit Commitment problem composed of 46 buses, 10 thermal generating units and planning horizons ranging from 24 to 168 hours. Results show that Bundle Methods succeed in obtaining a good solution for the dual problem.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2013. / Made available in DSpace on 2013-12-05T23:12:19Z (GMT). No. of bitstreams: 1 318856.pdf: 1230228 bytes, checksum: e1a7c96794e382372e29e54b3e261525 (MD5) Previous issue date: 2013 / A minimização da corrente de leakage é um passo essencial do projeto de circuitos digitais, uma vez que nas tecnologias CMOS recentes a potência de leakage tornou-se comparável à potência dinâmica. Gate sizing é uma técnica amplamente utilizada para minimização da potência de leakage devido à sua eficácia e ao baixo impacto que ele causa no fluxo standard cell. Em tal fluxo, o problema de sizing corresponde a selecionar, para cada porta do circuito, uma combinação de largura de porta e tensão de threshold disponível na biblioteca de células, de modo a satisfazer as restrições de projeto. A natureza discreta do problema, a qual o torna NP-difícil, e o grande número de portas nos circuitos contemporâneos têm motivado a busca por heurísticas eficientes, que sejam capazes de resolvê-lo em tempo de execução aceitável. Este trabalho apresenta três contribuições principais ao estado da arte. A primeira é uma formulação aperfeiçoada para o problema de sizing discreto baseada em Relaxação Lagrangeana (LR), a qual considera valores máximos de slew de entrada e de capacitância de saída das portas, impostas pelas bibliotecas standard cell. A segunda é uma heurística topológica gulosa para resolver a formulação LR proposta utilizando informações locais para guiar as decisões do algoritmo. A terceira contribuição reside em uma técnica híbrida de três passos para superar algumas das limitações da heurística topológica gulosa. Tal técnica híbrida inicia resolvendo a formulação LR assumindo um atraso crítico ligeiramente maior do que o atraso crítico-alvo e em seguida, aplica uma heurística rápida de recuperação de atraso para que o atraso crítico-alvo original seja satisfeito. Como terceiro passo, é usada uma heurística de recuperação de potência para reduzir ainda mais a potência de leakage explorando o espaço para otimização deixado pelos dois passos anteriores. Os experimentos práticos foram gerados utilizando-se a infraestrutura da Competição de Sizing Discreto do ISPD2012, a qual provê uma base comum para comparações justas com os trabalhos correlates mais recentes. Os resultados experimentais para a formulação LR usando a heurística topológica gulosa foram comparados com os resultados obtidos pelas três equipes melhor classificadas na Competição do ISPD 2012, os quais representavam o estado da arte no momento em que tais experimentos foram realizados. A potência de leakage obtida é, em média, 18,9%, 16,7% e 43,8% menor do que aquelas obtidas pelas três melhores equipes da Competição do ISPD2012, respectivamente, ao passo que o tempo de execução total é 38, 31 e 39 vezes menor. Com relação à técnica híbrida, a potência de leakage obtida é, em média, 8,15\\\\% menor do que aquela relatada pelo trabalho que representa o estado da arte na ocasião em que estes experimentos foram realizados, sendo o tempo total de execução uma ordem de magnitude menor. É Importante ressaltar que o trabalho estado da arte referido já havia superado as três melhores equipes da Competição do ISPD2012. <br>

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2009 / Made available in DSpace on 2012-10-24T20:54:05Z (GMT). No. of bitstreams: 1 271856.pdf: 4759615 bytes, checksum: a55c7147f3f06f74758a645d8a1c486d (MD5) / A Programação da Operação do Sistema Elétrico pode ser formulada por um problema de otimização cujo objetivo é a minimização do custo de operação e atendendo a um conjunto de restrições associadas ao sistema e às unidades de produção. Em sistemas hidrotérmicos, a fim de se assegurar o uso eficiente dos recursos disponíveis e a obtenção de soluções viáveis, torna-se necessária usar uma modelagem detalhada tanto das fontes hidrelétricas como das termelétricas. Conseqüentemente, tem-se um problema de grande porte e não convexo, cuja solução não é trivial. Particularmente, neste projeto consideram se as não linearidades das funções de produção das fontes termelétricas e hidrelétricas, bem como todas as restrições relevantes para cada tipo de fonte, tais como restrições de rampa e zonas proibidas de operação, entre outras. Adicionalmente, modelam-se as restrições dos intercâmbios de transmissão e a função de custo futuro para as hidrelétricas. Como solução desse problema tem-se um programa de geração horário para um horizonte de dois dias. Dada a dificuldade de se resolver o problema em referência, propõe-se o uso da técnica de Relaxação Lagrangeana a qual tem sido usada com êxito em problemas semelhantes. Nesse contexto, decompõe-se o problema original nos subproblemas de atendimento à demanda, hidráulico, de alocação de unidades hidrelétricas e de alocação de unidades termelétricas. Uma vez que a solução dual é infactível, este trabalho utiliza a técnica do Lagrangeano Aumentado Inexato para realizar a Recuperação Primal, utilizando o mesmo esquema de decomposição proposto. Assim é possível obter uma solução viável para o problema da programação da operação eletroenergética. Os algoritmos implementados são testados com uma configuração do sistema baseado no caso brasileiro. Nos resultados obtidos, são analisados os esforços computacionais, inviabilidade da solução dual, perfis de geração hidrelétrica e termelétrica, recuperação primal e o uso da função de custo futuro. / The short-term hydrothermal scheduling of a power system can be formulated as anoptimization problem that aims to minimize the operating cost and meet a set of constraints associated with the system and the generating units. Particularly, in hydrothermal systems, in order to ensure the efficient use of the available resources, it is necessary to use a detailed modeling for hydro and thermal plants and, as a consequence, it is obtained a huge and nonconvex problem, whose solution is not trivial. In this work, we consider the nonlinearities associated with the production functions of hydro and thermal plants, as well as all the relevant constraints associated with each type of technology, such as ramping constraint for thermal plants and forbidden operating zones for hydro plants. Additionally, the transmission capacity between subsystems and the value of the water in the future for hydro plants are modeled. The solution for this problem is calculated for a two day horizon with hourly steps . Given the difficulty to solve the problem aforementioned the Lagrangian Relaxation technique is proposed, which has been successfully applied in similar problems. By this technique, the original problem is decomposed into smaller subproblems easier to solve. Given that the dual solution is unfeasible, this work makes use of the Inexact Aumented Lagrangian to perform the primal recovery in order to ensure a feasible solution. Based on these principles, a set of algorithms were developed and implemented resulting in a computational model that was tested for the Brazilian system. By means of this application, a detailed analysis with respect to the computational burden and solution quality is presented. The results allow us to conclude that the proposed model is useful to be applied in real life problems.

Tese (doutorado) - 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-20T16:23:05Z (GMT). No. of bitstreams: 1 197468.pdf: 14614571 bytes, checksum: dfd09f23e1ae2d4456a2d37c269d62f0 (MD5) / O planejamento da operação de sistemas hidrotérmicos com predominância hidrelétrica possui características matemáticas as quais determinam que o problema correspondente seja solucionado de forma aproximada a partir de três outros problemas: planejamento da operação de médio prazo e de curto prazo, e a programação da operação energética. Os problemas referentes às etapas de médio e curto prazo possuem um ferramental bastante desenvolvido, sendo resultado do desenvolvimento técnico-metodológico obtido no setor elétrico ao longo das três últimas décadas. Todavia, desenvolvimento semelhante não ocorreu com o problema da programação, cujas principais contribuições têm sido restritas a sistemas termelétricos. Este trabalho visa fornecer uma contribuição para os aspectos ligados a formulação e solução do modelo da programação da operação, onde a modelagem do sistema hidrelétrico recebe atenção especial devido à predominância desse recurso no sistema brasileiro. Assim, neste trabalho é proposta uma modelagem detalhada da função de produção das unidades hidrelétricas que leva em consideração as não-linearidades presentes na cota de jusante, perdas hidráulicas, rendimentos do grupo turbina-gerador e, adicionalmente, a existência de múltiplos estados operativos relacionados com as zonas proibidas de operação. O problema resultante é de natureza não-linear, inteira-mista e de grande porte. Nesse sentido, este trabalho faz uso de diversas técnicas de programação matemática que decompõem o problema original em uma série de subproblemas mais simples de serem solucionados. Uma configuração hidrelétrica realista é utilizada para ilustrar o desempenho da estratégia de solução, aplicada ao problema hidrelétrico, onde as viabilidades conceitual e prática do modelo proposto podem ser comprovadas a partir da qualidade das soluções e dos tempos de processamento observados.

O trabalho apresentado nesta dissertação é referente ao estudo da evacuação de pessoas, mais especificamente, a evacuação predial faseada. O objetivo é determinar, para instâncias de até 25 andares, os instantes de liberação de cada grupo de pessoas, a fim de minimizar o tempo total de evacuação do edifício. No entanto, a determinação destes instantes deve considerar o risco ao qual os diferentes grupos estão submetidos, priorizando a evacuação do andar afetado. Além disso, os conflitos de diferentes grupos por espaço nas rotas de evacuação também devem ser evitados, já que, são nessas situações que acontecem grande parte dos acidentes. Para atingir tal objetivo, foi elaborado um modelo matemático de programação linear inteira. Devido à alta complexidade do modelo, fez-se necessária a aplicação de métodos heurísticos para a obtenção de soluções. Dessa maneira, foram desenvolvidas uma heurística de busca baseada em GRASP e uma heurística lagrangeana. Apesar da heurística lagrangeana atestar a qualidade da solução (a partir da comparação do resultado obtido com o limitante inferior), a heurística de busca mostrou-se mais adequada para o problema, pois forneceu resultados de qualidade com pouco esforço computacional. / This dissertation studies the evacuation of people, more specifically, building phased evacuation. The objective of this study is to determine, for buildings of up to 25 floors, in which instants each group of people has to be released, in order to minimize the total evacuation time. Furthermore, the determination of these instants has to consider the risk to which each group of people is submitted, thus the affected floor has to be the first group to be released. In addition, conflicts for space between groups should be avoided, since such situations increase the occurrences of accidents. To achieve this goal, an integer linear programming model was designed. Due to the high complexity of the model, it was necessary to apply heuristics to obtain solutions for some instances. Therefore, a search heuristic based on GRASP and a lagrangian heuristic were developed. Despite the fact that the lagrangian heuristic attests to the quality of the solution (when it is compared to the lower bound), the search heuristic was considered more suitable for this problem because it provided quality results with lower computational efforts.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2010 / Made available in DSpace on 2012-10-25T09:16:45Z (GMT). No. of bitstreams: 1 286903.pdf: 3179531 bytes, checksum: 147f57bbf31752db925e7f566b471e5b (MD5) / O problema da programação diária da operação de sistemas hi-drotérmicos tem como objetivo definir quais unidades devem estar operando, os respectivos níveis de geração, em cada hora do dia seguinte, com o propósito de atender à demanda ao longo do dia, às restrições operativas das usinas e dos reservatórios e às restrições elétricas do sistema ao menor custo operativo. Uma característica desafiante do problema da programação consiste em obter uma solução de boa qualidade com um custo computa-cional moderado. A obtenção de uma solução dessa natureza requer uma modelagem detalhada de todos os elementos de ge-ração e transmissão do sistema hidrotérmico. Em consequência, o problema de otimização resultante possui um elevado grau de complexidade, o qual pode ser decomposto em subproblemas menores, com características distintas e mais fáceis de serem so-lucionados. Neste trabalho, a estratégia de solução proposta para o problema da programação diária está baseada nas metodologi-as da Relaxação Lagrangeana e do Lagrageano Aumentado. Essa estratégia de solução proposta para o problema da programação diária é analisada em uma configuração hidrotérmica, extraída do sistema elétrico brasileiro. / The daily operation programming problem of hydrothermal systems aims to define which units should be in operation, the respective generation levels at each hour of the day, with the purpose of matching the demand, and meeting the operating plants constraints, the reservoir constraints and the electrical system constraints at the minimum operative cost. A challenging feature of this programming problem consists of obtaining a solution with good quality and moderate computational burden. In order to obtain a good solution, a detailed modeling of the generation and the transmission system is required. Consequently, the resulting optimization problem has a high degree of complexity, which can be decomposed into smaller subproblems, with distinctive characteristics and easier to solve. In this work, the proposed strategy of solution to the daily programming problem is based on the Lagrangian Relaxation and Augmented Lagrangian methods. This proposed strategy to the daily programming problem is analyzed in a hydrothermal setting, extracted from the Brazilian electrical system.

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-22T21:13:18Z (GMT). No. of bitstreams: 1 232413.pdf: 1398027 bytes, checksum: f7a1d4cc5f0d9ff727a8c81e2ad2dd1e (MD5) / O problema da programação diária da operação de sistemas hidrotérmicos tem como objetivo definir quais unidades devem estar operando, os respectivos níveis de gera-ção, com o propósito de atender à demanda ao menor custo operativo. Uma caracte-rística desafiante do problema da programação consiste em obter uma solução de boa qualidade com um custo computacional moderado. A obtenção de uma solução de boa qualidade requer uma modelagem detalhada da função de produção das unida-des hidrelétricas e termelétricas, bem como das respectivas restrições de operação dessas unidades. Particularmente, neste trabalho tem-se como foco a modelagem das usinas hidrelétricas, dada a importância dessas instalações para o Sistema Elétrico Brasileiro. Assim, para essas unidades, as não-linearidades associadas à cota de jusan-te, as perdas hidráulicas, o rendimentos da unidade e as zonas proibidas de geração são modeladas detalhadamente. Em conseqüência, o problema de otimização resul-tante pode ser caracterizado como não-linear e de grande porte o qual pode ser trata-do satisfatoriamente por meio da aplicação da técnica de Relaxação Lagrangena. De forma geral, essa técnica decompõe o problema em subproblemas menores, com ca-racterísticas distintas e mais fáceis de serem solucionados. Para obter um tempo com-putacional compatível com o horizonte de estudo, especial atenção deve ser dada ao subproblema de alocação das unidades hidrelétricas, o qual é natureza combinatória. Nesse sentido, este trabalho propõe duas formas distintas de decomposição do pro-blema, baseadas na Relaxação Lagrangeana, possibilitando o estabelecimento de uma análise comparativa das soluções apresentadas e dos tempos computacionais, que por sua vez possibilita definir, para problemas reais, a estratégia de decomposição mais apropriada. Os estudos foram realizados utilizando-se uma configuração reduzida extraída do Sistema Elétrico Brasileiro, constituída de cinco reservatórios, 22 unidades hidrelétricas e duas unidades termelétricas.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2011 / Made available in DSpace on 2012-10-26T07:42:30Z (GMT). No. of bitstreams: 1 295134.pdf: 3300794 bytes, checksum: 2e4906157b9f1035162468e9714c55a6 (MD5) / Este trabalho propõe um modelo para o problema de alocação de unidades hidrelétricas, cujo objetivo consiste em determinar quais unidades devem operar, e os respectivos níveis de geração de usinas hidrelétricas em cascata, a cada hora, em um horizonte de um dia. Como uma contribuição apresenta-se uma nova modelagem para a função de produção das unidades geradoras, com destaque para as perdas mecânicas e elétricas presentes nos conjuntos turbina gerador. Para levar em consideração as complexidades inerentes deste problema de maneira condizente com as necessidades do caso brasileiro, o modelo da alocação é representado matematicamente como um problema de programação não linear binário-misto. Com o objetivo de resolver este problema eficientemente este trabalho faz uso de uma estratégia de decomposição baseada nos métodos da Relaxação Lagrangeana e do Lagrangeano Aumentado. Diferentes análises em torno da modelagem e da estratégia de solução propostas neste trabalho são realizadas mediante o uso de um sistema composto por quatro usinas hidrelétricas em cascata, cuja capacidade de potência instalada é de 4.170 MW.

DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T15:12:03Z No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-15T15:32:35Z (GMT) No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Made available in DSpace on 2016-07-15T15:32:35Z (GMT). No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) Previous issue date: 2008 / In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e¢ ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out. / Neste trabalho, estudamos o problema de localização simples (SPLP - Simple Plant Location Problem). Usando a formulação matemática clássica e uma outra formulação proposta recentemente, desenvolvemos vários algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulação clássica, tais limites são obtidos utilizando o método de correção de dados e critérios de dominância entre os custos …xos e de transporte. Propomos uma projeção dessa formulação, que se mostrou computacionalmente atrativa. Usando a nova formulação propomos e mostramos a corretude de vários procedimentos iterativos que procuram encontrar uma solução para o problema, resolvendo uma seqüência de subproblemas paramétricos obtidos com a remoção de variáveis e restrições da formulação original. Em cada iteração desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxação lagrangeana a essa nova formulação para obter outros limites. Analisamos várias possibilidades de relaxação das restrições. Desenvolmento também algoritmos branch-and-bound baseados em ambas as formulações e nos limites obtidos. Avaliamos a e…ciência computacional de todos os algoritmos com instâncias de teste difíceis, disponíveis na literatura. Resultados computacionais e comparações com outros algoritmos da literatura são reportados.