Ir arriba
Información del artículo

Analysis of stochastic problem decomposition algorithms in computational grids

J.M. Latorre, S. Cerisola, A. Ramos, R. Palacios

Stochastic programming usually represents uncertainty discretely by means of a scenario tree. This representation leads to an exponential growth of the size of stochastic mathematical problems when better accuracy is needed. Trying to solve the problem as a whole, considering all scenarios together, yields to huge memory requirements that surpass the capabilities of current computers. Thus, decomposition algorithms are employed to divide the problem into several smaller subproblems and to coordinate their solution in order to obtain the global optimum. This paper analyzes several decomposition strategies based on the classical Benders decomposition algorithm, and applies them in the emerging computational grid environments. Most decomposition algorithms are not able to take full advantage of all the computing power available in a grid system because of unavoidable dependencies inherent to the algorithms. However, a special decomposition method presented in this paper aims at reducing dependency among subproblems, to the point where all the subproblems can be sent simultaneously to the grid. All algorithms have been tested in a grid system, measuring execution times required to solve standard optimization problems and a real-size hydrothermal coordination problem. Numerical results are shown to confirm that this new method outperforms the classical ones when used in grid computing environments.


Palabras clave: Stochastic programming. Linear programming. Benders decomposition. Grid computing. Performance analysis


Annals of Operations Research. Volumen: 166 Numero: 1 Páginas: 355-373

Índice de impacto JCR y cuartil Scopus: JCR impact factor: 0.961 (2009); 2.284 (2018).

Referencia DOI: DOI icon 10.1007/s10479-008-0476-1    

Publicado en papel: Febrero 2009.



Cita:
J.M. Latorre, S. Cerisola, A. Ramos, R. Palacios. Analysis of stochastic problem decomposition algorithms in computational grids. Annals of Operations Research. vol. 166, no. 1, pp. 355-373, Febrero 2009.


    Líneas de investigación:
  • *Planificación táctica a medio plazo
  • *Análisis de estrategia a largo plazo

pdf  Previsualizar
pdf Solicitar el artículo completo a los autores



Aviso legal  |  Política de cookies |  Política de Privacidad

© Universidad Pontificia Comillas, Escuela Técnica Superior de Ingeniería - ICAI, Instituto de Investigación Tecnológica

Calle de Santa Cruz de Marcenado, 26 - 28015 Madrid, España - Tel: (+34) 91 5422 800