Invited Session Fri.1.MA 141

Friday, 10:30 - 12:00 h, Room: MA 141

Cluster 22: Stochastic optimization [...]

Progressive hedging: Innovations and applications


Chair: David Woodruff



Friday, 10:30 - 10:55 h, Room: MA 141, Talk 1

David Woodruff
Bundling scenarios in progressive hedging

Coauthors: Jean-Paul Watson, Roger J-B Wets


In this paper, we provide theoretical background and describe computational experience with schemes for bundling
scenarios to improve convergence rates and reduce computational effort for Progressive Hedging (PH). Although the idea was floated (Wets 89, Wets 91) at about the same
time PH was first described, it has received very little attention. As we will show, bundling can be an
important component in PH.
We provide brief introduction to
stochastic programming problems and their solution via PH. Theoretical justification and guidance for
scenario bundling is introduced. Computational experiments with scenario bundling are described.



Friday, 11:00 - 11:25 h, Room: MA 141, Talk 2

Jia Kang
Parallel solution of structured nonlinear problems using Pyomo and PySP

Coauthors: Carl D. Laird, Jean-Paul Watson, David L. Woodruff, Daniel P. Word


Nonlinear programming has proven to be an effective tool for dynamic optimization, parameter estimation, and nonlinear stochastic programming. However, as problem sizes continue to increase, these problems can exceed the computing capabilities of modern desktop computers using serial solution approaches.
Block structured problems arise in a number of areas, including nonlinear stochastic programming and parameter estimation. Pyomo, an open-source algebraic modeling language, and PySP, a python-based stochastic programming framework, are used to formulate and solve these problems in parallel. In this work, we compare two approaches for parallel solution of these problems. Rockafellar and Wets' progressive hedging algorithm is used to efficiently solve large-scale parameter estimation problems in parallel with IPOPT (a nonlinear interior-point package) used as the sub-problem solver. As well, an internal decomposition approach that solves the structured linear KKT system in parallel is also used. We compare these parallel solution approaches with serial methods and discuss our experience working within Pyomo and PySP.



Friday, 11:30 - 11:55 h, Room: MA 141, Talk 3

Jean-Paul Watson
Asynchronous progressive hedging

Coauthors: Roger Jb Wets, David L. Woodruff


Progressive Hedging (PH) is a scenario-based decomposition strategy for solving multi-stage stochastic programs. An attractive feature of PH is the ease with which it can be parallelized, by assigning sub-problems to each of many available processors; sub-problems may be linear programs, mixed-integer linear programs, or non-linear programs. The PH algorithm as stated parallelizes synchronously, in that all scenario sub-problems are solved before averages and sub-gradients are computed. However, for large-scale parallelization, such barrier synchronization leads to poor parallel efficiency, especially as sub-problem solve time variability increases. To mitigate this issue, we introduce the Asynchronous Progressive Hedging (APH) algorithm, where updates are done without waiting for all scenario sub-problem solves to complete. APH is critical on parallel computing architectures that are inherently heterogeneous and unreliable, or when so many compute nodes are employed that at least one of them is likely to fail during execution. We show that key convergence properties of PH hold in APH, and report computational experiences on mixed-integer linear and non-linear stochastic programs.


  In particular, Texas Payday Loans can cater to the needs of its residents. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.