Previous |  Up |  Next


Title: Warm-start cuts for Generalized Benders Decomposition (English)
Author: Kůdela, Jakub
Author: Popela, Pavel
Language: English
Journal: Kybernetika
ISSN: 0023-5954 (print)
ISSN: 1805-949X (online)
Volume: 53
Issue: 6
Year: 2017
Pages: 1012-1025
Summary lang: English
Category: math
Summary: In this paper, we describe a decomposition algorithm suitable for two-stage convex stochastic programs known as Generalized Benders Decomposition. For this algorithm we propose a new reformulation that incorporates a lower bound cut that serves as a warm-start, decreasing the overall computation time. Additionally, we test the performance of the proposed reformulation on two modifications of the algorithm (bunching and multicut) using numerical examples. The numerical part is programmed in MATLAB and uses state-of-the-art conic solvers. (English)
Keyword: stochastic programming
Keyword: Generalized Benders Decomposition
Keyword: {\it L}-shaped method
Keyword: warm–start
MSC: 49M27
MSC: 90C15
MSC: 90C25
idZBL: Zbl 06861638
idMR: MR3758932
DOI: 10.14736/kyb-2017-6-1012
Date available: 2018-02-26T11:23:46Z
Last updated: 2018-05-25
Stable URL:
Reference: [1] Bazaraa, M. S., Sherali, H. D., Shetty, C. M.: Nonlinear Programming: Theory and Algorithms. Third edition..Wiley-Interscience, Hoboken, N. J. 2006. MR 2218478, 10.1002/0471787779
Reference: [2] Benders, J. F.: Partitioning procedures for solving mixed-variables programming problems..Numerische Mathematik 4 (1962), 1, 238-252. Zbl 1115.90361, MR 0147303, 10.1007/bf01386316
Reference: [3] Birge, J. R., Louveaux, F.: Introduction to Stochastic Programming..Springer, New York 2000. MR 2807730
Reference: [4] Boyd, S. P., Vandenberghe, L.: Convex Optimization..Cambridge University Press, New York 2004. Zbl 1058.90049, MR 2061575, 10.1017/cbo9780511804441
Reference: [5] Floudas, C. A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications..Oxford University Press, Oxford 1995.
Reference: [6] Floudas, C. A., Pardalos, P. M.: Encyclopedia of Optimization..Springer, New York 2009. MR 3593766, 10.1007/978-0-387-74759-0
Reference: [7] Geoffrion, A. M.: Generalized Benders decomposition..Journal of Optimization Theory and Applications 10 (1972), 4, 237-260. MR 0327310, 10.1007/bf00934810
Reference: [8] Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs..In: Recent Advances in Learning and Control (V. Blondel, S. Boyd and H. Kimura, eds.), Springer-Verlag Limited, Berlin 2008, pp. 95-110. MR 2409077, 10.1007/978-1-84800-155-8_7
Reference: [9] Madansky, A.: Inequalities for stochastic linear programming problems..Management Science 6 (1960), 197-204. MR 0110581, 10.1287/mnsc.6.2.197
Reference: [10] Mittelmann, H. D.: The state-of-the-art in conic optimization software..In: Handbook on Semidefinite, Conic and Polynomial Optimization (M. F. Anjos and J. B. Lasserre, eds.), Springer US, New York 2012, pp. 671-686. MR 2894667, 10.1007/978-1-4614-0769-0_23
Reference: [11] Pflug, G., Maggioni, F.: Bounds and approximations for multistage stochastic programs..SIAM J. Optim. 26 (2016), 1, 831-855. MR 3477324, 10.1137/140971889
Reference: [12] Slyke, R. M. Van, Wets, R.: L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming..SIAM J. Appl. Math. 17 (1969), 4, 638-663. MR 0253741, 10.1137/0117061
Reference: [13] Wolf, C., Fabián, C. I., Koberstein, A., Suhl, L.: Applying oracles of on-demand accuracy in two-stage stochastic programming - A computational study..Europ. J. Oper. Res. 239 (2014), 2, 437-448. MR 3231913, 10.1016/j.ejor.2014.05.010
Reference: [14] Zverovich, V., Fabián, C. I., Ellison, E. F. D., Mitra, G.: A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition..Math. Program. Computation 4 (2012), 3, 211-238. MR 2967981, 10.1007/s12532-012-0038-z


Files Size Format View
Kybernetika_53-2017-6_4.pdf 342.0Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo