Warm-start cuts for Generalized Benders Decomposition

Jakub Kůdela; Pavel Popela

Kybernetika (2017)

  • Volume: 53, Issue: 6, page 1012-1025
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Kůdela, Jakub, and Popela, Pavel. "Warm-start cuts for Generalized Benders Decomposition." Kybernetika 53.6 (2017): 1012-1025. <http://eudml.org/doc/294377>.

@article{Kůdela2017,
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.},
author = {Kůdela, Jakub, Popela, Pavel},
journal = {Kybernetika},
keywords = {stochastic programming; Generalized Benders Decomposition; L-shaped method; warm–start},
language = {eng},
number = {6},
pages = {1012-1025},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Warm-start cuts for Generalized Benders Decomposition},
url = {http://eudml.org/doc/294377},
volume = {53},
year = {2017},
}

TY - JOUR
AU - Kůdela, Jakub
AU - Popela, Pavel
TI - Warm-start cuts for Generalized Benders Decomposition
JO - Kybernetika
PY - 2017
PB - Institute of Information Theory and Automation AS CR
VL - 53
IS - 6
SP - 1012
EP - 1025
AB - 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.
LA - eng
KW - stochastic programming; Generalized Benders Decomposition; L-shaped method; warm–start
UR - http://eudml.org/doc/294377
ER -

References

top
  1. Bazaraa, M. S., Sherali, H. D., Shetty, C. M., 10.1002/0471787779, Wiley-Interscience, Hoboken, N. J. 2006. MR2218478DOI10.1002/0471787779
  2. Benders, J. F., 10.1007/bf01386316, Numerische Mathematik 4 (1962), 1, 238-252. Zbl1115.90361MR0147303DOI10.1007/bf01386316
  3. Birge, J. R., Louveaux, F., Introduction to Stochastic Programming., Springer, New York 2000. MR2807730
  4. Boyd, S. P., Vandenberghe, L., 10.1017/cbo9780511804441, Cambridge University Press, New York 2004. Zbl1058.90049MR2061575DOI10.1017/cbo9780511804441
  5. Floudas, C. A., Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications., Oxford University Press, Oxford 1995. 
  6. Floudas, C. A., Pardalos, P. M., 10.1007/978-0-387-74759-0, Springer, New York 2009. MR3593766DOI10.1007/978-0-387-74759-0
  7. Geoffrion, A. M., 10.1007/bf00934810, Journal of Optimization Theory and Applications 10 (1972), 4, 237-260. MR0327310DOI10.1007/bf00934810
  8. Grant, M., Boyd, S., 10.1007/978-1-84800-155-8_7, In: Recent Advances in Learning and Control (V. Blondel, S. Boyd and H. Kimura, eds.), Springer-Verlag Limited, Berlin 2008, pp. 95-110. MR2409077DOI10.1007/978-1-84800-155-8_7
  9. Madansky, A., 10.1287/mnsc.6.2.197, Management Science 6 (1960), 197-204. MR0110581DOI10.1287/mnsc.6.2.197
  10. Mittelmann, H. D., 10.1007/978-1-4614-0769-0_23, In: Handbook on Semidefinite, Conic and Polynomial Optimization (M. F. Anjos and J. B. Lasserre, eds.), Springer US, New York 2012, pp. 671-686. MR2894667DOI10.1007/978-1-4614-0769-0_23
  11. Pflug, G., Maggioni, F., 10.1137/140971889, SIAM J. Optim. 26 (2016), 1, 831-855. MR3477324DOI10.1137/140971889
  12. Slyke, R. M. Van, Wets, R., 10.1137/0117061, SIAM J. Appl. Math. 17 (1969), 4, 638-663. MR0253741DOI10.1137/0117061
  13. Wolf, C., Fabián, C. I., Koberstein, A., Suhl, L., 10.1016/j.ejor.2014.05.010, Europ. J. Oper. Res. 239 (2014), 2, 437-448. MR3231913DOI10.1016/j.ejor.2014.05.010
  14. Zverovich, V., Fabián, C. I., Ellison, E. F. D., Mitra, G., 10.1007/s12532-012-0038-z, Math. Program. Computation 4 (2012), 3, 211-238. MR2967981DOI10.1007/s12532-012-0038-z

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.