Parallel Birge and Qi Factorization of Three-stage Stochastic Linear Programs

Abstract

Many practical problems, such as portfolio management, problems in manufacturing, transportation or power generation, can be modeled as stochastic programs. Stochastic programs provide an effective framework for sequential decision problems with uncertain data, when uncertainty can be modeled by a discrete set of scenarios. In this paper we present an algorithm for solving a three-stage stochastic linear program based on the Birge and Qi factorization of a constraint matrix product in the frame of the primal-dual path-following interior point method. Moreover, we discuss the parallelization of this method for distributed-memory machines using Fortran/MPI and the linear algebra package LAPACK. Performance experiments on a 64-processor Beowulf cluster show the effectiveness of the proposed parallelization strategy, which exploits two levels of parallelism.