Stochastic Programming - Two-Stage Problems

Two-Stage Problems

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 should not depend on future observations. Two-stage stochastic programming formulation is widely used formulation in stochastic programming. The general formulation of a two-stage stochastic programming problem is given by:

\min_{x\in X}\{ g(x)= f(x) + E\}

where is the optimal value of the second-stage problem

\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

\begin{array}{llr} \min\limits_{x\in \mathbb{R}^n} &g(x)= c^T x + E & \\ \text{subject to} & Ax = b &\\ & x \geq 0 & \end{array}

where is the optimal value of the second-stage problem

\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 is the first-stage decision variable vector, is the second-stage decision variable vector, and contains the data of the second-stage problem. In this formulation, at the first stage we have to make a "here-and-now" decision before the realization of the uncertain data, viewed as a random vector, is known. At the second stage, after a realization of becomes available, we optimize our behavior by solving an appropriate optimization problem.

At the first stage we optimize (minimize in the above formulation) the cost of the first-stage decision plus the expected cost of the (optimal) second-stage decision. We can view the second-stage problem simply as an optimization problem which describes our supposedly optimal behavior when the uncertain data is revealed, or we can consider its solution as a recourse action where the term compensates for a possible inconsistency of the system and is the cost of this recourse action.

The considered two-stage problem is linear because the objective functions and the constraints are linear. Conceptually this is not essential and one can consider more general two-stage stochastic programs. For example, if the first-stage problem is integer, one could add integrality constraints to the first-stage problem so that the feasible set is discrete. Non-linear objectives and constraints could also be incorporated if needed.

Read more about this topic:  Stochastic Programming

Famous quotes containing the word problems:

    “If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
    —Barbara Coloroso (20th century)