14
$\begingroup$

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,1 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.2 I know I could just start reading many publications like 3 and 4, 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.

$\endgroup$
2
  • $\begingroup$ In addition to the papers suggested in other responses, I would also recommend reading the paper ``A sample approximation approach for optimization with probabilistic constraints", by Shabbir Ahmed and James Luedtke. The math in this paper is very accessible to a Masters level student IMO compared to other papers I have come across. Although the paper is not primarily focused on the practical applications, there are still plenty in the paper. $\endgroup$
    – batwing
    Mar 6, 2020 at 18:21
  • $\begingroup$ Thanks @batwing, I appreciate your comment. Will look for that paper. $\endgroup$
    – dhasson
    Mar 9, 2020 at 3:33

1 Answer 1

6
$\begingroup$

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:

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.

$\endgroup$
1
  • 1
    $\begingroup$ Hi, thanks for taking time to provide this answer. The statistical criteria and confidence intervals are among my topics of interest. I will mark it as accepted and review the references you mention. $\endgroup$
    – dhasson
    Mar 9, 2020 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.