×

zbMATH — the first resource for mathematics

Partition-based decomposition algorithms for two-stage stochastic integer programs with continuous recourse. (English) Zbl 1435.90095
Summary: In this paper, we propose partition-based decomposition algorithms for solving two-stage stochastic integer program with continuous recourse. The partition-based decomposition method enhance the classical decomposition methods (such as Benders decomposition) by utilizing the inexact cuts (coarse cuts) induced by a scenario partition. Coarse cut generation can be much less expensive than the standard Benders cuts, when the partition size is relatively small compared to the total number of scenarios. We conduct an extensive computational study to illustrate the advantage of the proposed partition-based decomposition algorithms compared with the state-of-the-art approaches.

MSC:
90C15 Stochastic programming
90C10 Integer programming
Software:
NumPy; PLCP; SQPlab; SUTIL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmed, S., Garcia, R., Kong, N., Ntaimo, L., Parija, G. R., Qiu, F. (2015). A stochastic integer programming test problem library, http://www.isye.gatech.edu/ sahmed/siplib.
[2] Albornoz, Vm; Benario, P.; Rojas, Me, A two-stage stochastic integer programming model for a thermal power system expansion, International Transactions in Operational Research, 11, 3, 243-257 (2004) · Zbl 1162.90526
[3] Benders, Jf, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302
[4] Bienstock, Daniel, & Zuckerberg, Mark (2010). Solving LP relaxations of large-scale precedence constrained problems. IPCO 1-14. · Zbl 1285.90006
[5] Birge, Jr; Louveaux, F., Introduction to stochastic programming (2011), Berlin: Springer Science & Business Media, Berlin · Zbl 1223.90001
[6] Bodur, M.; Dash, S.; Günlük, O.; Luedtke, J., Strengthened benders cuts for stochastic integer programs with continuous recourse, INFORMS Journal on Computing, 29, 1, 77-91 (2016) · Zbl 1364.90220
[7] Bodur, Merve, Luedtke, James R (2016). Mixed-integer rounding enhanced benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty. Management Science.
[8] Bonnans, J-F; Gilbert, Jc; Lemaréchal, C.; Sagastizábal, C., Numerical optimization: theoretical and practical aspects. (2006), Berlin: Springer, Berlin
[9] Contreras, I.; Cordeau, J-F; Laporte, G., Benders decomposition for large-scale uncapacitated hub location, Operations Research, 59, 6, 1477-1490 (2011) · Zbl 1242.90094
[10] De Oliveira, W.; Sagastizábal, C., Level bundle methods for oracles with on-demand accuracy, Optimization Methods and Software, 29, 6, 1180-1209 (2014) · Zbl 1306.90121
[11] De Oliveira, W.; Sagastizábal, C.; Scheimberg, S., Inexact bundle methods for two-stage stochastic programming, SIAM Journal on Optimization, 21, 2, 517-544 (2011) · Zbl 1226.90057
[12] Espinoza, D.; Moreno, E., A primal-dual aggregation algorithm for minimizing conditional-value-at-risk in linear programs, Computational Optimization and Applications, 59, 617-638 (2014) · Zbl 1310.90071
[13] Fragniere, E.; Gondzio, J.; Vial, J-P, Building and solving large-scale stochastic programs on an affordable distributed computing system, Annals of Operations Research, 99, 1-4, 167-187 (2000) · Zbl 0990.90083
[14] Higle, J. L., & Sen, S. (1991). Stochastic decomposition: An algorithm for two-stage linear programs with recourse. Mathematics of Operations Research, 16(3), 650-669. · Zbl 0746.90045
[15] Hiriart-Urruty, J-B; Lemaréchal, C., Convex analysis and minimization algorithms I: Fundamentals (2013), Berlin: Springer science & business media, Berlin
[16] Kim, K.; Mehrotra, S., A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management, Operations Research, 63, 6, 1431-1451 (2015) · Zbl 1334.90092
[17] Jesús, Ml; Cerisola, S.; Ramos, A.; Palacios, R., Analysis of stochastic problem decomposition algorithms in computational grids, Annals of Operations Research, 166, 1, 355-373 (2009) · Zbl 1163.90684
[18] Lemaréchal, C.; Nemirovskii, A.; Nesterov, Y., New variants of bundle methods, Mathematical Programming, 69, 1-3, 111-147 (1995) · Zbl 0857.90102
[19] Linderoth, J.; Shapiro, A.; Wright, S., The empirical behavior of sampling methods for stochastic programming, Annals of Operations Research, 142, 215-241 (2006) · Zbl 1122.90391
[20] Louveaux, Fv, Discrete stochastic location models, Annals of Operations Research, 6, 2, 21-34 (1986)
[21] Ruszczyński, A., A regularized decomposition method for minimizing a sum of polyhedral functions, Mathematical Programming, 35, 3, 309-333 (1986) · Zbl 0599.90103
[22] Ruszczyński, A.; Świetanowski, A., Accelerating the regularized decomposition method for two stage stochastic linear problems, European Journal of Operational Research, 101, 2, 328-342 (1997) · Zbl 0929.90067
[23] Saharidis, Gkd; Minoux, M.; Ierapetritou, Mg, Accelerating benders method using covering cut bundle generation, International Transactions in Operational Research, 17, 2, 221-237 (2010) · Zbl 1279.90072
[24] Sen, S., Subgradient decomposition and differentiability of the recourse function of a two stage stochastic linear program, Operations Research Letters, 13, 3, 143-148 (1993) · Zbl 0778.90047
[25] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on Stochastic programming: Modeling and theory (2009), Philadelphia: SIAM, Philadelphia · Zbl 1183.90005
[26] Song, Y.; Luedtke, J., An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse, SIAM Journal on Optimization, 25, 3, 1344-1367 (2015) · Zbl 1317.90222
[27] Trukhanov, S.; Ntaimo, L.; Schaefer, A., Adaptive multicut aggregation for two-stage stochastic linear programs with recourse, European Journal of Operational Research, 206, 2, 395-406 (2010) · Zbl 1188.90189
[28] van Ackooij, Wim, de Oliveira, Welington, Song, Yongjia (2016). An adaptive partition-based level decomposition for solving two-stage stochastic programs with fixed recourse. Submitted for publication.
[29] Van Der Walt, S.; Colbert, Sc; Varoquaux, G., The numpy array: A structure for efficient numerical computation, Computing in Science and Engineering, 13, 2, 22-30 (2011)
[30] Van Slyke, Rm; Wets, R., L-shaped linear programs with applications to optimal control and stochastic programming, SIAM Journal on Applied Mathematics, 17, 4, 638-663 (1969) · Zbl 0197.45602
[31] Wolf, C.; Fábián, Ci; Koberstein, A.; Suhl, L., Applying oracles of on-demand accuracy in two-stage stochastic programming - A computational study, European Journal of Operational Research, 239, 2, 437-448 (2014) · Zbl 1339.90257
[32] Wolf, C.; Koberstein, A., Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method, European Journal of Operational Research, 230, 1, 143-156 (2013) · Zbl 1317.90223
[33] You, F.; Grossmann, Ie, Multicut benders decomposition algorithm for process supply chain planning under uncertainty, Annals of Operations Research, 210, 1, 191-211 (2013) · Zbl 1284.90046
[34] Zhu, X.; Sherali, Hd, Two-stage workforce planning under demand fluctuations and uncertainty, Journal of the Operational Research Society, 60, 1, 94-103 (2009) · Zbl 1168.90533
[35] Zverovich, V.; Fábián, Ci; Ellison, Efd; Mitra, G., A computational study of a solver system for processing two-stage stochastic LPs with enhanced benders decomposition, Mathematical Programming Computation, 4, 3, 211-238 (2012) · Zbl 1275.90050
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.