Sample average approximation (SAA) is a technique to get good approximate solutions to stochastic programs (SP). When applying SAA, it is often useful to solve multiple SAA problems to obtain a confidence interval on the true optimal value of the SP and also get a better solution. We study techniques to accelerate the solution of this sequence of SAA problems, when solving them via Benders decomposition. We exploit similarities in the problem structure, as the problems just differ in the realizations of the random samples. Our extensive computational experiments of large scale problems provide empirical evidence of the improved efficiency of our algorithm. In addition, we also present theoretical results that provide insight into the algorithm's performance.

We consider multistage stochastic mixed-integer programs with general mixed-integer state variables in all time stages. We develop cutting-plane based algorithms that maintain convex polyhedral outer approximations for all expected cost to-go functions of the problem. We introduce so-called scaled-cuts to iteratively improve these convex polyhedral outer approximations and prove that the outer approximation in the first stage converges uniformly to the first-stage expected cost to-go function.

We consider improving the polyhedral representation of the extensive form of an SMIP. Given a facet-defining valid inequality for a single-scenario version of the SMIP, we provide conditions under which the same inequality remains facet-defining for the extensive form. Our main result gives necessary and sufficient conditions for a facet-defining inequality for a single-scenario version to be facet-defining for the extensive form. We then present several implications, which show that various recourse structures from the literature satisfy these conditions. For example, for an SMIP with simple recourse, any single-scenario facet is also a facet for the extensive form. For more general recourse structures, we provide additional mild necessary and sufficient conditions.

In stochastic programming, scenarios approximate distributions of unknown parameters, but in many applications the number of scenarios required to realistically model the uncertainty makes the optimisation problem numerically intractable. This motivates the scenario reduction problem: by finding a smaller
subset of scenarios, reduce the numerical complexity while keeping the error at an acceptable level.

Recently, problem-based scenario reduction methods based on opportunity cost dissimilarities have shown to be effective. In this setting,
opportunity cost means the cost of wrongly predicting scenario 1 when actually scenario 2 happens and can be viewed as a measure of how different these two
scenarios are with respect to the optimisation problem at hand.

In this talk, I will explain how test sets can be used to efficiently compute such opportunity cost matrices for stochastic integer programs. I will then describe new algorithms, based on ideas from algebraic geometry, to efficiently compute these test sets. Finally I will show promising numerical results.