Optimization Online


Sampling-Based Progressive Hedging Algorithms in Two Stage Stochastic Programming

Nezir Aydin (nzraydin***at***yildiz.edu.tr)
Alper Murat (amurat***at***wayne.edu)
Boris S. Mordukhovich (boris***at***math.wayne.edu)

Abstract: Most real-world optimization problems are subject to uncertainties in parameters. In many situations where the uncertainties can be estimated to a certain degree, various stochastic programming (SP) methodologies are used to identify robust plans. Despite substantial advances in SP, it is still a challenge to solve practical SP problems, partially due to the exponentially increasing number of scenarios representing the underlying uncertainties. Two commonly used SP approaches to tackle this complexity are approximation methods, i.e., Sample Average Approximation (SAA), and decomposition methods, i.e., Progressive Hedging Algorithm (PHA). SAA, while effectively used in many applications, can lead to poor solution quality if the selected sample sizes are not sufficiently large. With larger sample sizes, however, SAA becomes computationally impractical. In contrast, PHA---as an exact method for convex problems and a very effective method in terms of finding very good solutions for nonconvex problems--suffers from the need to iteratively solve many scenario subproblems, which is computationally expensive. In this paper, we develop novel SP algorithms integrating SAA and PHA methods. The proposed methods are innovative in that they blend the complementary aspects of PHA and SAA in terms of exactness and computational efficiency, respectively. Further, the developed methods are practical in that they allow the analyst to calibrate the tradeoff between the exactness and speed of attaining a solution. We demonstrate the effectiveness of the developed integrated approaches, Sampling-Based Progressive Hedging Algorithm (SBPHA) and Discarding SBPHA (d-SBPHA), over the pure strategies (i.e., SAA). The validation of the methods is demonstrated through two-stage stochastic Capacitated Reliable Facility Location Problem (CRFLP).

Keywords: stochastic programming; facility location; hybrid algorithms; progressive hedging; sample average approximation.

Category 1: Stochastic Programming

Citation: Unpublished. Submitted to Journal. Yildiz Technical University/Istanbul and Wayne State University/Detroit. December 2015

Download: [PDF]

Entry Submitted: 12/04/2015
Entry Accepted: 12/04/2015
Entry Last Modified: 12/04/2015

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