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 when a businessman speaks of minority employment, or air pollution, or poverty, he speaks in the language of a certified public accountant analyzing a corporate balance sheet, who is to know that he understands the human problems behind the statistical ones? If the businessman would stop talking like a computer printout or a page from the corporate annual report, other people would stop thinking he had a cash register for a heart. It is as simple as that—but that isn’t simple.”
    —Louis B. Lundborg (1906–1981)