Analysis of the performance of benders-based distributed decomposition methods for linear stochastic programming

Abstract

In stochastic programming, considering uncertainty might lead to large scale 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 additional computation time for coordination due to the iterative nature 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 paper 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 can take advantage of computer resources available in the grid, thus compensating a small increase in the overall computational weight. In particular, 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 Benders 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.