Non-convex nested Benders decomposition. (English) Zbl 1506.90207
Summary: We propose a new decomposition method to solve multistage non-convex mixed-integer (stochastic) nonlinear programming problems (MINLPs). We call this algorithm non-convex nested Benders decomposition (NC-NBD). NC-NBD is based on solving dynamically improved mixed-integer linear outer approximations of the MINLP, obtained by piecewise linear relaxations of nonlinear functions. Those MILPs are solved to global optimality using an enhancement of nested Benders decomposition, in which regularization, dynamically refined binary approximations of the state variables and Lagrangian cut techniques are combined to generate Lipschitz continuous non-convex approximations of the value functions. Those approximations are then used to decide whether the approximating MILP has to be dynamically refined and in order to compute feasible solutions for the original MINLP. We prove that NC-NBD converges to an \(\varepsilon \)-optimal solution in a finite number of steps. We provide promising computational results for some unit commitment problems of moderate size.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C11 | Mixed integer programming |
| 49M27 | Decomposition methods |
Keywords:
nested Benders decomposition; mixed integer nonlinear programming (MINLP); global optimization; non-convexities; non-convex value functionsSoftware:
ANTIGONE; GitHub; Julia; SCIP; Delaunay.jl; JuMP; GAMS.jl; NCNBD.jl; BARON; OR-Library; LINDO; SDDP; GurobiReferences:
| [1] | Ahmed, S., Cabral, F. G., Freitas Paulo da Costa, B.: Stochastic Lipschitz dynamic programming. Math. Programm. (2020) |
| [2] | Bacci, T., Frangioni, A., Gentile, C., Tavlaridis-Gyparakis, K.: New MINLP formulations for the unit commitment problems with ramping constraints. Preprint, http://www.optimization-online.org/DB_FILE/2019/10/7426.pdf (2019) |
| [3] | Beasley, JE, OR-library: distributing test problems by electronic mail, J. Oper. Res. Soc., 41, 11, 1069 (1990) · doi:10.1057/jors.1990.166 |
| [4] | Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131 (2013) · Zbl 1291.65172 · doi:10.1017/S0962492913000032 |
| [5] | Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex minlp, Optim. Methods Softw., 24, 597-634 (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124 |
| [6] | Benders, JF, Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 1, 238-252 (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316 |
| [7] | Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, VB, Julia: a fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98 (2017) · Zbl 1356.68030 · doi:10.1137/141000671 |
| [8] | Birge, JR, Decomposition and partitioning methods for multistage stochastic linear programs, Oper. Res., 33, 5, 989-1007 (1985) · Zbl 0581.90065 · doi:10.1287/opre.33.5.989 |
| [9] | Burlacu, R.; Geißler, B.; Schewe, L., Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes, Optim. Methods Softw., 35, 1, 37-64 (2020) · Zbl 1432.90089 · doi:10.1080/10556788.2018.1556661 |
| [10] | Cerisola, S.; Latorre, JM; Ramos, A., Stochastic dual dynamic programming applied to nonconvex hydrothermal models, Eur. J. Oper. Res., 218, 3, 687-697 (2012) · Zbl 1244.90173 · doi:10.1016/j.ejor.2011.11.040 |
| [11] | Van Dinter, J., Rebennack, S., Kallrath, J., Denholm, P., Newman, A.: The unit commitment model with concave emissions costs: a hybrid benders’ decomposition with nonconvex master problems. Ann. Oper. Res. 210(1), 361-386 (2013) · Zbl 1284.90112 |
| [12] | Dowson, O., Kapelevich, L.: SDDP.jl: a Julia package for stochastic dual dynamic programming. INFORMS J. Comput. (2020) |
| [13] | Dunning, I.; Huchette, J.; Lubin, M., JuMP: a modeling language for mathematical optimization, SIAM Rev., 59, 2, 295-320 (2017) · Zbl 1368.90002 · doi:10.1137/15M1020575 |
| [14] | Feizollahi, MJ; Ahmed, S.; Sun, A., Exact augmented Lagrangian duality for mixed integer linear programming, Math. Program., 161, 1-2, 365-387 (2017) · Zbl 1364.90226 · doi:10.1007/s10107-016-1012-8 |
| [15] | Füllner, C.: NCNBD.jl. Code released on GitHub https://github.com/ChrisFuelOR/NCNBD.jl (2021) |
| [16] | Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.-K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S. J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M. E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP optimization suite 7.0. Technical report, Optimization Online (2020) |
| [17] | GAMS Software GmbH. GAMS.jl. Code released on GitHub https://github.com/GAMS-dev/gams.jl (2020) |
| [18] | Geißler, B.: Towards globally optimal solutions for MINLPs by discretization techniques with applications in gas network optimization. PhD thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (2011) |
| [19] | Geoffrion, AM, Generalized Benders decomposition, J. Optim. Theory Appl., 10, 4, 237-260 (1972) · Zbl 0229.90024 · doi:10.1007/BF00934810 |
| [20] | LLC Gurobi Optimization. Gurobi optimization reference manual (2021) |
| [21] | Glover, F., Improved linear integer programming formulations of nonlinear integer problems, Manage. Sci., 22, 4, 455-460 (1975) · Zbl 0318.90044 · doi:10.1287/mnsc.22.4.455 |
| [22] | Hjelmeland, M.N., Zou, J., Helseth, A., Ahmed, S.: Nonconvex medium-term hydropower scheduling by stochastic dual dynamic integer programming. IEEE Trans. Sustain. Energy 10(1) (2019) |
| [23] | Infanger, G.; Morton, DP, Cut sharing for multistage stochastic linear programs with interstage dependency, Math. Program., 75, 2, 241-256 (1996) · Zbl 0874.90147 · doi:10.1007/BF02592154 |
| [24] | Kapelevich, L.: SDDiP.jl. Code released on GitHub https://github.com/lkapelevich/SDDiP.jl (2018) |
| [25] | Kallrath, J., Rebennack, S.: Computing area-tight piecewise linear overestimators, underestimators and tubes for univariate functions. In: Optimization in Science and Engineering, pp. 273-292. Springer (2014) · Zbl 1336.90064 |
| [26] | Kannan, R.: Algorithms, analysis and software for the global optimization of two-stage stochastic programs. PhD thesis, Massachusetts Institute of Technology (2018) |
| [27] | Kilinç, MR; Sahinidis, NV, Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with baron, Optim. Methods Softw., 33, 3, 540-562 (2018) · Zbl 1398.90110 · doi:10.1080/10556788.2017.1350178 |
| [28] | Li, C.; Grossmann, IE, A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables, J. Global Optim., 75, 2, 247-272 (2019) · Zbl 1428.90106 · doi:10.1007/s10898-019-00816-8 |
| [29] | Li, X.; Chen, Y.; Barton, PI, Nonconvex generalized Benders decomposition with piecewise convex relaxations for global optimization of integrated process design and operation problems, Ind. Eng. Chem. Res., 51, 21, 7287-7299 (2012) · doi:10.1021/ie201262f |
| [30] | Li, X.; Tomasgard, A.; Barton, PI, Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs, J. Optim. Theory Appl., 151, 425-454 (2011) · Zbl 1245.90079 · doi:10.1007/s10957-011-9888-1 |
| [31] | Meyer, R.R.: Integer and mixed-integer programming models: general properties. J. Optim. Theory Appl. 3(4) (1975) · Zbl 0283.90032 |
| [32] | Misener, R.; Floudas, CA, Antigone: algorithms for continuous/integer global optimization of nonlinear equations, J. Global Optim., 59, 2-3, 503-526 (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2 |
| [33] | Ogbe, E.; Li, X., A joint decomposition method for global optimization of multiscenario nonconvex mixed-integer nonlinear programs, J. Global Optim., 75, 595-629 (2018) · Zbl 1432.90092 · doi:10.1007/s10898-019-00786-x |
| [34] | Pedroso, J. P., Kubo, M., Viana, A.: Unit commitment with valve-point loading effect. Technical report, Universidade do Porto (2014) |
| [35] | Pereira, MVF; Pinto, LMVG, Multi-stage stochastic optimization applied to energy planning, Math. Program., 52, 1-3, 359-375 (1991) · Zbl 0749.90057 · doi:10.1007/BF01582895 |
| [36] | Philpott, A.B., Wahid, F., Bonnans, F.: MIDAS: a mixed integer dynamic approximation scheme. Math. Program. (2019) |
| [37] | Rebennack, S., Combining sampling-based and scenario-based nested Benders decomposition methods: application to stochastic dual dynamic programming, Math. Program., 156, 1-2, 343-389 (2016) · Zbl 1342.90116 · doi:10.1007/s10107-015-0884-3 |
| [38] | Rebennack, S., Computing tight bounds via piecewise linear functions through the example of circle cutting problems, Math. Methods Oper. Res., 84, 1, 3-57 (2016) · Zbl 1396.90051 · doi:10.1007/s00186-016-0546-0 |
| [39] | Rebennack, S.; Kallrath, J., Continuous piecewise linear delta-approximations for univariate functions: computing minimal breakpoint systems, J. Optim. Theory Appl., 167, 2, 617-643 (2015) · Zbl 1327.90245 · doi:10.1007/s10957-014-0687-3 |
| [40] | Rebennack, S., Krasko, V.: Piecewise linear function fitting via mixed-integer linear programming. INFORMS J. Comput. (2020) · Zbl 07290859 |
| [41] | Rockafellar, RT; Wets, RJB, Variational Analysis (2009), Berlin: Springer, Berlin · Zbl 0888.49001 |
| [42] | Sahinidis, N.V.: BARON 17.8.9: global optimization of mixed-integer nonlinear programs, User’s Manual (2017) |
| [43] | Schnetter, E.: Delaunay.jl. Code released on GitHub https://github.com/eschnett/Delaunay.jl (2020) |
| [44] | Schrage, L.: LindoSystems: LindoAPI (2004) |
| [45] | Steeger, G.; Lohmann, T.; Rebennack, S., Strategic bidding for a price-maker hydroelectric producer: stochastic dual dynamic programming and Lagrangian relaxation, IISE Trans., 47, 1-14 (2018) |
| [46] | Steeger, G.; Rebennack, S., Dynamic convexification within nested Benders decomposition using Lagrangian relaxation: an application to the strategic bidding problem, Eur. J. Oper. Res., 257, 2, 669-686 (2017) · Zbl 1394.90442 · doi:10.1016/j.ejor.2016.08.006 |
| [47] | Tawarmalani, M.; Sahinidis, N., Convex extensions and envelopes of lower semi-continuous functions, Math. Program., 93, 247-263 (2002) · Zbl 1065.90062 · doi:10.1007/s10107-002-0308-z |
| [48] | Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8 |
| [49] | van Slyke, RM; Wets, R., L-shaped linear programs with applications to optimal control and stochastic programming, J. SIAM Appl. Math., 17, 4, 638-663 (1969) · Zbl 0197.45602 · doi:10.1137/0117061 |
| [50] | Vielma, JP; Ahmed, S.; Nemhauser, G., Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions, Oper. Res., 58, 2, 303-315 (2010) · Zbl 1226.90046 · doi:10.1287/opre.1090.0721 |
| [51] | Vielma, JP; Nemhauser, GL, Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Math. Program., 128, 1-2, 49-72 (2011) · Zbl 1218.90137 · doi:10.1007/s10107-009-0295-4 |
| [52] | Zhang, S., Sun, X. A.: Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization. (2021). Available at https://arxiv.org/abs/1912.13278. Accessed 29 Nov 2021 |
| [53] | Zhou, K.; Kilinç, MR; Chen, X.; Sahinidis, NV, An efficient strategy for the activation of mip relaxations in a multicore global minlp solver, J. Global Optim., 70, 3, 497-516 (2018) · Zbl 1393.90076 · doi:10.1007/s10898-017-0559-0 |
| [54] | Zou, J., Ahmed, S., Sun, X.: Multistage stochastic unit commitment using stochastic dual dynamic integer programming. IEEE Trans. Power Syst. 34(3) (2019) |
| [55] | Zou, J.; Ahmed, S.; Sun, XA, Stochastic dual dynamic integer programming, Math. Program., 175, 1-2, 461-502 (2019) · Zbl 1412.90101 · doi:10.1007/s10107-018-1249-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
