This paper discusses how to generate good lower bounds for the fuel cost minimization problem arising from the steady-state gas pipeline network flows. These lower bounds may be wed to evaluate the quality of the solutions provided by the present generation of pipeline optimization algorithms. Mathematical models of steady-state gas pipeline network flows are complicated by the existence of both complex network structures and sophiscated compressor stations. Optimiiation problems based on these models are very dificult due to their nonlinearity, non-convexity, and discontinuity, see [l]. Hence the solutions provided by the present generation of pipeline optimization algorithms are frustrated. This raises a practical question: How can we evaluate the quality of proposed optimization algorithms? One way to answer this question is through the development of bounding procedures. Id this paper we shall focus on the problem of minimizing fuel cost for steady&ate gas pipeline networks. Since every feasible solution serves as an upper bound of minimization problems, we shall describe how to develop a good lower bound for such a problem. The problem will be stated in section 1, in which each compressor station is treated as a "black box-whose input is mass flow rate V, suction pressure pa, and discharge pressure pa of the station, and output is the minimum fuel cost g(v,p,,p& Operation limits of each station constitute a feasible domain D fix the input variables z),p., pd. To understand the minimization problem, we first must be able to answer the following questions:
What is the structure of the domains D's?
How do functions g's behave? The answers to these questions will be discussed in section 2.
It can be seen in section 2 that both the domain D and the function g are nonlinear and nonconvex. These make the task of finding the optimal solution to the fuel minimization problem practically impossible. To find a good lower bound to the optimal solution, we will first develop a linear super& B for each domain D in section 3. Then, in section 4, an algorithm to compute a convex lower bound s for each function g is discussed. Conclusions come in section 5.
In the real world, gas pipeline networks consist of nodes, pipes, compressor stations, and other devices, such as valves, regulators, etc. To make our mathematical model simple enough, several assumptions will be made through discussion. The first one is related to the networks being consid-WXI: Assumption 1 Network a being considered in this paper consist of only nodes, pipes, and wmpressor stations. The objective function of the problem is a sum of the fuel costs over all the compressor stations in the network. This problem involves the following (equality or inequality) constraints 1. Mass flow balance equation at each node; 2. Gas flow equation through each pipe; 3. Pressure constraints at each node;
