Natural gas system operation: lagrangean optimization techniques

To comply with natural gas demand growth patterns and Europe´s import dependency, the gas industry needs to organize an efficient upstream infrastructure. The best location of Gas Supply Units – GSUs and the alternative transportation mode – by phisical or virtual pipelines, are the key of a successful industry. In this work we study the optimal location of GSUs, as well as determining the most efficient allocation from gas loads to sources, selecting the best transportation mode, observing specific technical restrictions and minimizing system total costs. For the location of GSUs on system we use the P-median problem, for assigning gas demands nodes to source facilities we use the classical transportation problem. The developed model is an optimisation-based approach, based on a Lagrangean heuristic, using Lagrangean relaxation for P-median problems – Simple Lagrangean Heuristic. The solution of this heuristic can be improved by adding a local search procedure - the Lagrangean Reallocation Heuristic. These two heuristics, Simple Lagrangean and Lagrangean Reallocation, were tested on a realistic network - the primary Iberian natural gas network, organized with 65 nodes, connected by physical and virtual pipelines. Computational results are presented for both approaches, showing the location gas sources and allocation loads arrangement, system total costs and gas transportation mode.

Lagrangean Approximation for Combinatorial Inverse Problems

Various combinatorial problems are effectively modelled in terms of (0,1) matrices. Origins are coming from n-cube geometry, hypergraph theory, inverse tomography problems, or directly from different models of application problems. Basically these problems are NP-complete. The paper considers a set of such problems and introduces approximation algorithms for their solutions applying Lagragean relaxation and related set of techniques.

An heuristic approach for optimal location of gas supply units in transportation system

The best places to locate the Gas Supply Units (GSUs) on a natural gas systems and their optimal allocation to loads are the key factors to organize an efficient upstream gas infrastructure. The number of GSUs and their optimal location in a gas network is a decision problem that can be formulated as a linear programming problem. Our emphasis is on the formulation and use of a suitable location model, reflecting real-world operations and constraints of a natural gas system. This paper presents a heuristic model, based on lagrangean approach, developed for finding the optimal GSUs location on a natural gas network, minimizing expenses and maximizing throughput and security of supply.The location model is applied to the Iberian high pressure natural gas network, a system modelised with 65 demand nodes. These nodes are linked by physical and virtual pipelines – road trucks with gas in liquefied form. The location model result shows the best places to locate, with the optimal demand allocation and the most economical gas transport mode: by pipeline or by road truck.

Natural Gas location design and operation

A major determinant of the level of effective natural gas supply is the ease to feed customers, minimizing system total costs. The aim of this work is the study of the right number of Gas Supply Units – GSUs - and their optimal location in a gas network. This paper suggests a GSU location heuristic, based on Lagrangean relaxation techniques. The heuristic is tested on the Iberian natural gas network, a system modelized with 65 demand nodes, linked by physical and virtual pipelines. Lagrangean heuristic results along with the allocation of loads to gas sources are presented, using a 2015 forecast gas demand scenario.

Optimization model for medium term natural gas commitment

In this paper we study the optimal natural gas commitment for a known demand scenario. This study implies the best location of GSUs to supply all demands and the optimal allocation from sources to gas loads, through an appropriate transportation mode, in order to minimize total system costs. Our emphasis is on the formulation and use of a suitable optimization model, reflecting real-world operations and the constraints of natural gas systems. The mathematical model is based on a Lagrangean heuristic, using the Lagrangean relaxation, an efficient approach to solve the problem. Computational results are presented for Iberian and American natural gas systems, geographically organized in 65 and 88 load nodes, respectively. The location model results, supported by the computational application GasView, show the optimal location and allocation solution, system total costs and suggest a suitable gas transportation mode, presented in both numerical and graphic supports.

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests. (C) 2009 Elsevier B.V. All rights reserved.

Um modelo numerico para analise de estruturas de materiais compostos considerando efeitos viscoelasticos e falhas progressivas

Neste trabalho apresentam-se pocedimentos para análise não linear de estruturas de materiais compostos laminados reforçados por fibras. A formulação é baseada em uma descrição cinemática incremental Lagrangeana Total, que permite o tratamento de deslocamentos arbitrariamente grandes com pequenas deformações, utilizando elementos finitos tridimensionais degenerados deduzidos para a análise de cascas. As estruturas são consideradas como submetidas a cargas mecânicas e a ações de temperatura e de umidade. O material é suposto elástico linear com propriedades dependentes, ou não, dos valores da temperatura e da concentração de umidade, ou viscoelástico linear com uma relação constitutiva em integral hereditária , e com comportamento higrotermo-reologicamente simples. As lâminas são consideradas como sujeitas a falhas, as quais são detectadas através de critérios macroscópicos, baseados em tensões ou em deformações. As equações não lineares de equilíbrio são resolvidas através de procedimentos iterativos e as deformações dependentes do tempo são avaliadas pelo método das variáveis de estado. Diversos exemplos numéricos de estruturas submetidas à flexão, flambagem elástica e viscoelástica e falhas são apresentados.

Soluções cosmológicas e locais para uma eletrodinâmica modificada

The present work investigates some consequences that arise from the use of a modifed lagrangean for the eletromagnetic feld in two diferent contexts: a spatially homogeneous and isotropic universe whose dynamics is driven by a magnetic feld plus a cosmological parameter A, and the problem of a static and charged point mass (charged black hole). In the cosmological case, three diferent general solutions were derived. The first, with a null cosmological parameter A, generalizes a particular solution obtained by Novello et al [gr-qc/9806076]. The second one admits a constant A and the third one allows A to be a time-dependent parameter that sustains a constant magnetic feld. The first two solutions are non-singular and exhibit in ationary periods. The third case studied shows an in ationary dynamics except for a short period of time. As for the problem of a charged point mass, the solutions of the Einstein-Maxwell equations are obtained and compared with the standard Reissner-Nordstrom solution. Contrary to what happens in the cosmological case, the physical singularity is not removed

A branch-and-price approach to p-median location problems

This paper describes a branch-and-price algorithm for the p-median location problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand point to its nearest facility is minimized. The traditional column generation process is compared with a stabilized approach that combines the column generation and Lagrangean/surrogate relaxation. The Lagrangean/surrogate multiplier modifies; the reduced cost criterion, providing the selection of new productive columns at the search tree. Computational experiments are conducted considering especially difficult instances to the traditional column generation and also with some large-scale instances. (C) 2004 Elsevier Ltd. All rights reserved.

Spinning Hopf solitons on S-3 x R

We consider a field theory with target space being the two dimensional sphere S-2 and defined on the space-time S-3 x R. The Lagrangean is the square of the pull-back of the area form on S-2. It is invariant under the conformal group SO(4, 2) and the infinite dimensional group of area preserving diffeomorphisms of S-2. We construct an infinite number of exact soliton solutions with non-trivial Hopf topological charges. The solutions spin with a frequency which is bounded above by a quantity proportional to the inverse of the radius of S-3. The construction of the solutions is made possible by an ansatz which explores the conformal symmetry and a U(1) subgroup of the area preserving diffeomorphism group.

Abordagens complementares para problemas de p-medianas

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Métodos de geração de colunas para problemas de atribuição

Este trabalho apresenta métodos de geração de colunas para dois importantes problemas de atribuição: o Problema Generalizado de Atribuição (PGA) e o Problema de Atribuição de Antenas a Comutadores (PAAC). O PGA é um dos mais representativos problemas de Otimização Combinatória e consiste em otimizar a atribuição de n tarefas a m agentes, de forma que cada tarefa seja atribuída a exatamente um agente e a capacidade de cada agente seja respeitada. O PAAC consiste em atribuir n antenas a m comutadores em uma rede de telefonia celular, de forma a minimizar os custos de cabeamento entre antenas e comutadores e os custos de transferência de chamadas entre comutadores. A abordagem tradicional de geração de colunas é comparada com as propostas neste trabalho, que utilizam a relaxação lagrangeana/surrogate. São apresentados testes computacionais que demonstram a efetividade dos algoritmos propostos.

Integração de modelos de localização a sistemas de informações geográficas

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A column generation approach to capacitated p-median problems

The Capacitated p-median problem (CPMP) seeks to solve the optimal location of p facilities, considering distances and capacities for the service to be given by each median. In this paper we present a column generation approach to CPMP. The identified restricted master problem optimizes the covering of 1-median clusters satisfying the capacity constraints, and new columns are generated considering knapsack subproblems. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. In this work the Lagrangean/surrogate relaxation is directly identified from the master problem dual and provides new bounds and new productive columns through a modified knapsack subproblem. The overall column generation process is accelerated, even when multiple pricing is observed. Computational tests are presented using instances taken from real data from Sao Jose dos Campos' city.

Integrability and conformal symmetry in higher dimensions: A model with exact hopfion solutions

We use ideas on integrability in higher dimensions to define Lorentz invariant field theories with an infinite number of local conserved currents. The models considered have a two-dimensional target space. Requiring the existence of lagrangean and the stability of static solutions singles out a class of models which have an additional conformal symmetry. That is used to explain the existence of an ansatz leading to solutions with non-trivial Hopf charges. © SISSA/ISAS 2002.