In this thesis we study two discrete optimization problems: Traffic Light Synchronization and Location with Customers Orderings. A widely used approach to solve the synchronization of traffic lights on transport networks is the maximization of the time during which cars start at one end of a street and can go to the other without stopping for a red light (bandwidth maximization). The mixed integer linear model found in the literature, named MAXBAND, can be solved by optimization solvers only for small instances. In this manuscript we review in detail all the constraints of the original linear model, including those that describe all the cyclic routes in the graph, and we generalize some bounds for integer variables which so far had been presented only for problems that do not consider cycles. Furthermore, we summarized the first systematic algorithm to solve a simpler version of the problem on a single street. We also propose a solution algorithm that uses Tabu Search and Variable Neighbourhood Search and we carry out a computational study. In addition we propose a linear formulation for the shortest path problem with traffic lights constraints (SPTL). On the other hand, the simple plant location problem with order (SPLPO) is a variant of the simple plant location problem (SPLP) where the customers have preferences on the facilities which will serve them. In particular, customers define their preferences by ranking each of the potential facilities. Even though the SPLP has been widely studied in the literature, the SPLPO has been studied much less and the size of the instances that can be solved is very limited. In this manuscript, we propose a heuristic that uses a Lagrangean relaxation output as a starting point of a semi-Lagrangean relaxation algorithm to find good feasible solutions (often the optimal solution). We also carry out a computational study to illustrate the good performance of our method. Last, we introduce the partial and stochastic versions of SPLPO and apply the Lagrangean algorithm proposed for the deterministic case to then show examples and results.

DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 81 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2008. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:13:52Z No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:16:23Z (GMT) No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Made available in DSpace on 2016-06-22T17:16:23Z (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.

Orientadores: Secundino Soares Filho, Takaaki Ohishi / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T02:53:29Z (GMT). No. of bitstreams: 1 ArceEncina_AnastacioSebastian_D.pdf: 1529112 bytes, checksum: a6a22a9ce6cd536449dd06144205c2e5 (MD5) Previous issue date: 2006 / Resumo: A Programação diária de um sistema de energia elétrica busca obter um despacho de geração para o próximo dia, que seja compatível com as metas definidas pelo Planejamento energético e que sirva como referência operativa para a operação em tempo real. Assim, a modelagem do sistema deve ser detalhada levando em consideração as características dos sistemas de geração, de transmissão, requisitos do mercado, critérios de segurança e custos associados à operação. Este trabalho apresenta um modelo de despacho ótimo de unidades geradoras hidrelétricas que adota como critério de desempenho um modelo que avalia as perdas no sistema de geração, ocasionadas pela elevação do nível de canal de fuga, pela variação do rendimento do conjunto turbina-gerador e pelo atrito do fluxo d¿água nas tubulações do sistema hidráulico. Além das perdas no sistema de geração também forma parte do critério de desempenho o custo associado à partida e parada das unidades geradoras. Na formulação do problema, verifica-se a presença de variáveis inteiras, não lineares; restrições de atendimento à demanda, de meta de geração oriunda do Planejamento energético e restrições de capacidade de geração. Isto caracteriza o problema do despacho de unidades geradoras como sendo um problema de programação misto inteiro-não linear, combinatório e de grande porte quando considerado um sistema de geração como o do Sistema Elétrico Brasileiro. Como técnica de solução foi adotada uma heurística que combina Relaxação Lagrangeana e Programação Dinâmica. A metodologia foi aplicada a uma parte do sistema de geração do Sistema Elétrico Brasileiro, composta por 78 usinas hidrelétricas e o total de 398 unidades geradoras. Tomando como referência os dados de programação de um dia típico de operação, os resultados apontam ganhos significativos pela diminuição de perdas. Verifica-se também a importância de se considerar o custo das partidas e paradas no despacho das unidades geradoras / Abstract: The daily scheduling operation of the electrical energy system has by target to find the dispatch generation to the next day which must be compatible with the daily generation target defined by the energy planning models and to be an operational guide. Because of its proximity with the real time operation the modeling must represent the main characteristic of the generation and transmission systems, requirements market¿s, security criterion and operational costs. This work is concerned with the dispatch of hydro generating units. The performance criterion adopted takes into account variations in tailrace elevation, penstock head losses, turbine-generator efficiencies and start-up and shutdown costs. In the hydro generating units dispatch problem formulation there are integer, non-linear variables, constraints concerned with the generation capacity, load attainment and daily generation target, this last defined by the energy planning models. According above mentioned the dispatch of hydro generating units is a combinatorial and mixed integer non-linear programming problem whose solution can be quite complex for large hydroelectric system such as the Brazilian¿s generation system. A heuristic procedure based on Lagrangian Relaxation and Dynamic Programming is adopted as solution methodology. The approach has been tested on a hydro system composed of seventy and eight hydro plants with three hundred and ninety eight generating units of the Brazilian power generation system. The generation scheduling verified on a typical day was considered for comparison with the solution provided by the approach and the results show significant improvement in term of minimization looses and the importance of to consider the start-up and shut-down costs of hydro generating units / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / 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. / 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.

[pt] Nesta tese são propostos modelos e algoritmos aproximados para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro (AGMD). Este problema modela tipicamente aplicações em projetos de redes de computadores onde todos os vértices devem comunicar-se entre si a um custo mínimo, garantindo um certo nível de serviço. Os modelos propostos por Achuthan e Caccetta para o AGMD são reforçados através da introdução de restrições válidas. Uma relaxação lagrangeana é proposta para o modelo de multifluxo básico de Gouveia e Magnanti. Essa relaxação é utilizada para o desenvolvimento de heurísticas lagrangeanas. Adaptações são realizadas nas heurísticas construtivas propostas por Deo e Abdalla, e por Raidl e Julstrom. São propostas ainda quatro estratégias de busca local, uma heurística do tipo GRASP e outra híbrida. São obtidos limites superiores a menos de 2% do ótimo para as classes de instâncias usadas nos trabalhos de Gouveia e Magnanti, e de Santos, Lucena e Ribeiro. Além disto, obteve-se os melhores resultados conhecidos até o presente momento para 11 instâncias de grafos completos usadas por Raidl, Julstrom e Gruber. / [en] In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta are strengthened with valid inequalities. A lagrangean relaxation is proposed for the multicommodity flow model developed by Gouveia and Magnanti. Adaptations are made in the constructive heuristics proposed by Deo and Abdalla and by Raidl and Julstrom. Four local search procedures, a GRASP algorithm and a hybrid heuristic are proposed. Upper bounds within 2% of the optimal solution values are obtained for the two classes of instances used by Gouveia and Magnanti and by Santos, Lucena and Ribeiro. Moreover, stronger upper bounds are reported for 11 instances in complete graphs used by Raidl, Julstrom and Gruber

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.

Made available in DSpace on 2016-06-02T19:50:17Z (GMT). No. of bitstreams: 1 TeseLKO.pdf: 834201 bytes, checksum: 994d7b70c6b1001f9dec962fafc8b72e (MD5) Previous issue date: 2004-12-13 / Universidade Federal de Sao Carlos / The purpose of this work is to develop exact methods, based on Lagrangean and Surrogate relaxation, with good performance to solve the manufacturer s pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. Such methods involve a tree search procedure of branch and bound type and they use, in each node of the branch and bound tree, bounds derived from Lagrangean and/or Surrogate relaxations of a 0-1 linear programming formulation. Subgradient optimization algorithms are used to optimize such bounds. Problem reduction tests and Lagrangean and Surrogate heuristics are also applied in the subgradient optimization to obtain good feasible solution. Computational experiments were performed with instances from the literature and also real instances obtained from a carrier. The results show that the methods are able to solve these instances, on average, more quickly than other exact methods, including the software GAMS/CPLEX. / O objetivo deste trabalho é desenvolver métodos exatos, baseados em relaxação Lagrangiana e Surrogate, com bom desempenho para resolver o problema de carregamento de paletes do produtor. Tal problema consiste em arranjar ortogonalmente e sem sobreposição o máximo número de retângulos de dimensões ( , ) l w ou ( , ) w l sobre um retângulo maior ( , ) L W . Tais métodos exatos são procedimentos de busca em árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de relaxações Lagrangiana e/ou Surrogate de uma formulação de programação linear 0 1 − . Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes. São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e Surrogate na otimização do subgradiente para obter boas soluções factíveis. Testes computacionais foram realizados utilizando exemplos da literatura e exemplos reais, obtidos de uma transportadora. Os resultados mostram que os métodos são capazes de resolvê-los, em média, mais rapidamente do que outros métodos exatos, incluindo o software GAMS/CPLEX.

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.

Made available in DSpace on 2015-04-11T14:02:46Z (GMT). No. of bitstreams: 1 Adriana Gomes Penaranda.pdf: 2772639 bytes, checksum: e4d23c72018fc1400d20f9996f6aacc1 (MD5) Previous issue date: 2013-03-01 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Wireless Sensor Networks (WSNs) are composed of a large number of sensor nodes. These networks require density control to ensure a better functioning because the high concentration of sensor nodes generates collision data, interference, and retransmittions. In addition, sensor nodes have limited energy, processing, and communication, therefore is interesting to optimize the energy consumption of the network in order to extend its lifetime. Density control schemes have been used to prolong the network lifetime. The Density Control Problem in Wireless Sensor Networks (DCP-WSNs) minimizes the energy consumed by the sensor nodes active, choosing a subset of sensor nodes that meets the application requirements and maximize the use of network resources. This paper presents two approaches to treat DCP-WSN: Periodic and Multiperiod. The Periodic Approach always chooses the best solution for a given period, having a local view of the network lifetime and repeats this proceduce periodically. The Multiperiod Approach defines an expected life time of the network and divide it into periods. For each period the solution is chosen taking into consideration the other periods, thus with an global view of the network lifetime and periods. Both approaches are modeled with Integer Linear Programming and solved by an optimization software. For the Periodic Approach model is proposed a Lagrangean Relaxation with a Lagrangean Heuristic which relax difficults constraints in order to make the problem easier to be solved. We also present a Genetic Algorithm Hybrid (GA) which uses the Periodic Approach to generate the solution of each period and execute a refinement stage based on concepts of the Multiperiod Approach. The proposed heuristics are compared with algorithms of the literature and results show that the Lagrangean Relaxation and Heuristic reach better energy consumption and solution time. Furthermore the Lagrangean relaxation generates lower bounds for the DCP-WSN that may be used to evaluate other algorithms Density Control. / As Redes de Sensores Sem Fios (RSSFs) são redes compostas por um grande número de nós de sensores. Estas redes necessitam de controle de densidade para garantir um melhor funcionamento, pois a alta concentração de nós sensores gera colisão de dados, interferências e consequentemente retransmissão de dados. Os nós sensores possuem limitações de energia, processamento e comunicação e por isto é interessante otimizar o consumo de energia da rede com o objetivo de estender seu tempo de vida. Esquemas de controle de densidade têm sido utilizados como recursos para prolongar o tempo de vida da rede. O Problema de Controle de Densidade em Redes de Sensores Sem Fios (PCD-RSSFs) consiste em minimizar a energia consumida pelos nós sensores ativos, escolhendo um subconjunto de nós que atenda os requisitos da aplicação e maximize a utilização dos recursos da rede. Este trabalho apresenta duas abordagens para tratar o PCD-RSSFs: Periódica e Multiperíodo. A Abordagem Periódica escolhe a melhor solução para um dado período, tendo uma visão local do tempo de vida da rede e repete este procedimento periodicamente. A Abordagem Multiperíodo consiste em definir um tempo esperado de vida da rede e dividí-lo em períodos. Para cada período a solução é escolhida levando em consideração os outros períodos, caracterizando uma visão global do tempo de vida da rede e dos períodos. Ambas as abordagens foram modeladas com Programação Linear Inteira e resolvidas por um software de otimização. Para a modelagem da Abordagem Periódica é proposta uma Relaxação Lagrangeana em conjunto com uma Heurística Lagrangeana onde a ideia é relaxar restrições difíceis com o intuito de deixar o problema mais simples de ser resolvido. Também é apresentado um Algoritmo Genético (AG) híbrido que utiliza Abordagem Periódica para gerar a solução de cada período e em seguida uma fase de refinamento baseada nos conceitos da Abordagem Multiperíodo. As heurísticas implementadas são comparadas com algoritmos da literatura e os resultados mostram que a combinação Relaxação Lagrangeana e Heurística Lagrangeana obtêm melhor desempenho tanto em consumo de energia quanto em tempo de solução. Além disso a Relaxação Lagrangeana gera limites inferiores para o PCD-RSSFs que podem ser utilizados para avaliação de outros algoritmos de controle de Densidade

[pt] Esta tese investiga e desenvolve algoritmos baseados em relaxação Lagrangiana e técnica de desagregação multiparamétrica normalizada para resolver problemas não convexos de programação inteira-mista quadrática com restrições quadráticas. Primeiro, é realizada uma revisão de técnias de relaxação para este tipo de problema e subclasses do mesmo. Num segundo momento, a técnica de desagregação multiparamétrica normalizada é aprimorada para sua versão reformulada onde o tamanho dos subproblemas a serem resolvidos tem seu tamanho reduzido, em particular no número de variáveis binárias geradas. Ademais, dificuldas em aplicar a relaxação Lagrangiana a problemas não convexos são discutidos e como podem ser solucionados caso o subproblema dual seja substituído por uma relaxação não convexa do mesmo. Este método Lagrangiano modificado é comparado com resolvedores globais comerciais e resolvedores de código livre. O método proposto convergiu em 35 das 36 instâncias testadas, enquanto o Baron, um dos resolvedores que obteve os melhores resultados, conseguiu convergir apenas para 4 das 36 instâncias. Adicionalmente, mesmo para a única instância que nosso método não conseguiu resolver, ele obteve um gap relativo de menos de 1 por cento, enquanto o Baron atingiu um gap entre 10 por cento e 30 por cento para a maioria das instâncias que o mesmo não convergiu. / [en] This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming. First, relaxations for quadratic programming and related problem classes are reviewed. Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables. Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations. This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances. The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36. Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1 percent in all instances, while Baron achieved relative gaps between 10 percent and 30 percent in most of them.