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

Monday, November 14, 2016: 9:15 AM
Monterey I (Hotel Nikko San Francisco)
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

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.

Extended Abstract: File Not Uploaded