Analysis of the Performance of Benders-based Distributed Decomposition Methods for Linear Stochastic Programming

In stochastic programming, the consideration of uncertainty might lead to large scale prob-lems. In these problems, computational resources might fall short of the requirements for solving these problems, especially concerning memory capacity. Decomposition techniques help to clear this obstacle, by producing a set of smaller subproblems at the cost of addi-tional computation time for coordination due to the iterative of the resolution algorithm. However, one way to mitigate the effect of the increased computational time derived from the decomposition is to solve the subproblems in parallel or distributed systems. This pa-per compares the performance of two different Benders decomposition techniques for linear stochastic problems when executed in two different computational grids (one using single-core computers and the other using dual-core computers). Decomposition methods that create less task-dependency take better advantage of computer resources available in the grid, thus compensating a small increase in the overall computational weight. In particu-lar, the proposed method called “complete-scenario decomposition ” requires a larger total CPU time (the sum of all individual CPU times in the grid) compared to traditional Ben-ders decomposition; however, the computational overhead is compensated by a better grid performance, so the proposed method yields shorter execution times as measured by the user