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

Annals of Operations Research Vol. 166, nº. 1, pp. 355 - 373


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

Índice de impacto JCR y cuartil WoS: 0,961 (2009); 4,800 - Q1 (2022)

Referencia DOI: DOI icon

Publicado en papel: Febrero 2009.

Publicado on-line: Noviembre 2008.

J.M. Latorre, S. Cerisola, A. Ramos, R. Palacios, Analysis of stochastic problem decomposition algorithms in computational grids. Annals of Operations Research. Vol. 166, nº. 1, pp. 355 - 373, Febrero 2009. [Online: Noviembre 2008]

    Líneas de investigación:
  • *Técnicas de cálculo paralelo y distribuido aplicado a la solución de problemas de programación matemática
  • *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