[3][4] Several stochastic programming methods have been developed: 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.
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
could be inferred from historical data if one assumes that the distribution does not significantly change over the considered period of time.
To solve the two-stage stochastic problem numerically, one often needs to assume that the random vector
Then the expectation in the first-stage problem's objective function can be written as the summation:
has an infinite (or very large) number of possible realizations the standard approach is then to represent this distribution by scenarios.
For example, the number of scenarios constructed will affect both the tractability of the deterministic equivalent and the quality of the obtained solutions.
A stochastic LP is built from a collection of multi-period linear programs (LPs), each having the same structure but somewhat different data.
In order to incorporate uncertainties in the second stage, one should assign probabilities to different scenarios and solve the corresponding deterministic equivalent.
(Strictly speaking a deterministic equivalent is any mathematical program that can be used to compute the optimal first-stage decision, so these will exist for continuous probability distributions as well, when one can represent the second-stage cost in some closed form.)
For example, to form the deterministic equivalent to the above stochastic linear program, we assign a probability
Then we can minimize the expected value of the objective, subject to the constraints from all scenarios:
In practice it might be possible to construct scenarios by eliciting experts' opinions on the future.
The number of constructed scenarios should be relatively modest so that the obtained deterministic equivalent can be solved with reasonable computational effort.
In theory some measures of guarantee that an obtained solution solves the original problem with reasonable accuracy.
has a practical value since almost always a "true" realization of the random data will be different from the set of constructed (generated) scenarios.
Such exponential growth of the number of scenarios makes model development using expert opinion very difficult even for reasonable size
A common approach to reduce the scenario set to a manageable size is by using Monte Carlo simulation.
Then we can formulate a corresponding sample average approximation By the Law of Large Numbers we have that, under some regularity conditions
Nevertheless, consistency results for SAA estimators can still be derived under some additional assumptions: Suppose the sample
denotes the cdf of the standard normal distribution) and is the sample variance estimate of
[8][9] Empirical tests of models of optimal foraging, life-history transitions such as fledging in birds and egg laying in parasitoid wasps have shown the value of this modelling technique in explaining the evolution of behavioural decision making.
Stochastic dynamic programming is a useful tool in understanding decision making under uncertainty.
At that time the returns in the first period have been realized so it is reasonable to use this information in the rebalancing decision.
To complete the problem description one also needs to define the probability distribution of the random process
For example, one can construct a particular scenario tree defining time evolution of the process.
In order to write dynamic programming equations, consider the above multistage problem backward in time.
All discrete stochastic programming problems can be represented with any algebraic modeling language, manually implementing explicit or implicit non-anticipativity to make sure the resulting model respects the structure of the information made available at each stage.
An instance of an SP problem generated by a general modelling language tends to grow quite large (linearly in the number of scenarios), and its matrix loses the structure that is intrinsic to this class of problems, which could otherwise be exploited at solution time by specific decomposition algorithms.
Extensions to modelling languages specifically designed for SP are starting to appear, see: They both can generate SMPS instance level format, which conveys in a non-redundant form the structure of the problem to the solver.