Prof. L. Ridgway Scott (U. of Houston)
Associate Director

Dr. Roger Z. Ríos (Texas A&M U.)
Research Associate

Suming Wu (U. of Houston)
Graduate Research Assistant

Seongbae Kim (Texas A&M U.)
Graduate Research Assistant

Working with representatives of the natural gas and high-performance computing industries, the project focus is on models and solution methods for pipeline optimization problems. The research is applicable to the efficient operation of existing networks, the evaluation of tradeoffs between safety and throughput, and the design safe and energy-efficient new networks. The work is cross-disciplinary, bringing together researchers in the natural gas industry, discrete optimization, classical applied mathematics, and high-performance computing.

Work during the first 18 months of the grant largely focused on obtaining necessary computational facilities, completing initial research, and working with industry to ensure that our models accurately reflect the problems faced in the field. During the first part of the research, we spent much of our time working with our industrial partners, learning first-hand about specific problems faced by the natural gas industry and about the mathematical models that are used. We then identified some real mathematical problems that have proven difficult to solve with present technology.

In particular, the problem we have mainly addressed is how to efficiently operate the compressor stations driving the gas in a pipeline network so as to minimize its fuel cost consumption while satisfying levels of production and demand under steady-state assumptions. By how, we specifically mean finding gas flow rates through the pipes and pressure drops at network interconnection points, that would achieve a minimum level of fuel consumption. To this end, we first studied the structure of compressor stations as separate entities. For this study, we considered the case of compressor stations consisting of several centrifugal compressor units hooked up in parallel. This compressor topology seems to be fairly common in practical settings. We established the mathematical structure for the compressors, namely the constraints that define the set of feasible operating values and the equation that represents the fuel consumption. We found out how it is possible to establish a one-to-one mapping that links the space formed by the compressor operating variables (compressor head, compressor speed, volumetric flow rate) with the space formed by the network decision variables (mass flow rate, pressure drops). Given the complexity of the fuel cost function, we proposed and derived related approximation cost functions which behave very similarly and are more tractable, that is, not as expensive to evaluate as the original function.

In the next stage of the work, we considered the general problem consisting of an entire pipeline network with many compressor stations. For this problem we developed methodologies (lower bounding schemes), based on several model relaxations and simplifications by exploiting its underlying mathematical structure. These lower bounding schemes are very important since they allowed us to evaluate the performance of pipeline optimization algorithms. One of the relaxations consisted of replacing the set of feasible operating values in the compressors (which is a non-convex set) by a convex linear outer approximation set. It is a well-known fact in nonlinear optimization that working on convex sets is computationally preferable than working on non-convex sets. A second relaxation focused on developing a convex piece-wise linear under-estimator function (convex envelope) of the fuel cost function. Although deriving convex envelopes is, in general, as difficult as solving the original problem, we fully exploited the fact that the individual components of the fuel cost function are functions defined in the three-dimensional space regardless of the size of the entire instance, thus the computational effort of producing such convex envelopes becomes relatively small. We found these two developed schemes to do a very good job within the compressor feasible domain. A third model relaxation applies the Lagrangian relaxation approach to a set of pipeline constraints, which are the constraints imposing the highest degree of restriction and difficulty. The development of these methodologies represents a major contribution to the field since, on one hand, it provides a way to assess the quality of a given feasible solution delivered by other approximation algorithms, and, in the other hand, is something that had never been done in over 30 years of research in the pipeline industry.

We have also developed algorithms for optimally operating large gas pipeline networks. The top salient features of these algorithms are (a) the inclusion of decision variables that have traditionally been treated separately in the decision-making process, and (b) the handling of looped network topologies, which stand as the most challenging type in industry, both of which represent a significant improvement over earlier approaches. One of the algorithms uses dynamic programming as its driving engine aiming at finding global optimal solutions. This technique is suitable for this type of problem as satisfying the set of constraints becomes no issue once a given discretization of the variables is adopted. The other algorithm focuses on deriving good approximate solutions, not necessarily optimal, in a relatively short amount of time. This type of approximation algorithms are very important from the practical stand point since in many real-world scenarios implementing a quick solution is preferred. Our computational work showed the effectiveness of the proposed procedures by delivering solutions of high quality over a variety of problem instances. These problem instances were carefully constructed so as to represent realistic network topologies and using real-world data for the compressor stations provided by our industrial partners. This, of course, provides the decision maker with a very valuable tool for improving the operation of compressor stations, resulting in a significant reduction of fuel utilization with its corresponding economical impact.

Another area of work we were involved was in the marketing side of the industry. Given the deregulation process the gas industry has been suffering for the past 10+ years, decision making tools such as operations research became extremely important on successfully addressing many of the problems buyers and sellers face nowadays. In particular we address the problem of deciding how to carry over gas flow imbalances over a period of time in a such a way that the penalty imposed to the shipper from the pipeline company at the end of the time horizon is minimized. The problem was formulated as a two-level optimization problem, which is a very difficult problem to solve from the optimization stand point. We proposed and developed a heuristic based on simulated annealing that finds solution of high quality, and in fact, shown how this can be used by the shipping company to significantly reduce the penalty cost.

There are many other problems in this field where operations research techniques can play a vital tool for aiding in the decision making process. They become particularly important because of the tremendous economical impact. At the same time, the inherent complexity of the natural gas industry dictates the need for team work, that is, researchers with a deep understanding of the field and researchers with a strong background on operations research, in order to improve and provide better solutions to the problems faced nowadays in the natural gas world. We have tackled successfully some of them, but the potential to do more significant work on other important problems in the industry is tremendous and must be further pursued.