(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 , and its nonlinear variant generalized
Benders decomposition  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  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.
 Sahinidis, N. V. (2004). Optimization
under uncertainty: state-of-the-art and opportunities. Computers & Chemical
 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
 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),
 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.
 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
 Benders, J. F. (1962). Partitioning procedures for solving
mixed-variables programming problems. Numerische
 Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and
 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.
 Guignard, M. and Kim, S. (1987). Lagrangean decomposition: a model
yielding stronger Lagrangean bounds. Mathematical
 Carøe, C. C. and Schultz, R. (1999). Dual decomposition in
stochastic integer programming. Operations
Research Letters, 24(1),
 Kannan, R. and Barton, P. I. An improved Lagrangian relaxation
algorithm for general nonconvex two-stage stochastic programs. In