Mixed Integer Models for the Stationary Case of Gas Network Optimization

A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed integer linear program. We study sub-polyhedra linking these piece-wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the separation algorithms are also presented. Our computational results demonstrate the success of this approach. Received: April, 2004     

Adaptive linearized models for optimization of gas networks

We are interested in simulation and optimization of gas networks. Usually, a gas network consists of various components like compressors and valves connected by pipes. The aim is to run the network cost efficiently whereas demands of consumers have to be satisfied. This results in a complex nonlinear mixed integer problem. We address this task with methods provided by discrete optimization. Therefore, the gas dynamics in all pipes and at compressors must be described by piecewise linear constraints. We introduce an adaptive approach for the linearization process to handle the complexity on the one hand and the aimed accuracy on the other and present numerical simulation and optimization results based on our model. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Transient Modeling and Simulation of Gas Pipe Networks with Characteristic Diagram Models for Compressors

One challenge for the simulation and optimization of real gas pipe networks is the treatment of compressors. Their behavior is usually described by characteristic diagrams reflecting the connection of the volumetric flow and the enthalpy change or shaft torque. Such models are commonly used for an optimal control of compressors and compressor stations [4,7] using stationary models for the gas flow through the pipes. For transient simulations of gas networks, simplified compressor models have been studied in [1–3]. Here, we present a transient simulation of gas pipe networks with characteristic diagram models of compressors using a stable network formulation as (partial) differential-algebraic system. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An explicit staggered-grid method for numerical simulation of large-scale natural gas pipeline networks

We present an explicit second order staggered finite difference (FD) discretization scheme for forward simulation of natural gas transport in pipeline networks. By construction, this discretization approach guarantees that the conservation of mass condition is satisfied exactly. The mathematical model is formulated in terms of density, pressure, and mass flux variables, and as a result permits the use of a general equation of state to define the relation between the gas density and pressure for a given temperature. In a single pipe, the model represents the dynamics of the density by propagation of a non-linear wave according to a variable wave speed. We derive compatibility conditions for linking domain boundary values to enable efficient, explicit simulation of gas flows propagating through a network with pressure changes created by gas compressors. We compare our staggered grid method with an explicit operator splitting method and a lumped element scheme, and perform numerical experiments to validate the convergence order of the new discretization approach. In addition, we perform several computations to investigate the influence of non-ideal equation of state models and temperature effects on pipeline simulations with boundary conditions on various time and space scales.     

Long-term optimization model of tree water networks

This paper describes an optimization method to design, over a period of time, a radial water network consisting of pipes, pumps and pressure reducing valves. The network structure can be modified during the planning period by the addition or removal of certain nodes and elements. The evolution of the consumption at the nodes is known. The hydraulic constraints of pressure and flow velocity are respected throughout the studied period.The investment decisions are determined in such a manner as to minimize the sum of the present worth values of the investment costs and operation costs over the planning period.The choice of pipe lengths to be invested in each branch as variables allows one to formulate the dynamic investment problem as a multi-stage linear program. Each stage corresponds to the state of the network at a time of the planning period. Such a formulation of a combinatorial problem of investments allows one to design networks of large dimensions in the long term whilst maintaining acceptable times of computation.An application of the model to a real problem is presented.     

A Branch-and-Bound Algorithm to Solve a Multi-level Network Optimization Problem

Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, and electric power systems. A model for multi-level network design is formulated as a mixed-integer program. The approach is innovative because it integrates in the same model aspects of discrete facility location, topological network design, and dimensioning. We propose a branch-and-bound algorithm based on Lagrangian relaxation to solve the model. Computational results for randomly generated problems are presented showing the quality of our approach. We also present and discuss a real world problem of designing a two-level local access urban telecommunication network and solving it with the proposed methodology.     

Extending a Gas Pipeline Network

This paper describes the use of a mixed-integer programming model for the problem of determining methods of reinforcing and increasing a natural gas pipeline network. The model considers the options of (i) reinforcing pipes, (ii) building new pipes into the network, (iii) setting up of liquid natural gas tanks at certain points on the network, and attempts to find the best policy for satisfying demand levels. Because of the difficulties of solving the resultant mixed-integer problem, the model can only be used for small networks.     

The modeling and numerical simulation of gas flow networks

Summary. A network formulation is introduced for the modeling and numerical simulation of complex gas transmission systems like a multi-cylinder internal combustion engine. Several simulation levels are discussed which result in different network representations of a specific system. Basic elements of a network are chambers of finite volume, straight pipes and connections like valves or nozzles. The pipe flow is modeled by the unsteady, one-dimensional Euler equations of gas dynamics. Semi-empirical approaches for the chambers and the connections yield differential-algebraic equations (DAEs) in time. The numerical solution is based on a TVD scheme for the pipe equations and a predictor-corrector method for the DAE-system. Simulation results for an internal combustion engine demonstrate the practical interest of the new approach. Received May 12, 1994 / Revised version received August 26, 1994     

天然气稳态运行优化的混合整数模型及其算法

天然气稳态运行优化问题的难点在于网络结构复杂、规模大、目标函数及约束高度非线性.针对其混合整数非线性规划模型,基于网络约简和线性化技术,建立了线性近似模型,并提出一种新的求解算法.将新算法用于优化我国西部天然气管网系统,结果表明所提算法是有效的.     

Chaotic artificial immune approach applied to economic dispatch of electric energy using thermal units

The economic dispatch problem (EDP) is an optimization problem useful in power systems operation. The objective of the EDP of electric power generation, whose characteristics are complex and highly non-linear, is to schedule the committed generating unit outputs so as to meet the required load demand at minimum operating cost while satisfying system constraints. Recently, as an alternative to the conventional mathematical approaches, modern heuristic optimization techniques have been given much attention by many researchers due to their ability to find an almost global optimal solution in EDPs. As special mechanism to avoid being trapped in local minimum, the ergodicity property of chaotic sequences has been used as optimization technique in EDPs. Based on the chaos theory, this paper discusses the design and validation of an optimization procedure based on a chaotic artificial immune network approach based on Zaslavsky’s map. The optimization approach based on chaotic artificial immune network is validated for a test system consisting of 13 thermal units whose incremental fuel cost function takes into account the valve-point loading effects. Simulation results and comparisons show that the chaotic artificial immune network approach is competitive in performance with other optimization approaches presented in literature and is also an attractive tool to be used on applications in the power systems field.     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

Designing,calculation, and optimization of polymeric honeycomb pipes

The problem of optimization of the honeycomb wall structure of pipes subjected to static loads is investigated. As the basic engineering design parameter of the pipes, their ring rigidity is assumed. The corresponding optimization problem is formulated. Starting from the necessary ring rigidity of cylindrical pipes made of polymeric materials with honeycomb walls, their geometrical, physicomechanical, and technological parameters are determined. Based on the calculations, the optimum geometry (wall thickness, diameter, and the number of layers) of the pipes is found. Numerical results are presented and analyzed. Translated from Mekhanika Kompozitnykh Materialov, Vol. 44, No. 6, pp. 853–860, November–December, 2008.     

A neural approach for obstacle detection with a linear stereoscopic sensor

A neural implementation for achieving real-time obstacle detection in front of a moving vehicle using a linear stereoscopic sensor is presented. The key problem is the so-called “correspondence problem” which consists in matching features in two stereo images that are projections of the same physical entity in the three-dimensional world. In our approach, the set of edge points extracted from each linear image is first split into two classes. Within each of these classes, the matching problem is turned into an optimization task where an energy function, which represents the constraints on the solution, is to be minimized. The optimization problem is then performed thanks to an analog Hopfield neural network. The preliminary discrimination of the edge points allows us to implement the matching process as two networks running in parallel. Experimental results are presented to demonstrate the effectiveness of the approach for 3-D reconstruction in real traffic conditions.     

Mixed-integer minimax dynamic optimization for structure identification of glycerol metabolic network

Cell metabolism is a dynamic regulation process, in which its network structure and/or regulatory mechanisms can change constantly over time due to internal and external perturbations. This paper models glycerol metabolism in continuous fermentation as a nonlinear mixed-integer dynamic system by defining the time-varying metabolic network structure as an integer-valued function. To identify the dynamic network structure and kinetic parameters, we establish a mixed-integer minimax dynamic optimization problem with concentration robustness as its objective functional. By direct multiple shooting strategy and a decomposition approach consisting of convexification, relaxation and rounding strategy, the optimization problem is transformed into a large-scale approximate multistage parameter optimization problem. It is then solved using a competitive particle swarm optimization algorithm. We also show that the relaxation problem yields the best lower bound for the optimization problem, and its solution can be arbitrarily approximated by the solution obtained from rounding strategy. Numerical results indicate that the proposed mixed-integer dynamic system can better describe cellular self-regulation and response to intermediate metabolite inhibitions in continuous fermentation of glycerol. These numerical results show that the proposed numerical methods are effective in solving the large-scale mixed-integer dynamic optimization problems.     

Solving a class of geometric programming problems by an efficient dynamic model

In this paper, a neural network model is constructed on the basis of the duality theory, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle to solve geometric programming (GP) problems. The main idea is to convert the GP problem into an equivalent convex optimization problem. A neural network model is then constructed for solving the obtained convex programming problem. By employing Lyapunov function approach, it is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. The simulation results also show that the proposed neural network is feasible and efficient.     

Design of optimal utility of wireless rechargeable sensor networks via joint spatiotemporal scheduling

In wireless rechargeable sensor networks, how to optimize energy resources for maximizing the sensor data is a challenging problem. In this paper, mobile charging vehicle scheduling, sensor charging time splitting and rate control with battery capacity constraints are considered together to maximize network utility. However, they are considered independently in exist works even though these problems are interdependent. In order to improve network performance through collaborative optimization of three problems, a joint optimization problem is formulated firstly. Then, a multistage approach is developed to jointly optimize the three subproblems iteratively. Furthermore, an accelerated distributed algorithm is integrated to improve the convergence speed of rate control. The results of extended experiments demonstrate that proposed approach can obtain higher network utility and charging efficiency compared to other charging scheduling methods.     

The graph coloring problem: A neuronal network approach

Solution of an optimization problem with linear constraints through the continuous Hopfield network (CHN) is based on an energy or Lyapunov function that decreases as the system evolves until a local minimum value is attained. This approach is extended in to optimization problems with quadratic constraints. As a particular case, the graph coloring problem (GCP) is analyzed. The mapping procedure and an appropriate parameter-setting procedure are detailed. To test the theoretical results, some computational experiments solving the GCP are shown.     

Optimization methods for pipeline transportation of natural gas with variable specific gravity and compressibility

In this paper, the problem of flow maximization in pipeline systems for transmission of natural gas is addressed. We extend previously suggested models by incorporating the variation in pipeline flow capacities with gas specific gravity and compressibility. Flow capacities are modeled as functions of pressure, compressibility and specific gravity by the commonly-used Weymouth equation, and the California Natural Gas Association method is used to model compressibility as a function of specific gravity and pressure. The sources feeding the transmission network do not necessarily supply gas with equal specific gravity. In our model, it is assumed that when different flow streams enter a junction point, the specific gravity of the resulting flow is a weighted average of the specific gravities of entering flows. We also assume the temperature to be constant, and the system to be in steady state. Since the proposed model is non-convex, and global optimization hence can be time consuming, we also propose a heuristic method based on an iterative scheme in which a simpler NLP model is solved in each iteration. Computational experiments are conducted in order to assess the computability of the model by applying a global optimizer, and to evaluate the performance of the heuristic approach. When applied to a wide set of test instances, the heuristic method provides solutions with deviations less than 10% from optimality, and in many instances turns out to be exact. We also report several experiments demonstrating that letting the compressibility and the specific gravity be global constants can lead to significant errors in the estimates of the total network capacity.