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

Authors: 
Kannan, R., Massachusetts Institute of Technology
Barton, P. I., Massachusetts Institute of Technology
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.