Optimization Online


On the parallel solution of dense saddle-point linear systems arising in stochastic programming

Miles Lubin(mlubin***at***uchicago.edu)
Cosmin Petra(petra***at***mcs.anl.gov)
Mihai Anitescu(anitescu***at***mcs.anl.gov)

Abstract: We present a novel approach for solving dense saddle-point linear systems in a distributed-memory environment. This work is motivated by an application in stochastic optimization problems with recourse, but the proposed approach can be used for a large family of dense saddle-point systems, in particular those arising in convex programming. Although stochastic optimization problems have many important applications, they can present serious computational difficulties. In particular, sample average approximation (SAA) problems with a large number of samples are often too big to solve on a single shared-memory system. Recent work has developed interior point methods and specialized linear algebra to solve these problems in parallel, using a scenario-based decomposition that distributes the data and work across computational nodes. Even for sparse SAA problems, the decomposition produces a dense and possibly very large saddle-point linear system that must be solved repeatedly. We developed a specialized parallel factorization procedure for these systems, together with a streamlined method for assembling the distributed dense matrix. Strong scaling tests indicate over 90% efficiency on 1,024 cores on a stochastic unit commitment problem with 57 million variables. Stochastic unit commitment problems with up to 189 million variables are solved efficiently on up to 2,048 cores.

Keywords: stochastic programming, parallel computing, parallel dense linear algebra, saddle-point

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Preprint ANL/MCS-P1798-1010, Argonne National Laboratory, 2010.

Download: [PDF]

Entry Submitted: 10/26/2010
Entry Accepted: 10/26/2010
Entry Last Modified: 10/26/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society