Optimization Online


A Distributed Interior-Point KKT Solver for Multistage Stochastic Optimization

Hübner Jens (huebner***at***ifam.uni-hannover.de)
Schmidt Martin (mar.schmidt***at***fau.de)
Steinbach Marc C. (mcs***at***ifam.uni-hannover.de)

Abstract: Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate number of variables per node. For this setting we develop a distributed implementation based on data parallelism in a depth-first distribution of the scenario tree over the processes. Our theoretical analysis predicts very low memory and communication overheads. Detailed computational experiments confirm this prediction and demonstrate the overall performance of the algorithm. We solve multistage stochastic quadratic programs with up to 400e6 variables and 8.59e9 KKT matrix entries or 136e6 variables and 12.6e9 entries on a compute cluster with 384 GiB of RAM.

Keywords: Multistage stochastic programming, Parallel computing, Distributed computing, KKT systems, Interior-point methods

Category 1: Stochastic Programming

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

Category 3: Applications -- OR and Management Sciences (Finance and Economics )


Download: [PDF]

Entry Submitted: 02/09/2016
Entry Accepted: 02/09/2016
Entry Last Modified: 02/10/2016

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 Optimization Society