Scalable stochastic programming
Monday, April 11, 2011
3:30PM – 5PM
Cosmin G. Petra
Our recent work is devoted to solving large scale two-stage stochastic programming problems on massively parallel machines. The solution of sample average approximation problems is obtained using an interior-point framework. Data and computations are distributed across nodes by using a scenario-based decomposition based on a Schur-complement technique. We introduce a stochastic preconditioner for the Schur complement matrix that removes the expensive factorization of the dense Schur-complement from the parallel execution flow at the price of a few cheap CG/BICGSTAB iterations. A considerable increase in scalability is obtained for a wide range of cores. We also present the spectral analysis of the preconditioned matrix which indicates an exponential clustering of the eigenvalues of the preconditioned matrix around 1.
The preconditioning technique however suffers from a memory bottleneck as does the classical Schur-complement. We overcome this issue by using a novel approach for distributing and directly solving the dense Schur-complement systems in parallel in a distributed memory environment. Also, in order to efficiently use all the cores inside a node, we implemented a hybrid parallel programming model which uses multithreaded sparse linear solver WSMP together with OpenMP to achieve shared-memory parallelism for the second-stage computations. The solver has been used to solve a stochastic unit commitment problem with transmission constraints on 131,072 cores (32,768 nodes) of the "Intrepid" Blue Gene/P system at Argonne National Laboratory.
Authors: Cosmin G. Petra, Miles Lubin, Mihai Anitescu
Hosted by Omar Ghattas