(520b) Nonconvex Generalized Benders Decomposition for Optimal Process Design and Synthesis Under Uncertainty

Mixed-integer nonlinear programming (MINLP) provides a powerful framework for the design and synthesis of process systems in an optimal and systematic manner. Traditionally, a deterministic process model is used in the MINLP framework, although real systems are almost always uncertain. Recently, more and more attention has been paid to including uncertainties into optimization models [1], especially when the uncertainties have a significant impact on the decision made, and stochastic programming with recourse [2] is a natural way to address uncertainties in various engineering problems.

Due to their special structures, stochastic programs with recourse have long been solved with duality-based decomposition strategies, typically the Benders decomposition/L-shaped method [3] [4] and generalized Benders decomposition [5]. However, these methods cannot solve nonconvex stochastic programs rigorously because of duality gap. This paper presents a rigorous, duality-based decomposition method, called nonconvex generalized Benders decomposition (NGBD), for two-stage stochastic nonconvex MINLP, which guarantees finding an ε-optimal solution within a finite number of iterations. The method follows the framework of concepts presented by Geoffrion [6] for the design of large-scale mathematical programming techniques and the notion of generalized Benders decomposition. By convexification of the nonconvex functions, the stochastic MINLP is relaxed into a lower bounding problem that is a potentially large-scale convex MINLP. Solution of this lower bounding problem is then decomposed into a sequence of relaxed master problems, which are mixed-integer linear programs (MILP) with much smaller sizes, and primal bounding problems, which are convex programs. 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 can be proved that NGBD terminates finitely when the lower and upper bounds coincide (or are close enough), or infeasibility of the problem is indicated.

Case studies of a literature problem (pump network configuration problem [7]) and a real industrial system (the Sarawak Gas Production System [8]) show the advantages of the stochastic programming model and the dramatic computational advantages of NGBD over the state-of-the-art branch-and-reduce global optimization method (BARON [9]). A nonconvex MINLP with almost 150,000 variables can be solved to global optimality with NGBD within 80 minutes. 

 References

[1] N.V. Sahinidis. Optimization under uncertainty: state-of-the-art and opportunities. Computers and Chemical Engineering, 28:971 – 983, 2004.

[2] J. R. Birge and F. Louveaux. Introduction to Stochastic Programming. Springer, New York, 1997.

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

[4] 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.

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

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

[7] T. Westerlund, F. Pettersson and I. E. Grossmann. Optimization of pump configurations as a MINLP problem. Computers and Chemical Engineering, 18(9):845–858, 1994.

[8] 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.

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