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

Monday, November 9, 2015: 12:49 PM
Salon F (Salt Lake Marriott Downtown at City Creek)
Rohit Kannan, Dept. of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, MA and Paul I. Barton, Process Systems Engineering Laboratory, Massachusetts Institute of Technology, Cambridge, MA

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.

Extended Abstract: File Not Uploaded