Sampling based progressive hedging algorithms for stochastic programming problems

Many real-world optimization problems have parameter uncertainty. For instances where the uncertainties can be estimated to a certain degree, stochastic programming (SP) methodologies are used to identify robust plans. Despite advances in SP, it is still a challenge to solve real world stochastic programming problems, in part due to the exponentially increasing number of scenarios. For two-stage and multi-stage problems, the number of scenarios increases exponentially with the number of uncertain parameters, and for multi-stage problems also with the number of decision stages. In the case of large scale mixed integer stochastic problem instances, there are usually two common approaches: approximation methods and decomposition methods. Most common sampling-based approximation (SAA) SP technique is the Monte Carlo sampling-based method. The Progressive Hedging Algorithm (PHA) on the other hand can optimally solve large problems through the decomposition into smaller problem instances. The 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 and multi-stage SPs, however, the SAA method is not practical due to the significant computational effort required. In contrast, PHA suffers from the need to solve many sub-problems iteratively which is computationally expensive. In this dissertation, we develop novel SP algorithms integrating sampling based SAA and decomposition based PHA SP methods. The proposed integrated methods are novel in that they marry the complementary aspects of PHA and SAA in terms of exactness and computational efficiency. 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 or PHA) as well as other commonly used SP methods through extensive experimentation. In addition, we develop alternative hybridization strategies and present results of extensive experiments for these strategies under different uncertainty models. The validation of the methods is demonstrated through Capacitated Reliable facility Location Problem (CRFLP) and Multi-stage stochastic lot-sizing problems