Adapting Progressive Hedging for Solving Two-Stage Stochastic Programs Under a Peer-to-Peer Computing Network
- 26 March 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 11 (4) , 3611-3622
Abstract
Following recent technology advances and increasing applications in peer-to-peer network computing, we explore the potential of using decentralized optimization methods to solve notoriously hard stochastic programs. As the first attempt, we adapt the well-known progressive hedging (PH) method under a peer-to-peer computing network for solving two-stage stochastic programs efficiently. Similar to the existing parallel PH method, our decentralized variant assigns each node within the network to take charge of the computing tasks covering one or few scenarios, and thus it distributes the overall computational burden over the entire network. However, unlike the parallel PH method, the decentralized variant no longer needs a master node to realize central coordination, and thus it improves the scalability of the network computing as well. In this paper, we show the exact convergence of our decentralized method for solving two-stage stochastic programs with continuous variables subject to convex constraints. Further, we investigate several computational issues for the mixed-integer cases to improve the adaptation efficiency. Finally, the efficiency of our method is demonstrated through comparative computational experiments on a set of benchmark test instances.Keywords
Funding Information
- National Natural Science Foundation of China (62203218)
- Natural Science Foundation of Jiangsu Province of China (BK20220884)
- Purdue Research Foundation
This publication has 34 references indexed in Scilit:
- Pyomo — Optimization Modeling in Python2017
- Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programsMathematical Programming, 2016
- A hierarchy of bounds for stochastic mixed-integer programsMathematical Programming, 2012
- PySP: modeling and solving stochastic programs in PythonMathematical Programming Computation, 2012
- Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problemsComputational Management Science, 2010
- Solving Stochastic Transportation Network Protection Problems Using the Progressive Hedging-based MethodNetworks and Spatial Economics, 2008
- The Million-Variable “March” for Stochastic Combinatorial OptimizationJournal of Global Optimization, 2005
- Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programmingJournal of Heuristics, 1996
- Applying the progressive hedging algorithm to stochastic generalized networksAnnals of Operations Research, 1991
- Solving multistage stochastic networks: An application of scenario aggregationNetworks, 1991