×

Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs. (English) Zbl 1338.90282

Summary: We present a method for computing lower bounds in the progressive hedging algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using dual prices that are calculated during execution of the standard PHA. We report computational results on stochastic unit commitment and stochastic server location problem instances, and explore the relationship between key PHA parameters and the quality of the resulting lower bounds.

MSC:

90C15 Stochastic programming
90C11 Mixed integer programming

Software:

ddsip; PySP; Pyomo
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahmed, S., Tawarmalani, M., Sahinidis, N.V.: A finite branch and bound algorithm for two-stage stochastic integer programs. Math. Program. Ser. A 100(2), 355-377 (2004) · Zbl 1068.90084 · doi:10.1007/s10107-003-0475-6
[2] Boyd, S., Parihk, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3, 1-22 (2011) · Zbl 1229.90122
[3] Carøe, C.C., 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
[4] Carrión, M., Arroyo, J.M.: A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem. IEEE Trans. Power Syst. 21(3), 1371-1378 (2006) · doi:10.1109/TPWRS.2006.876672
[5] Cheung, K., Gade, D., Monroy, C.S., Ryan, S.M., Watson, J.P., Wets, R.J.B., Woodruff, D.L.: Scalable stochastic unit commitment, part 2: solver performance. Energy Syst. 6, 309-329 (2015) · doi:10.1007/s12667-015-0148-6
[6] Cormican, K.J., Morton, D.P., Wood, R.K.: Stochastic network interdiction. Oper. Res. 46(2), 184-197 (1998) · Zbl 0987.90516 · doi:10.1287/opre.46.2.184
[7] Crainic, T., Hewitt, M., Rei, W.: Scenario grouping in a progressive hedging-based meta-heuristics for stochastic network design. Comput. Oper. Res. 43, 90-99 (2014) · Zbl 1348.90165 · doi:10.1016/j.cor.2013.08.020
[8] Dantzig, G.B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101-111 (1960) · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[9] Eichhorn, A.; Heitsch, H.; Römisch, W.; Rebennack, S. (ed.); Pardalos, PM (ed.); Pereira, MVF (ed.); Iliadis, NA (ed.), Stochastic optimization of electricity portfolios: Scenario tree modeling and risk management, 405-432 (2010), Berlin · Zbl 1359.90079 · doi:10.1007/978-3-642-12686-4_15
[10] Ela, E., Milligan, M., O’Malley, M.: A flexible power system operations simulation model for assessing wind integration. In: 2011 IEEE Power and Energy Society General Meeting. IEEE, New York (2011)
[11] Escudero, L., Garn, A., Prez, G., Unzueta, A.: Scenario cluster decomposition of the lagrangian dual in stochastic mixed 0-1 optimization. Comput. Oper. Res. 40, 362-377 (2013) · Zbl 1349.90655 · doi:10.1016/j.cor.2012.07.009
[12] Guignard, M., Kim, S.: Lagrangean decomposition: a model yielding stronger lagrangean bounds. Math. Program. 39(2), 215-228 (1987) · Zbl 0638.90074 · doi:10.1007/BF02592954
[13] Guo, G., Hackebeil, G., Ryan, S., Watson, J., Woodruff, D.: 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
[14] Hart, W., Watson, J., Woodruff, D.: Pyomo: Modeling and solving mathematical programs in Python. Math. Program. Comput. 3(3), 219-260 (2011) · Zbl 1408.90209
[15] Held, H., Hemmecke, R., Woodruff, D.L.: A decomposition algorithm applied to planning the interdiction of stochastic networks. Naval Res. Logist. (NRL) 52(4), 321-328 (2005) · Zbl 1104.90010 · doi:10.1002/nav.20079
[16] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993) · Zbl 0795.49001
[17] Janjarassuk, U., Linderoth, J.: Reformulation and sampling to solve a stochastic network interdiction problem. Networks 52(3), 120-132 (2008) · Zbl 1173.90345 · doi:10.1002/net.20237
[18] Kaut, M., Wallace, S.: Evaluation of scenario-generation methods for stochastic programming. Pac. J. Optim. 3(2), 257-271 (2007) · Zbl 1171.90490
[19] Løkketangen, A., Woodruff, D.L.: 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
[20] 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
[21] 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
[22] Märkert, A., Gollmer, R.: User’s Guide to ddsip-AC Package for the Dual Decomposition of Two-Stage Stochastic Programs with Mixed-Integer Recourse. Department of Mathematics, University of Duisburg-Essen, Duisburg (2008)
[23] Meyer, R.R.: On the existence of optimal solutions to integer and mixed-integer programming problems. Math. Program. 7(1), 223-235 (1974) · Zbl 0292.90036 · doi:10.1007/BF01585518
[24] Morales-Espana, G., Latorre, J.M., Ramos, A.: Tight and compact MILP formulation for the thermal unit commitment problem. IEEE Trans. Power Syst. 21, 4897-4908 (2013) · doi:10.1109/TPWRS.2013.2251373
[25] Mulvey, J.M., Vladimirou, H.: Applying the progressive hedging algorithm to stochastic generalized networks. Ann. Oper. Res. 31, 399-424 (1991) · Zbl 0734.90033 · doi:10.1007/BF02204860
[26] Mulvey, J.M., Vladimirou, H.: Solving multistage stochastic networks: an appplication of scenario aggregation. Networks 21, 619-643 (1991) · Zbl 0743.90053 · doi:10.1002/net.3230210603
[27] Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization, vol. 27. Wiley, New York (1988) · Zbl 0652.90067
[28] Ntaimo, L., Sen, S.: The million-variable march for stochastic combinatorial optimization. J. Glob. Optim. 32, 385-400 (2005) · Zbl 1098.90045 · doi:10.1007/s10898-004-5910-6
[29] Papavasiliou, A., Oren, S.S.: Multiarea stochastic unit commitment for high wind penetration in a transmission constrained network. Oper. Res. 61(3), 578-592 (2013) · Zbl 1273.90035 · doi:10.1287/opre.2013.1174
[30] Pflug, GC; Pichler, A.; Bertocchi, M. (ed.); Consigli, G. (ed.); Dempster, MA (ed.), Approximations for probability distributions and stochastic optimization problems (2011), Berlin
[31] Rockafellar, R.T., Wets, R.J.B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1), 119-147 (2004) · Zbl 0729.90067 · doi:10.1287/moor.16.1.119
[32] Ruiz, P.A., Philbrick, R.C., Zack, E., Cheung, K.W., Sauer, P.W.: Uncertainty management in the unit commitment problem. IEEE Trans. Power Syst. 24(2), 642-651 (2009) · doi:10.1109/TPWRS.2008.2012180
[33] Ryan, S.M., Wets, R.J.B., Woodruff, D.L., Silva-Monroy, C., Watson, J.P.: Toward scalable, parallel progressive hedging for stochastic unit commitment. In: 2013 IEEE Power and Energy Society General Meeting. IEEE, New York (2013) · Zbl 1225.91032
[34] Santoso, T., Ahmed, S., Goetschalckx, M., Shapiro, A.: A stochastic programming approach for supply chain network design under uncertainty. Eur. J. Oper. Res. 167(1), 96-115 (2005) · Zbl 1075.90010 · doi:10.1016/j.ejor.2004.01.046
[35] Shor, N.Z., Kiwiel, K.C., Ruszczynski, A.: Minimization Methods for Non-differentiable Functions, vol. 3. Springer, Berlin (1985)
[36] Sun, J., Tesfatsion, L.: Dynamic testing of wholesale power market designs: an open-source agent-based framework. Comput. Econ. 30(3), 291-327 (2007) · Zbl 1310.91118 · doi:10.1007/s10614-007-9095-1
[37] Takriti, S., Birge, J.R., Long, E.: A stochastic model for the unit commitment problem. IEEE Trans. Power Syst. 11(3), 1497-1508 (1996) · doi:10.1109/59.535691
[38] van der Vlerk, M.H.: Stochastic integer programming bibliography. http://www.eco.rug.nl/mally/biblio/sip.html (1996-2007) · Zbl 0909.90222
[39] Watson, J., Woodruff, D., Hart, W.: PySP: Modeling and solving stochastic programs in Python. Math. Program. Comput. 4(2), 109-149 (2012) · Zbl 1275.90049
[40] Watson, J.P., Woodruff, D.L.: Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Comput. Manag. Sci. 8(4), 355-370 (2011) · Zbl 1225.91032 · doi:10.1007/s10287-010-0125-4
[41] Wets, R.J.B.: On the relation between stochastic and deterministic optimization. In: Bensoussan, A., Lions, J.L. (eds.) Control Theory, Numerical Methods and Computer Systems Modelling, pp. 350-361. Springer, Berlin (1975)
[42] Wets, RJB; Wallace, SW (ed.), The aggregation principle in scenario analysis and stochastic optimization, 91-113 (1989), Berlin · doi:10.1007/978-3-642-83724-1_4
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.