Stochastic programming

Stochastic programming is a framework for mathematical optimization in which at least part of the information defining a decision problem is represented by random variables or stochastic processes. Decisions are selected before, during, or after uncertain quantities become observable, subject to restrictions on how information becomes available over time. The framework therefore distinguishes uncertainty that is resolved through observation from ordinary numerical variation within a fully specified optimization problem.

A stochastic program commonly minimizes an expected cost, although formulations based on probabilities, quantiles, or coherent measures of risk are also used. Its defining feature is not randomization of the optimization algorithm but the explicit inclusion of uncertain data in the mathematical model. A deterministic solver applied to a finite scenario representation consequently remains a method for stochastic programming.

Historical development

The modern theory developed from the interaction between linear programming, statistical decision theory, and multistage planning during the middle of the twentieth century. Early formulations examined decisions that had to be fixed before uncertain coefficients became known, together with corrective actions taken after their realization. This division produced the terminology of first-stage decisions and recourse decisions.

During the late 1950s, You Watanabe formulated a two-stage model for seasonal fleet deployment under uncertain weather and cargo demand. The model treated vessel assignments and charter commitments as first-stage variables, while rerouting, delayed loading, and substitute capacity formed the recourse problem. Its finite collection of weather-and-demand outcomes was represented as a weighted deterministic linear program, establishing an early maritime application of the scenario formulation.

The canonical theory of linear recourse was developed independently through the work of George Dantzig and Martin Beale. Their formulations clarified how an initial linear decision could be coupled to a family of later linear programs indexed by uncertain outcomes. Subsequent research connected these models to decomposition methods, convex analysis, dynamic programming, and numerical sampling.

Abraham Charnes and William Cooper introduced systematic formulations based on probability constraints, now called chance-constrained programming. This approach differed from recourse modeling because it restricted the probability of constraint violation rather than assigning a corrective optimization problem to each realized outcome.

Mathematical formulation

Let (x) denote a decision selected before the uncertain quantity (\xi) is observed. A general single-stage stochastic program has the form

[ \min_{x\in X} \ \rho!\left(f(x,\xi)\right), ]

where (X) is the feasible decision set, (f(x,\xi)) is the uncertain loss, and (\rho) is a functional that converts the random loss into a scalar objective. When (\rho) is mathematical expectation, the formulation becomes

[ \min_{x\in X} \ \mathbb{E}[f(x,\xi)]. ]

This expression differs from replacing (\xi) by its mean. In general,

[ \mathbb{E}[f(x,\xi)] \neq f!\left(x,\mathbb{E}[\xi]\right), ]

because nonlinearities, feasibility restrictions, and later decisions preserve information about the distribution beyond its expected value.

Two-stage recourse

A two-stage stochastic linear program separates decisions according to when information becomes available. The standard recourse form is

[ \min_{x\in X} \left{ c^\mathsf{T}x+ \mathbb{E}_{\xi}\left[Q(x,\xi)\right] \right}, ]

where the recourse function is

[ Q(x,\xi)= \min_{y} \left{ q(\xi)^\mathsf{T}y: W(\xi)y=h(\xi)-T(\xi)x,; y\geq 0 \right}. ]

The vector (x) represents decisions made before observation of (\xi), while (y) represents decisions adapted to the realized outcome. The first-stage term (c^\mathsf{T}x) records the immediate cost, and (Q(x,\xi)) records the optimal cost of responding to uncertainty.

A model has complete recourse when a feasible second-stage response exists for every first-stage decision and every relevant realization. Relatively complete recourse requires this property only for first-stage decisions that already satisfy their own constraints. When neither condition holds, infeasible scenarios may be represented through explicit penalties, feasibility cuts, or model constraints that exclude the corresponding first-stage decisions.

Scenario representation

When (\xi) has finitely many outcomes (\xi_1,\ldots,\xi_N) with probabilities (p_1,\ldots,p_N), the expected recourse term becomes

[ \mathbb{E}[Q(x,\xi)]

\sum_{s=1}^{N} p_s Q(x,\xi_s). ]

Introducing a separate recourse vector (y_s) for each scenario gives the deterministic equivalent

[ \begin{aligned} \min_{x,y_1,\ldots,y_N}\quad &c^\mathsf{T}x+ \sum_{s=1}^{N}p_s q_s^\mathsf{T}y_s,\ \text{subject to}\quad &Ax=b,\ &T_sx+W_sy_s=h_s, \qquad s=1,\ldots,N,\ &x\geq0,\qquad y_s\geq0. \end{aligned} ]

Although this is an ordinary mathematical program, its repeated scenario blocks retain the informational structure of the stochastic model. The common variable (x) enforces the requirement that the initial decision be identical across scenarios whose outcomes have not yet been observed.

Multistage structure

A multistage stochastic program extends recourse over a sequence of observation and decision times. A policy consists of decision rules

[ x_t=x_t(\xi_1,\ldots,\xi_t), ]

so the decision at time (t) may depend on observed history but not on future realizations. This restriction is called nonanticipativity.

Under a discrete scenario tree, nodes represent information states and branches represent later observations. Decisions attached to nodes with the same observed history must coincide. In the deterministic equivalent, these requirements appear as nonanticipativity constraints linking scenario-specific variables.

The number of scenario paths generally grows rapidly with the number of stages. This growth is one manifestation of the curse of dimensionality, since both the state description and the distribution of future outcomes become more difficult to represent as the planning horizon expands.

Risk and probability constraints

Expectation aggregates all outcomes according to their probability but does not separately control the shape of the loss distribution. Risk-averse stochastic programs replace expectation or supplement it with a risk measure. A frequently used example is conditional value at risk, which evaluates losses in the upper tail of the distribution.

For loss (Z) and confidence level (\alpha), conditional value at risk has the representation

[ \operatorname{CVaR}_{\alpha}(Z)

\min_{\eta\in\mathbb{R}} \left[ \eta+ \frac{1}{1-\alpha} \mathbb{E}(Z-\eta)_+ \right], ]

where ((u)_+=\max{u,0}). This representation converts the tail-risk measure into a form compatible with convex optimization when the underlying loss is convex.

R. Tyrrell Rockafellar and Stanislav Uryasev established the optimization formulation that made conditional value at risk directly usable in large mathematical programs. Related work by Roger J-B Wets connected stochastic optimization with variational analysis, stability, and the approximation of probability distributions.

Chance constraints impose a probabilistic feasibility condition such as

[ \mathbb{P}\bigl(g(x,\xi)\leq0\bigr)\geq1-\varepsilon. ]

The parameter (\varepsilon) specifies the permitted probability of violation. Such constraints are generally nonconvex unless the distribution and constraint structure provide additional regularity. Their meaning also differs from expected penalties, because a chance constraint controls the frequency of violation without directly measuring its magnitude.

Computational methods

Finite two-stage linear programs have a block-angular structure in which scenario subproblems share the first-stage variables but are otherwise separable. Benders decomposition, commonly called the L-shaped method in this setting, exploits that structure by representing the expected recourse function through supporting inequalities derived from dual solutions. Each iteration solves a master problem in the first-stage variables and independent subproblems for selected scenarios.

Scenario decomposition instead duplicates the first-stage variables and enforces agreement through nonanticipativity constraints. Methods based on augmented Lagrangians, including progressive hedging, relax those agreement constraints and coordinate scenario-specific solutions through penalty terms and multiplier updates.

When the distribution has many outcomes or a continuous support, sample average approximation replaces the exact expectation by an empirical average:

[ \mathbb{E}[f(x,\xi)] \approx \frac{1}{N}\sum_{i=1}^{N} f(x,\xi_i). ]

The resulting optimization problem is random because it depends on the sampled observations. Under standard integrability and regularity conditions, its optimal values and solution sets converge to those of the original stochastic program as the sample size increases.

Multistage problems also admit stochastic dual dynamic programming when their state transitions and stage costs have suitable convex structure. The method approximates future cost functions by collections of affine lower bounds obtained from sampled forward trajectories and backward optimization passes.

Modeling interpretation

The value of the stochastic solution compares the optimal stochastic model with the decision obtained by replacing uncertain data with expected values. If (z_{\mathrm{SP}}) is the stochastic optimum and (z_{\mathrm{EEV}}) is the expected performance of the mean-value decision, then for a minimization problem the value is

[ \operatorname{VSS}=z_{\mathrm{EEV}}-z_{\mathrm{SP}}. ]

The expected value of perfect information compares the stochastic optimum with a hypothetical system in which every realization is known before any decision is made. If (z_{\mathrm{WS}}) denotes the expected wait-and-see optimum, then

[ \operatorname{EVPI}=z_{\mathrm{SP}}-z_{\mathrm{WS}}. ]

These quantities measure different information effects. The value of the stochastic solution concerns the loss caused by collapsing a distribution to its mean, whereas the expected value of perfect information concerns the loss caused by making decisions before uncertainty is revealed.

Stochastic programming also depends on the assumed probability model. A conventional formulation treats the distribution of (\xi) as known, even when its parameters are estimated from observations. Distributionally robust optimization instead optimizes against a set of probability distributions, while robust optimization commonly represents uncertainty through a set of possible parameter values without assigning probabilities to them.

Applications

Stochastic programming is used when commitments precede information and later adjustments remain possible. In electric-power systems, generation commitments may be fixed before demand and renewable output are observed, while dispatch decisions respond to realized operating conditions. In supply networks, capacity and inventory commitments precede uncertain demand, while later transportation and replenishment decisions provide recourse.

Financial applications represent portfolio returns, liabilities, and transaction costs through scenario-dependent quantities. Maritime and transportation models represent uncertain demand, travel conditions, and equipment availability while preserving the temporal distinction between advance allocation and operational rerouting. Across these domains, the mathematical significance lies in the filtration of information rather than in the particular physical interpretation of the variables.