Stochastic programming

Continuing the first lecture, we will introduce advanced features that
improve the performance of algorithms for solving the Benders-based
decomposition. Aggregating scenarios and regularization approaches
will be a primary focus. We will also introduce a different dual
decomposition technique that can be effective for solving two-stage
stochastic programs, and discuss algorithmic approaches for solving
the dual decomposition.

Multistage stochastic programming (MSP) is a framework for sequential decision making under uncertainty where the decision space is typically high dimensional and involves complicated constraints, and the uncertainty is modeled by a general stochastic process. In the traditional risk neutral setting, the goal is to find a sequence of decisions or a policy so as to optimize an expected value objective. MSP has found applications in a variety of important sectors including energy, finance, manufacturing, services, and natural resources.

This lecture gives an introduction to modeling optimization
problems where parameters of the problem are uncertain. The primary
focus will be on the case when the uncertain parameters are modeled as
random variables. We will introduce both two-stage, recourse-based
stochastic programming and chance-constrained approaches. Statistics
that measure the value of computing a solution to the stochastic
problem will be introduced. We will show how to create
an equivalent extensive form formulations of the instances, so that

We present the Benders decomposition algorithm for solving two-stage stochastic optimization models. The main feature of this algorithm is that it alternates between solving a relatively compact master problem, and a set of subproblems, one per scenario, which can be solved independently (hence decomposing the large problem into many small problems). After presenting and demonstrating correctness of the basic algorithm, several computational enhancements will be discussed, including effective selection of cuts, multi-cut vs.

This lecture introduces the concept of risk measures and their use in stochastic optimization models to enable decision makers to seek decisions that are less likely to yield a highly undesirable outcome. In particular, we focus on coherent and convex risk measures, and demonstrate the duality relationship between such risk measures and distributionally robust stochastic optimization models. The specific examples of average value-at-risk (also known as conditional value-at-risk) and mean semideviation risk measures will be presented.

First, three approaches to scenario generation besides
Monte Carlo methods are considered: (i) Optimal quantization
of probability distributions, (ii) Quasi-Monte Carlo
methods and (iii) Quadrature rules based on sparse
grids. The available theory is discussed and related
to applying them in stochastic programming. Second,
the problem of optimal scenario reduction and the
generation of scenario trees for multistage models
are addressed.

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty,
various impediments have historically prevented its widespread use. One key factor involves the
ability of non-experts to easily express stochastic programming problems, ideally building on a likely
existing deterministic model expressed through an algebraic modeling language. A second key factor
relates to the difficulty of solving stochastic programming models, particularly the general mixed-integer,