Analysis of the Performance of Benders-based Decomposition Methods for Linear Stochastic Programming on a Grid

Abstract

Large-scale stochastic optimization problems can be divided into smaller subproblems using decomposition; however the computational overhead of decomposition methods is not justified except for the reason of adjusting the size of the problem to the computer resources being used. Decomposition is usually required due to memory size limitations, since large optimization problems may require considerably more memory than the physical memory available, and the use of virtual memory drops the performance dramatically. However, one way to mitigate the effect of increased computational time derived from decomposition is to solve subproblems in parallel or distributed systems. This paper compares the performance of two different Benders decomposition techniques when executed in two different computational grids (one using single-core computers and other using dual-core computers). Decomposition methods that create less task-dependencies take better 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 (addition 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.