Abstract
This paper considers deterministic global optimization of scenario-based, two-stage stochastic mixed-integer nonlinear programs (MINLPs) in which the participating functions are nonconvex and separable in integer and continuous variables. A novel decomposition method based on generalized Benders decomposition, named nonconvex generalized Benders decomposition (NGBD), is developed to obtain ε-optimal solutions of the stochastic MINLPs of interest in finite time. The dramatic computational advantage of NGBD over state-of-the-art global optimizers is demonstrated through the computational study of several engineering problems, where a problem with almost 150,000 variables is solved by NGBD within 80 minutes of solver time.
Similar content being viewed by others
References
Grossmann, I.E.: Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Eng. 3, 227–252 (2002)
Floudas, C.A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, London (1995)
Biegler, L.T., Grossmann, I.E.: Retrospective on optimization. Comput. Chem. Eng. 28, 1169–1192 (2004)
Sahinidis, N.V.: Optimization under uncertainty: state-of-the-art and opportunities. Comput. Chem. Eng. 28, 971–983 (2004)
Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997)
Li, X., Armagan, E., Tomasgard, A., Barton, P.I.: Stochastic pooling problem for natural gas production network design and operation under uncertainty. AIChE J. (2010). doi:10.1002/aic.12419
Tarhan, B., Grossmann, I.E., Goel, V.: Stochastic programming approach for the planning of offshore oil or gas field infrastructure under decision-dependent uncertainty. Ind. Eng. Chem. Res. 48, 3078–3097 (2009)
Karuppiah, R., Grossmann, I.E.: Global optimization of multiscenario mixed integer nonlinear programming models arising in the synthesis of integrated water networks under uncertainty. Comput. Chem. Eng. 32, 145–160 (2008)
Rebennack, S., Kallrath, J., Pardalos, P.M.: Optimal storage design for a multi-product plant: a non-convex MINLP formulation. Comput. Chem. Eng. 35, 255–271 (2011)
Acevedo, J., Pistikopoulos, E.N.: Stochastic optimization based algorithms for process synthesis under uncertainty. Comput. Chem. Eng. 22, 647–671 (1998)
Ahmed, S., King, A.J., Parija, G.: A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J. Glob. Optim. 26, 3–24 (2003)
Shapiro, A., Dentcheva, D., Ruszczynski, A.: Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia (2009)
Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 238–252 (1962)
Van Slyke, R.M., Wets, R.: L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4), 638–663 (1969)
Geoffrion, A.M.: Generalized Benders decomposition. J. Optim. Theory Appl. 10(4), 237–260 (1972)
Carøe, C.C., Schultz, R.: Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24, 37–45 (1999)
Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Manag. Sci. 27, 1–18 (1981)
Fisher, M.L.: An applications oriented guide to Lagrangian relaxation. Interfaces 15(2), 10–21 (1985)
Karuppiah, R., Grossmann, I.E.: A Lagrangian based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures. J. Glob. Optim. 41, 163–186 (2008)
Khajavirad, A., Michalek, J.J.: A deterministic Lagrangian-based global optimization approach for quasiseparable nonconvex mixed-integer nonlinear programs. J. Mech. Des. 131(5), 051009 (2009)
Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563–591 (2004)
Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: Global optimization of mixed-integer nonlinear problems. AIChE J. 46(9), 1769–1797 (2000)
Kesavan, P., Allgor, R.J., Gatzke, E.P., Barton, P.I.: Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs. Math. Program., Ser. A 100, 517–535 (2004)
Duran, M., Grossmann, I.E.: An outer-approximation algorithm for a class of mixed nonlinear programs. Math. Program. 66, 327–349 (1986)
Fletcher, R., Leyffer, S.: Solving mixed integer nonlinear programs by outer approximation. Math. Program. 66, 327–349 (1994)
Geoffrion, A.M.: Elements of large-scale mathematical programming: part I: concepts. Manag. Sci. 16(11), 652–675 (1970)
Geoffrion, A.M.: Elements of large-scale mathematical programming: part II: synthesis of algorithms and bibliography. Manag. Sci. 16(11), 652–675 (1970)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10, 147–175 (1976)
Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, α-BB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137–1158 (1998)
Gatzke, E.P., Tolsma, J.E., Barton, P.I.: Construction of convex relaxations using automated code generation technique. Optim. Eng. 3, 305–326 (2002)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Sahinidis, N.V., Tawarmalani, M.: BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs. User’s Manual (2010)
ARKI Consulting and Development: http://www.gams.com/docs/conopt3.pdf (2011)
Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99–131 (2005)
IBM. IBM ILOG CPLEX: High-performance mathematical programming engine. http://www-01.ibm.com/software/integration/optimization/cplex/ (2011)
Lemaréchal, C., Sagastizábal, C.: Variable metric bundle methods: from conceptual to implementable forms. Math. Program. 76, 393–410 (1997)
Balas, E., Jeroslow, R.: Canonical cuts on the unit hypercube. SIAM J. Appl. Math. 23(1), 61–69 (1972)
Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Cambridge (1999)
Geoffrion, A.M.: Duality in nonlinear programming: a simplified applications-oriented development. SIAM Rev. 13(1), 1–37 (1971)
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 2nd edn. Wiley, New York (1993)
GAMS: General Algebraic and Modeling System. Available at http://www.gams.com/ (2011)
LindoSystems, Inc.: LINDOGlobal User’s Manual. http://www.gams.com/dd/docs/solvers/lindoglobal.pdf (2011)
Mitsos, A., Chachuat, B., Barton, P.I.: McCormick-based relaxations of algorithms. SIAM J. Optim. 20(2), 573–601 (2009)
Berman, O., Ashrafi, N.: Optimization models for reliability of modular software systems. IEEE Trans. Softw. Eng. 19(11), 1119–1123 (1993)
Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gumus, Z., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems for Local and Global Optimization. Kluwer Academic, Dordrecht (1999)
Westerlund, T., Pettersson, F., Grossmann, I.E.: Optimization of pump configurations as a MINLP problem. Comput. Chem. Eng. 18(9), 845–858 (1994)
Selot, A., Kuok, L.K., Robinson, M., Mason, T.L., Barton, P.I.: A short-term operational planning model for natural gas production systems. AIChE J. 54(2), 495–515 (2008)
Selot, A.: Short-term supply chain management in upstream natural gas systems. PhD thesis, Massachusetts Institute of Technology (2009)
Birge, J.R.: Decomposition and partitioning methods for multistage stochastic linear programs. Oper. Res. 33(5), 989–1007 (1985)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Panos M. Pardalos.
This work was supported by Statoil and the research council of Norway (project nr 176089/S60) as part of the paired Ph.D. research program in gas technologies between MIT and NTNU.
Electronic Supplementary Material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Li, X., Tomasgard, A. & Barton, P.I. Nonconvex Generalized Benders Decomposition for Stochastic Separable Mixed-Integer Nonlinear Programs. J Optim Theory Appl 151, 425–454 (2011). https://doi.org/10.1007/s10957-011-9888-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9888-1