Kybernetika 53 no. 6, 1012-1025, 2017

Warm-start cuts for Generalized Benders Decomposition

Jakub Kůdela and Pavel PopelaDOI: 10.14736/kyb-2017-6-1012

Abstract:

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.

Keywords:

stochastic programming, Generalized Benders Decomposition, L-shaped method, warm-start

Classification:

90C15, 90C25, 49M27

paper.pdf

References:

  1. M. S. Bazaraa, H. D. Sherali and C. M. Shetty: Nonlinear Programming: Theory and Algorithms. Third edition. Wiley-Interscience, Hoboken, N. J. 2006.   DOI:10.1002/0471787779
  2. J. F. Benders: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4 (1962), 1, 238-252.   DOI:10.1007/bf01386316
  3. J. R. Birge and F. Louveaux: Introduction to Stochastic Programming. Springer, New York 2000.   CrossRef
  4. S. P. Boyd and L. Vandenberghe: Convex Optimization. Cambridge University Press, New York 2004.   DOI:10.1017/cbo9780511804441
  5. C. A. Floudas: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, Oxford 1995.   CrossRef
  6. C. A. Floudas and P. M. Pardalos: Encyclopedia of Optimization. Springer, New York 2009.   DOI:10.1007/978-0-387-74759-0
  7. A. M. Geoffrion: Generalized Benders decomposition. Journal of Optimization Theory and Applications 10 (1972), 4, 237-260.   DOI:10.1007/bf00934810
  8. M. Grant and S. Boyd: 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.   DOI:10.1007/978-1-84800-155-8_7
  9. A. Madansky: Inequalities for stochastic linear programming problems. Management Science 6 (1960), 197-204.   DOI:10.1287/mnsc.6.2.197
  10. H. D. Mittelmann: 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.   DOI:10.1007/978-1-4614-0769-0_23
  11. G. Pflug and F. Maggioni: Bounds and approximations for multistage stochastic programs. SIAM J. Optim. 26 (2016), 1, 831-855.   DOI:10.1137/140971889
  12. R. M. Van Slyke and R. Wets: L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming. SIAM J. Appl. Math. 17 (1969), 4, 638-663.   DOI:10.1137/0117061
  13. C. Wolf, C. I. Fabián, A. Koberstein and L. Suhl: Applying oracles of on-demand accuracy in two-stage stochastic programming - A computational study. Europ. J. Oper. Res. 239 (2014), 2, 437-448.   DOI:10.1016/j.ejor.2014.05.010
  14. V. Zverovich, C. I. Fabián, E. F. D. Ellison and G. Mitra: 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.   DOI:10.1007/s12532-012-0038-z