 |
Center for Nonlinear Studies |
Natural gas is used to heat homes and to power gas-turbines in power plants which produce electricity. Sources of natural gas are often separated by great distances from the loads. As a result, there are major gas pipelines that run across states and across countries. Laws of physics that govern the steady-state flow through these pipelines dictate that the square flow is proportional to the difference in square pressure between the ends of a pipe and inversely to the length of the pipe. We consider networks with tree structures, which closely resemble the structure of major interstate pipelines in the US. Given a fixed input flow, the remaining flows on the tree are uniquely determined based on the loads. Since it is not uncommon for pipeline lengths to exceed 1,000 miles, to prevent pressure from dropping too much it is necessary to install compressor stations along the pipe which locally boost the pressure, making it feasible to transport the gas over such long distances. However, there is an operational cost associated with running the compressors that depends on their compression ratios: the ratio of outlet to inlet pressure at the compressor. Different configurations of compressor ratios might lead to feasible pressures that support the flows, but some are more expensive than others. The goal is to find an optimal configuration that minimizes the total cost of running the compressors while maintaining feasible pressures. We propose two ways to solve this optimization problem efficiently. The first method is based on reformulation of the problem as a geometric program, and the second is based on a well-known dynamic programming approach. We apply both these methods to the Belgium gas network and to the US Transco pipeline, which runs from the Gulf of Mexico up to Pennsylvania, and discuss the results.
Host: Misha Chertkov