Details
| Original language | English |
|---|---|
| Pages (from-to) | 612-630 |
| Number of pages | 19 |
| Journal | INFORMS journal on computing |
| Volume | 29 |
| Issue number | 4 |
| Publication status | Published - 1 Aug 2017 |
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 400 × 106 variables and 8:59 × 109 KKT matrix entries or 136×106 variables and 12:6×109 entries on a compute cluster with 384 GB RAM.
Keywords
- Distributed computing, Interior-point methods, KKT systems, Multistage stochastic programming, Parallel computing, Portfolio optimization
ASJC Scopus subject areas
- Computer Science(all)
- Software
- Computer Science(all)
- Information Systems
- Computer Science(all)
- Computer Science Applications
- Decision Sciences(all)
- Management Science and Operations Research
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: INFORMS journal on computing, Vol. 29, No. 4, 01.08.2017, p. 612-630.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - A distributed interior-point KKT solver for multistage stochastic optimization
AU - Hübner, Jens
AU - Schmidt, Martin
AU - Steinbach, Marc C.
N1 - Publisher Copyright: © 2017 INFORMS.
PY - 2017/8/1
Y1 - 2017/8/1
N2 - 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 400 × 106 variables and 8:59 × 109 KKT matrix entries or 136×106 variables and 12:6×109 entries on a compute cluster with 384 GB RAM.
AB - 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 400 × 106 variables and 8:59 × 109 KKT matrix entries or 136×106 variables and 12:6×109 entries on a compute cluster with 384 GB RAM.
KW - Distributed computing
KW - Interior-point methods
KW - KKT systems
KW - Multistage stochastic programming
KW - Parallel computing
KW - Portfolio optimization
UR - http://www.scopus.com/inward/record.url?scp=85036453067&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2017.0748
DO - 10.1287/ijoc.2017.0748
M3 - Article
AN - SCOPUS:85036453067
VL - 29
SP - 612
EP - 630
JO - INFORMS journal on computing
JF - INFORMS journal on computing
SN - 1091-9856
IS - 4
ER -