×

Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. (English) Zbl 1400.90236

Summary: We present algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide an open-source software implementation that we call DSP. Our innovations include the incorporation of Benders-like cuts in a dual decomposition framework to tighten Lagrangian subproblems and aid the exclusion of infeasible first-stage solutions for problems without (relative) complete recourse. We also use an interior-point cutting-plane method with new termination criteria for solving the Lagrangian master problem. We prove that the algorithm converges to an optimal solution of the Lagrangian dual problem in a finite number of iterations, and we also prove that convergence can be achieved even if the master problem is solved suboptimally. DSP can solve instances specified in C code, SMPS files, and Julia script. DSP also implements a standard Benders decomposition method and a dual decomposition method based on subgradient dual updates that we use to perform benchmarks. We present extensive numerical results using SIPLIB instances and a large unit commitment problem to demonstrate that the proposed innovations provide significant improvements in the number of iterations and solution times. The software reviewed as part of this submission has been given the Digital Object Identifier (DOI) https://doi.org/10.5281/zenodo.998971.

MSC:

90C15 Stochastic programming
90C11 Mixed integer programming
49M27 Decomposition methods
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1
[2] Ahmed, S, A scenario decomposition algorithm for 0-1 stochastic programs, Oper. Res. Lett., 41, 565-569, (2013) · Zbl 1287.90041 · doi:10.1016/j.orl.2013.07.009
[3] Ahmed, S; Tawarmalani, M; Sahinidis, NV, A finite branch-and-bound algorithm for two-stage stochastic integer programs, Math. Program., 100, 355-377, (2004) · Zbl 1068.90084 · doi:10.1007/s10107-003-0475-6
[4] Bezanson, J., Karpinski, S., Shah, V.B., Edelman, A.: Julia: a fast dynamic language for technical computing. arXiv preprint arXiv:1209.5145 (2012) · Zbl 1356.68030
[5] Birge, J.R., Dempster, M.A., Gassmann, H.I., Gunn, E.A., King, A.J., Wallace, S.W.: A standard input format for multiperiod stochastic linear programs. IIASA Laxenburg Austria (1987)
[6] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, Berlin (2011) · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4
[7] Bixby, RE, Solving real-world linear programs: a decade and more of progress, Oper. Res., 50, 3-15, (2002) · Zbl 1163.90643 · doi:10.1287/opre.50.1.3.17780
[8] Carøe, CC; Schultz, R, Dual decomposition in stochastic integer programming, Oper. Res. Lett., 24, 37-45, (1999) · Zbl 1063.90037 · doi:10.1016/S0167-6377(98)00050-9
[9] Crainic, TG; Fu, X; Gendreau, M; Rei, W; Wallace, SW, Progressive hedging-based metaheuristics for stochastic network design, Networks, 58, 114-124, (2011) · Zbl 1233.90084
[10] Dawande, M; Hooker, JN, Inference-based sensitivity analysis for mixed integer/linear programming, Oper. Res., 48, 623-634, (2000) · Zbl 1106.90377 · doi:10.1287/opre.48.4.623.12420
[11] Fisher, ML, An applications oriented guide to Lagrangian relaxation, Interfaces, 15, 10-21, (1985) · doi:10.1287/inte.15.2.10
[12] Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Manag. Sci. 50(12-supplement), 1861-1871 (2004)
[13] Forrest, J.: Cbc. https://projects.coin-or.org/Cbc
[14] Forrest, J.: Clp. https://projects.coin-or.org/Clp
[15] Frangioni, A, About Lagrangian methods in integer optimization, Ann. Oper. Res., 139, 163-193, (2005) · Zbl 1091.90048 · doi:10.1007/s10479-005-3447-9
[16] Gade, D; Küçükyavuz, S; Sen, S, Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs, Math. Program., 144, 39-64, (2014) · Zbl 1291.90143 · doi:10.1007/s10107-012-0615-y
[17] Gamrath, G., Lübbecke, M.E.: Experiments with a generic Dantzig-Wolfe decomposition for integer programs. In: International Symposium on Experimental Algorithms, pp. 239-252. Springer (2010)
[18] Gassmann, HI; Schweitzer, E, A comprehensive input format for stochastic linear programs, Ann. Oper. Res., 104, 89-125, (2001) · Zbl 1081.90503 · doi:10.1023/A:1013138919445
[19] Geoffrion, A.M.: Lagrangean Relaxation for Integer Programming. Springer, Berlin (1974) · Zbl 0395.90056 · doi:10.1007/BFb0120690
[20] Gertz, EM; Wright, SJ, Object-oriented software for quadratic programming, ACM Trans. Math. Softw. (TOMS), 29, 58-81, (2003) · Zbl 1068.90586 · doi:10.1145/641876.641880
[21] Goffin, JL; Vial, JP, Cutting planes and column generation techniques with the projective algorithm, J. Optim. Theory Appl., 65, 409-429, (1990) · Zbl 0676.90041 · doi:10.1007/BF00939559
[22] Gondzio, J, Warm start of the primal-dual method applied in the cutting-plane scheme, Math. Program., 83, 125-143, (1998) · Zbl 0920.90102
[23] Gondzio, J; Gonzalez-Brevis, P; Munari, P, New developments in the primal-dual column generation technique, Eur. J. Oper. Res., 224, 41-51, (2013) · Zbl 1292.90318 · doi:10.1016/j.ejor.2012.07.024
[24] Gondzio, J; Grothey, A, A new unblocking technique to warmstart interior point methods based on sensitivity analysis, SIAM J. Optim., 19, 1184-1210, (2008) · Zbl 1177.90411 · doi:10.1137/060678129
[25] Gondzio, J., Sarkissian, R.: Column generation with a primal-dual method. Relatorio tecnico, University of Geneva 102 (1996)
[26] Guo, G; Hackebeil, G; Ryan, SM; Watson, JP; Woodruff, DL, Integration of progressive hedging and dual decomposition in stochastic integer programs, Oper. Res. Lett., 43, 311-316, (2015) · Zbl 1408.90209 · doi:10.1016/j.orl.2015.03.008
[27] Gurobi Optimization, Inc.: Gurobi optimizer reference manual (2015). http://www.gurobi.com
[28] Helmberg, C.: ConicBundle. https://www-user.tu-chemnitz.de/ helmberg/ (2004)
[29] IBM Corp.: IBM ILOG CPLEX Optimization Studio 12.6.1 (2014). http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html
[30] Kim, K; Mehrotra, S, A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management, Oper. Res., 63, 1431-1451, (2015) · Zbl 1334.90092 · doi:10.1287/opre.2015.1421
[31] King, A.: Stochastic Modeling Interface (2007). https://projects.coin-or.org/Smi
[32] Kleywegt, AJ; Shapiro, A; Homem-de Mello, T, The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12, 479-502, (2002) · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[33] Laporte, G; Louveaux, FV, The integer L-shaped method for stochastic integer programs with complete recourse, Oper. Res. Lett., 13, 133-142, (1993) · Zbl 0793.90043 · doi:10.1016/0167-6377(93)90002-X
[34] Lee, C; Liu, C; Mehrotra, S; Shahidehpour, M, Modeling transmission line constraints in two-stage robust unit commitment problem, IEEE Trans. Power Syst., 29, 1221-1231, (2014) · doi:10.1109/TPWRS.2013.2291498
[35] Linderoth, J; Wright, S, Decomposition algorithms for stochastic programming on a computational grid, Comput. Optim. Appl., 24, 207-250, (2003) · Zbl 1094.90026 · doi:10.1023/A:1021858008222
[36] Løkketangen, A; Woodruff, DL, Progressive hedging and tabu search applied to mixed integer (0, 1) multistage stochastic programming, J. Heuristics, 2, 111-128, (1996) · Zbl 0869.90056 · doi:10.1007/BF00247208
[37] Lubin, M., Dunning, I.: Computing in operations research using Julia. arXiv preprint arXiv:1312.1431 (2013) · Zbl 1331.90001
[38] Lubin, M; Martin, K; Petra, CG; Sandıkçı, B, On parallelizing dual decomposition in stochastic integer programming, Oper. Res. Lett., 41, 252-258, (2013) · Zbl 1286.90102 · doi:10.1016/j.orl.2013.02.003
[39] Lubin, M., Petra, C.G., Anitescu, M., Zavala, V.: Scalable stochastic optimization of complex energy systems. In: 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 1-10. IEEE (2011)
[40] Lulli, G; Sen, S, A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems, Manag. Sci., 50, 786-796, (2004) · Zbl 1232.90314 · doi:10.1287/mnsc.1030.0164
[41] Märkert, A., Gollmer, R.: Users Guide to ddsip-a C package for the dual decomposition of two-stage stochastic programs with mixed-integer recourse (2014)
[42] Mehrotra, S, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047 · doi:10.1137/0802028
[43] Mitchell, JE, Computational experience with an interior point cutting plane algorithm, SIAM J. Optim., 10, 1212-1227, (2000) · Zbl 0999.90050 · doi:10.1137/S1052623497324242
[44] OptiRisk Systems: FortSP: a stochastic programming solver, version 1.2 (2014). http://www.optirisk-systems.com/manuals/FortspManual.pdf
[45] Papavasiliou, A; Oren, SS, Multiarea stochastic unit commitment for high wind penetration in a transmission constrained network, Oper. Res., 61, 578-592, (2013) · Zbl 1273.90035 · doi:10.1287/opre.2013.1174
[46] Papavasiliou, A; Oren, SS; O’Neill, RP, Reserve requirements for wind power integration: a scenario-based stochastic programming framework, IEEE Trans. Power Syst., 26, 2197-2206, (2011) · doi:10.1109/TPWRS.2011.2121095
[47] Ralphs, T.K., Galati, M.V.: Decomposition in integer linear programming. Integer Program. Theory Pract. 3, 57-110 (2005) · Zbl 1129.90035
[48] Ralphs, T.K., Hassanzadeh, A.: A generalization of Benders algorithm for two-stage stochastic optimization problems with mixed integer recourse. Technical Report 14T-005, Department of Industrial and Systems Engineering, Lehigh University (2014)
[49] Saltzman, M., Ladányi, L., Ralphs, T.: The COIN-OR open solver interface: technology overview. In: CORS/INFORMS Conference. Banff (2004)
[50] Santoso, T; Ahmed, S; Goetschalckx, M; Shapiro, A, A stochastic programming approach for supply chain network design under uncertainty, Eur. J. Oper. Res., 167, 96-115, (2005) · Zbl 1075.90010 · doi:10.1016/j.ejor.2004.01.046
[51] Sen, S; Higle, JL, The C\(^3\) theorem and a D\(^2\) algorithm for large scale stochastic mixed-integer programming: set convexification, Math. Program., 104, 1-20, (2005) · Zbl 1159.90464 · doi:10.1007/s10107-004-0566-z
[52] Sherali, HD; Fraticelli, BM, A modification of benders’ decomposition algorithm for discrete subproblems: an approach for stochastic programs with integer recourse, J. Global Optim., 22, 319-342, (2002) · Zbl 1045.90040 · doi:10.1023/A:1013827731218
[53] Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: ParaSCIP: a parallel extension of SCIP. In: Competence in High Performance Computing 2010, pp. 135-148. Springer (2011)
[54] Shinano, Y., Heinz, S., Vigerske, S., Winkler, M.: Fiberscip-a shared memory parallelization of scip, pp. 13-55. Zuse Institute Berlin, Technical Report ZR (2013)
[55] Tarhan, B., Grossmann, I.E.: Improving dual bound for stochastic MILP models using sensitivity analysis. Working paper (2015)
[56] Watson, JP; Woodruff, DL, Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems, CMS, 8, 355-370, (2011) · Zbl 1225.91032 · doi:10.1007/s10287-010-0125-4
[57] Watson, JP; Woodruff, DL; Hart, WE, Pysp: modeling and solving stochastic programs in python, Math. Program. Comput., 4, 109-149, (2012) · Zbl 1275.90049 · doi:10.1007/s12532-012-0036-1
[58] Wunderling, R.: Paralleler und objektorientierter Simplex-Algorithmus. Ph.D. Thesis, Technische Universität Berlin (1996). http://www.zib.de/Publications/abstracts/TR-96-09/ · Zbl 0871.65048
[59] Zhang, M; Kucukyavuz, S, Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs, SIAM J. Optim., 24, 1933-1951, (2014) · Zbl 1311.90081 · doi:10.1137/13092678X
[60] Zverovich, V; Fábián, CI; Ellison, EF; Mitra, G, A computational study of a solver system for processing two-stage stochastic LPs with enhanced benders’ decomposition, Math. Program. Comput., 4, 211-238, (2012) · Zbl 1275.90050 · doi:10.1007/s12532-012-0038-z
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.