Sources to learn about Sample Average Approximation for practitioners

Question

I want to start learning Stochastic Programming, beginning with SAA (Sample Average Approximation) and keeping a practitioner's perspective in mind, i.e. I would like my sources to collectively cover intuition, background theory and the topics one should keep in mind when applying SAA. I know about Shapiro et al's book,¹ but I'm also interested in the application-focused topics, which apparently aren't part of the book's focus.

I have found a tutorial by Shapiro and Philpott.² I know I could just start reading many publications like ³ and ⁴, presentations like this one by Morton, or class notes from universities like this JHU 2019 class or Jeff Linderoth's 2003 course notes (I guess the content covered could be slightly outdated because of last 2 decades' newer advances in the field). The problem with the former approach is that I could get easily lost in the abundance of alternatives. Are there other sources you'd recommend optimization practitioners to read as an introduction to the topic? My priority is to know how to use and model real-world problems, keeping in mind mathematical rigor and computational issues/tractability regarding sampling procedures and approximations.

Any help in building a learning path will be highly appreciated, be it considering the former references, a different set or additional sources. Consider the reader to have Master's degree knowledge level of Applied Math and OR.

^{1 Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2014). Lectures on stochastic programming: modeling and theory. Society for Industrial and Applied Mathematics.}

^{2 Shapiro, A., & Philpott, A. (2007). A tutorial on stochastic programming. Manuscript. Available at www2. isye. gatech. edu/ashapiro/publications. html, 17.}

^{3 Verweij, B., Ahmed, S., Kleywegt, A. J., Nemhauser, G., & Shapiro, A. (2003). The sample average approximation method applied to stochastic routing problems: a computational study. Computational Optimization and Applications, 24(2-3), 289-333.}

^{4 Kim, S., Pasupathy, R., & Henderson, S. G. (2015). A guide to sample average approximation. In Handbook of simulation optimization (pp. 207-243). Springer, New York, NY.}

Answer 1

SAA is a very widely used technique for stochastic optimization problems and as far as I can see there are two frequently used approaches for the implementation of SAA. Please check Homem-de-Mello's survey paper.

I will give you some references on a very specific problem (Influence Maximization) where these approaches are applied. In Lee2015, Wu2017, Guney2018b a single batch of scenarios is used with a sample size as large as possible. This falls into Single Replication Procedure (SRP) category of SAA procedure as described in Homem-de-Mello's survey paper. In this case, most of the time the quality of approximations is rather not the major concern and no extra statistical information is provided (such as confidence intervals)

However, in Guney2019, Guney2019b, multiple batches with smaller sample sizes are used that yield smaller integer programs which consume less memory and CPU time. This method is named as Multiple Replication Procedure (MRP) in Homem-de-Mello. The advantage of MRP is, when the number of batches is sufficiently large ($\geq 20$), the Central Limit Theorem can be induced to provide $1-\alpha$ confidence intervals to make a statistical assessment on the quality of the approximations. As mentioned in Homem-de-Mello it is still possible to build confidence intervals with SRP, however it requires the satisfaction of additional conditions.

For some further reading I would recommend:

• Linderoth (2006) A very nice implementation of classical MRP
• Pasupathy (2019) Optimal sample size sequence determination
• Bertsimas (2017) Robust SAA

In terms of implementation, the SRP is very simple, usually you create your scenarios / do the sampling and just take the average. For MRP, there are different ways. One of them is having a fixed MRP size with all equal sample sizes. Another approach is: in each replication increasing the sample size (until you are happy with your approximation quality) and just consider your last replication's results.