(496c) Rigorous Decomposition Method for Upstream Natural Gas Supply Chain Network Design and Operation Under Uncertainty

Li, X. - Presenter, Lamar University
Tomasgard, A. - Presenter, Norwegian University of Science and Technology
Barton, P. I. - Presenter, Massachusetts Institute of Technology

Upstream natural gas supply chain networks involve gas wells in different reservoirs, transmission pipelines, gas production platforms, riser platforms, simple mixing and splitting units and gas terminals (such as liquefied natural gas plants or dry gas processing and distribution terminals) that process gas to supply markets. The integrated design and operation of such networks determines the optimal network design decisions and the gas flows during operation that can achieve the best expected profitability while ensuring the minimum supply of gas to markets and satisfaction of product specific requirements. Due to the need to track gas qualities (i.e., compositions) in the network and address the large uncertainty in the design, this problem is formulated as a stochastic pooling problem, which is a stochastic nonconvex mixed-integer nonlinear program (MINLP) with recourse and it can be transformed into an equivalent (potentially large-scale) deterministic MINLP.

Due to their special structures, stochastic programs with recourse have long been solved with duality-based decomposition strategies, typically the L-shaped method [1] [2]. The L-shaped method is essentially a Benders decomposition [3] method in the context of stochastic linear programs, and it has been extended to solving stochastic convex programs [4]. However, this method cannot solve stochastic nonconvex programs rigorously because of duality gap.

This paper presents a rigorous, duality-based decomposition method for the stochastic pooling problem, which guarantees finding an ε-optimal solution with a finite number of iterations. The method follows the framework of concepts presented by Geoffrion [5] for the design of large-scale mathematical programming techniques, and takes advantages of notions in generalized Benders decomposition [6] which is developed for convex programs. By convexification of the bilinear terms, the stochastic pooling problem is relaxed into a lower bounding problem that is a potentially large-scale mixed-integer linear program (MILP). Solution of this lower bounding problem is then decomposed into a sequence of relaxed master problems, which are MILPs with much smaller sizes, and primal bounding problems, which are linear programs (LP). The solutions of the relaxed master problems yield a sequence of nondecreasing lower bounds on the optimal objective value, and they also generate a sequence of integer realizations defining the primal problems which yield a sequence of nonincreasing upper bounds on the optimal objective value. It is proved in this paper that the decomposition algorithm terminates finitely when the lower and upper bounds coincide (or are close enough), or infeasibility of the problem is indicated.

The results of the case studies involving two example systems and a real industrial system, the Sarawak Gas Production System [7], demonstrate the dramatic computational advantages of the decomposition method over both a state-of-the-art branch-and-reduce global optimization method (realized by BARON [8]) and explicit enumeration of integer realizations. With the decomposition method, a large-scale nonconvex MINLP with almost a hundred thousand variables can be solved in 1000 seconds of solver time. As for future work, the decomposition algorithm will be parallelized to accelerate the solution and it will also be extended to tackle more general stochastic nonconvex programs.


[1] R. M. Van Slyke and R. Wets. L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics, 17(4):638?663, 1969.

[2] J. R. Birge. Decomposition and partitioning methods for multistage stochastic linear programs. Operations Research, 33(5):989?1007, 1985.

[3] J. F. Benders. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4:238?252, 1962.

[4] J. R. Birge and C. H. Rosa. Parallel decomposition of large-scale stochastic nonlinear programs. Annals of Operations Research, 64(1):39?65, 1996.

[5] A. M. Geoffrion. Elements of large-scale mathematical programming: Part I: Concepts. Management Science, 16(11):652?675, 1970.

[6] A. M. Geoffrion. Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4):237?260, 1972.

[7] A. Selot, L. K. Kuok, M. Robinson, T. L. Mason and P. I. Barton. A short-term operational planning model for natural gas production systems. AIChE Journal.54:495?515, 2008.

[8] N. V. Sahinidis. BARON: A general purpose global optimization software package. Journal of Global Optimization.8:201?205, 1996.