GOSSIP: Decomposition Software for the Global Optimization of Nonconvex Two-Stage Stochastic Mixed-Integer Nonlinear Programs

Stochastic programming provides a natural way of incorporating uncertainty in model parameters, and has been receiving increasing attention in the process systems engineering literature [1–6]. Despite rapid advances in decomposition techniques for solving nonconvex two-stage stochastic mixed-integer nonlinear programs (MINLPs) [1, 7, 8], there is, to the best of our knowledge, no publicly available software framework which implements these techniques. Motivated by the above, we introduce GOSSIP, a decomposition framework for the global optimization of two-stage stochastic MINLPs.

GOSSIP includes subroutines for reformulating user input, detecting special structure, automatic construction of the subproblems required by the decomposition techniques, automatic construction of relaxations, and bounds tightening [9–12]. The decomposition framework includes implementations of nonconvex generalized Benders decomposition (NGBD) [7, 8], Lagrangian relaxation [1, 13], and a modified Lagrangian relaxation algorithm. The option of solving the extensive form of the two-stage stochastic MINLP using a global optimization solver is also included. Solver links to several state-of-the-art optimization software are part of GOSSIP and are used to solve the various subproblems used by the decomposition techniques.

A library of test instances of two-stage stochastic MINLPs from the literature is composed, and the capabilities of GOSSIP are demonstrated over this diverse set of problems.

[1] R. Karuppiah and I. E. Grossmann, “Global optimization of multiscenario mixed integer nonlinear programming models arising in the synthesis of integrated water networks under uncertainty,” Computers & Chemical Engineering, vol. 32, no. 1, pp. 145–160, 2008.

[2] S. Rebennack, J. Kallrath, and P. M. Pardalos, “Optimal storage design for a multi-product plant: A non-convex MINLP formulation,” Computers & Chemical Engineering, vol. 35, no. 2, pp. 255–271, 2011.

[3] Y. Chen, T. A. Adams, and P. I. Barton, “Optimal design and operation of flexible energy polygeneration systems,” Industrial & Engineering Chemistry Research, vol. 50, no. 8, pp. 4553–4566, 2011.

[4] X. Li, E. Armagan, A. Tomasgard, and P. I. Barton, “Stochastic pooling problem for natural gas production network design and operation under uncertainty,” AIChE Journal, vol. 57, no. 8, pp. 2120–2135, 2011.

[5] X. Li, Y. Chen, and P. I. Barton, “Nonconvex generalized Benders decomposition with piecewise convex relaxations for global optimization of integrated process design and operation problems,” Industrial & Engineering Chemistry Research, vol. 51, no. 21, pp. 7287–7299, 2012.

[6] A. Sundaramoorthy, J. M. Evans, and P. I. Barton, “Capacity planning under clinical trials uncertainty in continuous pharmaceutical manufacturing, 1: mathematical framework,” Industrial & Engineering Chemistry Research, vol. 51, no. 42, pp. 13692–13702, 2012.

[7] X. Li, A. Tomasgard, and P. I. Barton, “Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs,” Journal of Optimization Theory and Applications, vol. 151, no. 3, pp. 425–454, 2011.

[8] X. Li, A. Sundaramoorthy, and P. I. Barton, “Nonconvex generalized Benders decomposition,” in Optimization in Science and Engineering, pp. 307–331, Springer, 2014.

[9] M. Tawarmalani and N. V. Sahinidis, “A polyhedral branch-and-cut approach to global optimization,” Mathematical Programming, vol. 103, no. 2, pp. 225–249, 2005.

[10] R. Misener and C. A. Floudas, “GloMIQO: Global mixed-integer quadratic optimizer,” Journal of Global Optimization, vol. 57, no. 1, pp. 3–50, 2013.

[11] R. Misener and C. A. Floudas, “A framework for globally optimizing mixed-integer signomial programs,” Journal of Optimization Theory and Applications, vol. 161, no. 3, pp. 905–932, 2014.

[12] R. Misener and C. A. Floudas, “ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations,” Journal of Global Optimization, vol. 59, no. 2-3, pp. 503–526, 2014.

[13] C. C. CarøE and R. Schultz, “Dual decomposition in stochastic integer programming,” Operations Research Letters, vol. 24, no. 1, pp. 37–45, 1999.