(169b) 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.