In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, but follow known probability distributions. This framework contrasts with deterministic optimization, in which all problem parameters are assumed to be known exactly. The goal of stochastic programming is to find a decision which both optimizes some criteria chosen by the decision maker, and appropriately accounts for the uncertainty of the problem parameters. Because many real-world decisions involve uncertainty, stochastic programming has found applications in a broad range of areas ranging from finance to transportation to energy optimization.
Methods Several stochastic programming methods have been developed:
Scenario-based methods including sample average approximation Stochastic integer programming for problems in which some variables must be integers Chance constrained programming for dealing with constraints that must be satisfied with a given probability Stochastic dynamic programming Markov decision process Benders decomposition
Two-stage problem definition The basic idea of two-stage stochastic programming is that (optimal) decisions should be based on data available at the time the decisions are made and cannot depend on future observations. The two-stage formulation is widely used in stochastic programming. The general formulation of a two-stage stochastic programming problem is given by:
min x ∈ X { g ( x ) = f ( x ) + E ξ [ Q ( x , ξ ) ] } {\displaystyle \min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}
where Q ( x , ξ ) {\displaystyle Q(x,\xi )} is the optimal value of the second-stage problem
min y { q ( y , ξ ) | T ( ξ ) x + W ( ξ ) y = h ( ξ ) } . {\displaystyle \min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}.}
The classical two-stage linear stochastic programming problems can be formulated as
min x ∈ R n g ( x ) = c T x + E ξ [ Q ( x , ξ ) ] subject to A x = b x ≥ 0 {\displaystyle {\begin{array}{llr}\min \limits _{x\in \mathbb {R} ^{n}}&g(x)=c^{T}x+E_{\xi }[Q(x,\xi )]&\\{\text{subject to}}&Ax=b&\\&x\geq 0&\end{array}}}
where Q ( x , ξ ) {\displaystyle Q(x,\xi )} is the optimal value of the second-stage problem
min y ∈ R m q ( ξ ) T y subject to T ( ξ ) x + W ( ξ ) y = h ( ξ ) y ≥ 0 {\displaystyle {\begin{array}{llr}\min \limits _{y\in \mathbb {R} ^{m}}&q(\xi )^{T}y&\\{\text{subject to}}&T(\xi )x+W(\xi )y=h(\xi )&\\&y\geq 0&\end{array}}}
In such formulation:
x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} is the first-stage decision variable vector.
y ∈ R m {\displaystyle y\in \mathbb {R} ^{m}} is the second-stage decision variable vector.
… excerpt ends here. Continue reading the full article.
