×

Scalable branching on dual decomposition of stochastic mixed-integer programming problems. (English) Zbl 1490.90204

Summary: We present a scalable branching method for the dual decomposition of stochastic mixed-integer programming. Our new branching method is based on the branching method proposed by Carøe and Schultz that creates branching disjunctions on first-stage variables only. We propose improvements to the process for creating branching disjunctions, including (1) branching on the optimal solutions of the Dantzig-Wolfe reformulation of the restricted master problem and (2) using a more comprehensive (yet simple) measure for the dispersions associated with subproblem solution infeasibility. We prove that the proposed branching process leads to an algorithm that terminates finitely, and we provide conditions under which globally optimal solutions can be identified after termination. We have implemented our new branching method, as well as the Carøe-Schultz method and a branch-and-price method, in the open-source software package DSP. Using SIPLIB test instances, we present extensive numerical results to demonstrate that the proposed branching method significantly reduces the number of node subproblems and solution times.

MSC:

90C15 Stochastic programming
90C11 Mixed integer programming
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

DIP; ALPS; DSP; GCG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, S., A scenario decomposition algorithm for 0-1 stochastic programs, Oper. Res. Lett., 41, 6, 565-569 (2013) · Zbl 1287.90041 · doi:10.1016/j.orl.2013.07.009
[2] Ahmed, S.; Tawarmalani, M.; Sahinidis, N., A finite branch-and-bound algorithm for two-stage stochastic integer programs, Math. Program., 100, 2, 355-377 (2004) · Zbl 1068.90084 · doi:10.1007/s10107-003-0475-6
[3] Amor, HB; Desrosiers, J.; Frangioni, A., On the choice of explicit stabilizing terms in column generation, Discret. Appl. Math., 157, 6, 1167-1184 (2009) · Zbl 1169.90395 · doi:10.1016/j.dam.2008.06.021
[4] Atakan, S., Sen, S.: A progressive hedging based branch-and-bound algorithm for mixed-integer stochastic programs. Comput. Manag. Sci. pp. 1-40 (2018) · Zbl 1483.90091
[5] Berthold, T.: Primal heuristics for mixed integer programs. Ph.D. thesis, Technischen Universität Berlin (2006)
[6] Birge, JR; Louveaux, F., Introduction to Stochastic Programming (2011), Berlin: Springer, Berlin · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4
[7] Boland, N.; Christiansen, J.; Dandurand, B.; Eberhard, A.; Linderoth, J.; Luedtke, J.; Oliveira, F., Progressive hedging with a Frank-Wolfe based method for computing stochastic mixed-integer programming Lagrangian dual bounds, SIAM J. Optim., 28, 2, 1312-1336 (2018) · Zbl 1398.90097 · doi:10.1137/16M1076290
[8] Boland, N.; Christiansen, J.; Dandurand, B.; Eberhard, A.; Oliveira, F., A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems, Math. Programm. (2018) · Zbl 1431.90116 · doi:10.1007/s10107-018-1253-9
[9] Carøe, CC; Schultz, R., Dual decomposition in stochastic integer programming, Oper. Res. Lett., 24, 1, 37-45 (1999) · Zbl 1063.90037 · doi:10.1016/S0167-6377(98)00050-9
[10] de Oliveira, W., Sagastizábal, C.: Bundle methods in the XXIst century: a bird’s-eye view. Pesquisa Operacional 34, 647-670 (2014)
[11] Elhedhli, S.; Naoum-Sawaya, J., Improved branching disjunctions for branch-and-bound: an analytic center approach, Eur. J. Oper. Res., 247, 1, 37-45 (2015) · Zbl 1346.90611 · doi:10.1016/j.ejor.2015.05.066
[12] Feltenmark, S.; Kiwiel, K., Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems, SIAM J. Optim., 10, 3, 697-721 (2000) · Zbl 0958.65070 · doi:10.1137/S1052623498332336
[13] Gamrath, G., Lübbecke, M.E.: Experiments with a generic Dantzig-Wolfe decomposition for integer programs. In: International Symposium on Experimental Algorithms. Springer, pp. 239-252 (2010)
[14] Kim, K., Anitescu, M., Zavala, V.M.: An asynchronous decomposition algorithm for security constrained unit commitment under contingency events. In: 2018 Power Systems Computation Conference (PSCC). IEEE, pp. 1-8 (2018)
[15] Kim, K., Botterud, A., Qiu, F.: Temporal decomposition for improved unit commitment in power system production cost modeling. IEEE Trans. Power Syst. (2018)
[16] Kim, K.; Mehrotra, S., A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management, Oper. Res., 63, 6, 1431-1451 (2015) · Zbl 1334.90092 · doi:10.1287/opre.2015.1421
[17] Kim, K.; Petra, CG; Zavala, VM, An asynchronous bundle-trust-region method for dual decomposition of stochastic mixed-integer programming, SIAM J. Optim., 29, 1, 318-342 (2019) · Zbl 1410.90138 · doi:10.1137/17M1148189
[18] Kim, K., Zavala, V.M.: Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. Math. Programm. Comput. pp. 1-42 (2017)
[19] Kirst, P.; Stein, O.; Steuermann, P., Deterministic upper bounds for spatial branch-and-bound methods in global minimization with nonconvex constraints, TOP, 23, 2, 591-616 (2015) · Zbl 1342.90146 · doi:10.1007/s11750-015-0387-7
[20] Kiwiel, KC, Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program., 46, 1-3, 105-122 (1990) · Zbl 0697.90060 · doi:10.1007/BF01585731
[21] Kiwiel, KC, Approximations in proximal bundle methods and decomposition of convex programs, J. Optim. Theory Appl., 84, 3, 529-548 (1995) · Zbl 0824.90110 · doi:10.1007/BF02191984
[22] Kiwiel, KC; Lemaréchal, C., An inexact bundle variant suited to column generation, Math. Program., 118, 1, 177-206 (2009) · Zbl 1163.65039 · doi:10.1007/s10107-007-0187-4
[23] Li, C.; Grossmann, I., An improved L-shaped method for two-stage convex 0-1 mixed integer nonlinear stochastic programs, Comput. Chem. Eng., 112, 165-179 (2018) · doi:10.1016/j.compchemeng.2018.01.017
[24] Li, C.; Grossmann, I., A finite \(\epsilon \)-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables, J. Global Optim., 75, 4, 921-947 (2019) · Zbl 1432.90095 · doi:10.1007/s10898-019-00820-y
[25] Li, C.; Grossmann, I., 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
[26] Lubin, M.; Martin, K.; Petra, C.; Sandıkçı, B., On parallelizing dual decomposition in stochastic integer programming, Oper. Res. Lett., 41, 3, 252-258 (2013) · Zbl 1286.90102 · doi:10.1016/j.orl.2013.02.003
[27] Lulli, G.; Sen, S., A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems, Manag. Sci., 50, 6, 786-796 (2004) · Zbl 1232.90314 · doi:10.1287/mnsc.1030.0164
[28] Mahajan, A., Ralphs, T.K.: Experiments with branching using general disjunctions. In: Operations Research and Cyber-Infrastructure. Springer, pp. 101-118 (2009)
[29] McMullen, P., The maximum number of faces of a convex polytope, Mathematika, XVII, 179-184 (1970) · Zbl 0217.46703 · doi:10.1112/S0025579300002850
[30] McMullen, P.; Shephard, G., Convex Polytopes and the Upper Bound Conjecture (1971), Cambridge: Cambridge University Press, Cambridge · Zbl 0172.47401 · doi:10.1016/0095-8956(71)90042-6
[31] Munguía, L.M., Oxberry, G., Rajan, D.: PIPS-SBB: a parallel distributed-memory branch-and-bound algorithm for stochastic mixed-integer programs. In: Parallel and Distributed Processing Symposium Workshops, 2016 IEEE International. IEEE, pp. 730-739 (2016)
[32] Nemhauser, G.; Wolsey, L., Integer and Combinatorial Optimization (1988), New York: Wiley-Interscience, New York · Zbl 0652.90067 · doi:10.1002/9781118627372
[33] Ntaimo, L.: Decomposition algorithms for stochastic combinatorial optimization: computational experiments and extensions. Ph.D. thesis, The University of Arizona (2004)
[34] Ntaimo, L., Sen, S.: The million-variable “march” for stochastic combinatorial optimization. J. Glob. Optim. 32(3), 385-400 (2005). doi:10.1007/s10898-004-5910-6 · Zbl 1098.90045
[35] Ogbe, E.; Li, X., A new cross decomposition method for stochastic mixed-integer linear programming, Eur. J. Oper. Res., 256, 2, 487-499 (2017) · Zbl 1394.90440 · doi:10.1016/j.ejor.2016.08.005
[36] Oliveira, W.; Sagastizábal, C.; Scheimberg, S., Inexact bundle methods for two-stage stochastic programming, SIAM J. Optim., 21, 2, 517-544 (2011) · Zbl 1226.90057 · doi:10.1137/100808289
[37] Qi, Y., Sen, S.: The ancestral Benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Math. Program. 161(1), 193-235 (2017) · Zbl 1356.90098
[38] Ralphs, T.K., Galati, M.V.: Decomposition in integer linear programming. In: Integer Programming. CRC Press, pp. 73-126 (2005)
[39] Romeijnders, W.; Schultz, R.; van der Vlerk, M.; Klein Haneveld, W., A convex approximation for two-stage mixed-integer recourse models with a uniform error bound, SIAM J. Optim., 26, 1, 426-447 (2016) · Zbl 1332.90185 · doi:10.1137/140986244
[40] Ryan, K., Rajan, D., Ahmed, S.: Scenario decomposition for 0-1 stochastic programs: improvements and asynchronous implementation. In: Parallel and Distributed Processing Symposium Workshops, 2016 IEEE International. IEEE, pp. 722-729 (2016)
[41] Sherali, H.; Zhu, X., On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables, Math. Program., 108, 2, 597-616 (2006) · Zbl 1138.90436 · doi:10.1007/s10107-006-0724-6
[42] Still, C.; Westerlund, T., Solving convex MINLP optimization problems using a sequential cutting plane algorithm, Comput. Optim. Appl., 34, 1, 63-83 (2006) · Zbl 1111.90087 · doi:10.1007/s10589-005-3076-x
[43] Tavaslioglu, O.; Prokopyev, O.; Schaefer, A., Solving stochastic and bilevel mixed-integer programs via a generalized value function, Oper. Res., 67, 6, 1659-1677 (2019) · Zbl 1455.90110 · doi:10.1287/opre.2019.1842
[44] Trespalacios, F.; Grossmann, IE, Lagrangean relaxation of the hull-reformulation of linear generalized disjunctive programs and its use in disjunctive branch and bound, Eur. J. Oper. Res., 253, 2, 314-327 (2016) · Zbl 1346.90632 · doi:10.1016/j.ejor.2016.02.048
[45] Xu, Y., Ralphs, T.K., Ladányi, L., Saltzman, M.J.: Alps: a framework for implementing parallel tree search algorithms. In: The Next Wave in Computing, Optimization, and Decision Technologies. Springer, pp. 319-334 (2005)
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.