Augmented Markov Chain Monte Carlo Simulation for Two-Stage Stochastic Programs with Recourse

In this paper, we develop a simulation-based approach for two-stage stochastic programs with recourse. We construct an augmented probability model with stochastic shocks and decision variables. Simulating from the augmented probability model solves for the expected recourse function and the optimal first-stage decision. Markov chain Monte Carlo methods, together with ergodic averaging, provide a framework to compute the optimal solution. We illustrate our methodology via the two-stage newsvendor problem with unimodal and bimodal continuous uncertainty. Finally, we present performance comparisons of our algorithm and the sample average approximation method.