×

On parallelizing dual decomposition in stochastic integer programming. (English) Zbl 1286.90102

Summary: For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Carøe and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the master program by using structure-exploiting interior-point solvers. Our results demonstrate the potential for parallel speedup and the importance of regularization (stabilization) in the dual optimization. Load imbalance is identified as a remaining barrier to parallel scalability.

MSC:

90C15 Stochastic programming
90C11 Mixed integer programming
90C10 Integer programming
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41 (2009) · Zbl 1171.90476
[2] Amdahl, G. M., Validity of the single processor approach to achieving large scale computing capabilities, (Proceedings of AFIPS Spring Joint Computer Conference (1967), ACM: ACM Atlantic City, NJ), 483-485
[3] Birge, J. R.; Louveaux, F., Introduction to Stochastic Programming (2011), Springer: Springer New York · Zbl 1223.90001
[4] Briant, O.; Lemaréchal, C.; Meurdesoif, P.; Michel, S.; Perrot, N.; Vanderbeck, F., Comparison of bundle and classical column generation, Mathematical Programming, 113, 2, 299-344 (2008) · Zbl 1152.90005
[5] Carøe, C. C.; Schultz, R., Dual decomposition in stochastic integer programming, Operations Research Letters, 24, 1-2, 37-45 (1999) · Zbl 1063.90037
[6] Duff, I. S., MA57: a code for the solution of sparse symmetric definite and indefinite systems, ACM Transactions on Mathematical Software, 30, 2, 118-144 (2004) · Zbl 1070.65525
[7] Fábián, C. I.; Szöke, Z., Solving two-stage stochastic programming problems with level decomposition, Computational Management Science, 4, 4, 313-353 (2007) · Zbl 1145.90045
[9] Frangioni, A., About Lagrangian methods in integer optimization, Annals of Operations Research, 139, 1, 163-193 (2005) · Zbl 1091.90048
[10] Gertz, E. M.; Wright, S. J., Object-oriented software for quadratic programming, ACM Transactions on Mathematical Software, 29, 1, 58-81 (2003) · Zbl 1068.90586
[11] Gondzio, J.; Grothey, A., Parallel interior-point solver for structured quadratic programs: application to financial planning problems, Annals of Operations Research, 152, 1, 319-339 (2007) · Zbl 1144.90510
[13] Hiriart-Urruty, J. B.; Lemaréchal, C., Convex Analysis and Minimization Algorithms, Vol. I-II (1993), Springer-Verlag: Springer-Verlag Germany · Zbl 0795.49002
[14] Kiwiel, K. C., A Cholesky dual method for proximal piecewise linear programming, Numerische Mathematik, 68, 3, 325-340 (1994) · Zbl 0822.65038
[15] Kiwiel, K. C., Approximations in proximal bundle methods and decomposition of convex programs, Journal of Optimization Theory and Applications, 84, 3, 529-548 (1995) · Zbl 0824.90110
[16] Lemaréchal, C., Lagrangian relaxation, (Jünger, M.; Naddef, D., Computational Combinatorial Optimization (2001), Springer), 112-156 · Zbl 1052.90065
[17] Lemaréchal, C.; Nemirovskii, A.; Nesterov, Y., New variants of bundle methods, Mathematical Programming, 69, 1, 111-147 (1995) · Zbl 0857.90102
[18] Linderoth, J.; Wright, S., Decomposition algorithms for stochastic programming on a computational grid, Computational Optimization and Applications, 24, 2, 207-250 (2003) · Zbl 1094.90026
[19] Lubin, M.; Petra, C. G.; Anitescu, M.; Zavala, V., Scalable stochastic optimization of complex energy systems, (Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (2011), ACM: ACM Seattle, WA), 64:1-64:10
[20] Lulli, G.; Sen, S., A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems, Management Science, 50, 6, 786-796 (2004) · Zbl 1232.90314
[21] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM Journal on Optimization, 2, 4, 575-601 (1992) · Zbl 0773.90047
[22] Römisch, W.; Vigerske, S., Recent progress in two-stage mixed-integer stochastic programming with applications to power production planning, (Pardalos, P. M.; Rebennack, S.; Pereira, M. V.F.; Iliadis, N. A.; Pardalos, P. M., Handbook of Power Systems, Vol. I (2010), Springer), 177-208 · Zbl 1359.90077
[23] Ruszczyński, A., A regularized decomposition method for minimizing a sum of polyhedral functions, Mathematical Programming, 35, 3, 309-333 (1986) · Zbl 0599.90103
[24] Sen, S., Algorithms for stochastic mixed-integer programming models, (Aardal, K.; Nemhauser, G. L.; Weismantel, R., Discrete Optimization (2005), Elsevier), 515-558 · Zbl 1172.90457
[25] Zverovich, V.; Fábián, C.; Ellison, E.; 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. 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.