A Software Framework for the Global Optimization of Nonconvex Two-Stage Stochastic Programs

Most real-life optimization models inherently contain uncertain model parameters. Stochastic programming provides a natural way of addressing such formulations, and has been extensively used in the process systems engineering literature [1-5].

This work presents a software framework for solving two-stage stochastic programs with recourse, whose deterministic equivalent form can be written as:

where , , , and functions , , and  are continuous. The uncertainties are modeled using a finite number, s, of scenarios indexed by h, each with a positive probability of occurrence . The binary and continuous first-stage decisions y and z, respectively, are made before the realization of the uncertainties, while the mixed-integer second-stage decisions, , are made after the realization of scenario h. Joint polyhedral constraints in y and z are assumed (purely for notational convenience) to be modeled by the scenario constraints in Problem (P).

Duality-based decomposition techniques such as Benders decomposition [6], and its nonlinear variant generalized Benders decomposition [7] can be used to solve Problem (P) in a decomposable manner under certain restrictions on the participating functions. These methods, however, rely on strong duality for convergence, which is not guaranteed for most nonconvex problems. When the first-stage variables in Problem (P) correspond purely to 0-1 decisions, nonconvex generalized Benders decomposition (NGBD) can be used [2-4, 8]. Nonconvex generalized Benders decomposition is an extension of generalized Benders decomposition that rigorously handles nonconvexities in the participating functions in Problem (P). A popular decomposition technique that can handle the general form of Problem (P) is Lagrangian relaxation [9, 10]. The lower bounding problem in the conventional Lagrangian relaxation technique involves the (partial) solution of the Lagrangian dual problem, which is usually computationally intensive. Our recent work [11] proposed a modified Lagrangian relaxation technique which combines Lagrangian relaxation with NGBD and bounds tightening techniques to solve Problem (P) when continuous first-stage decisions are to be made.

In this work, we provide a computational framework for solving Problem (P) which implements versions of all of the aforementioned decomposition techniques. We demonstrate the capabilities of our framework via several process systems engineering-related case studies.

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

[2] Li, X., Armagan, E., Tomasgard, A., and Barton, P. I. (2011). Stochastic pooling problem for natural gas production network design and operation under uncertainty. AIChE Journal, 57(8), 2120-2135.

[3] Li, X., Chen, Y. and Barton, P. I. (2012). Nonconvex generalized Benders decomposition with piecewise convex relaxations for global optimization of integrated process design and operation problems. Industrial & Engineering Chemistry Research, 51(21), 7287-7299.

[4] Li, X., Sundaramoorthy, A., and Barton, P. I. (2014). Nonconvex generalized Benders decomposition. In Optimization in Science and Engineering (pp. 307-331). Springer New York.

[5] Karuppiah, R. and Grossmann, I. E. (2008). Global optimization of multiscenario mixed integer nonlinear programming models arising in the synthesis of integrated water networks under uncertainty. Computers & Chemical Engineering, 32(1), 145-160.

[6] Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.

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

[8] Li, X., Tomasgard, A., and Barton, P. I. (2011). Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs. Journal of Optimization Theory and Applications, 151(3), 425-454.

[9] Guignard, M. and Kim, S. (1987). Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Mathematical Programming, 39(2), 215-228.

[10] Carĝe, C. C. and Schultz, R. (1999). Dual decomposition in stochastic integer programming. Operations Research Letters, 24(1), 37-45.

[11] Kannan, R. and Barton, P. I. An improved Lagrangian relaxation algorithm for general nonconvex two-stage stochastic programs. In preparation.