Editing Stochastic programming (section)

=== Discretization ===
To solve the two-stage stochastic problem numerically, one often needs to assume that the random vector <math>\xi</math> has a finite number of possible realizations, called ''scenarios'', say <math>\xi_1,\dots,\xi_K</math>, with respective probability masses <math>p_1,\dots,p_K</math>. Then the expectation in the first-stage problem's objective function can be written as the summation:
<math display="block">
E[Q(x,\xi)]=\sum\limits_{k=1}^{K} p_kQ(x,\xi_k)
</math>
and, moreover, the two-stage problem can be formulated as one large linear programming problem (this is called the deterministic equivalent of the original problem, see section {{Section link||Deterministic equivalent of a stochastic problem}}).

When <math>\xi</math> has an infinite (or very large) number of possible realizations the standard approach is then to represent this distribution by scenarios. This approach raises three questions, namely:

# How to construct scenarios, see {{Section link||Scenario construction}};
# How to solve the deterministic equivalent. Optimizers such as [[CPLEX]], and [[GNU Linear Programming Kit|GLPK]] can solve large linear/nonlinear problems. The NEOS Server,<ref name="neos">{{Cite web|url=http://www.neos-server.org/neos/|title = NEOS Server for Optimization}}</ref> hosted at the [[University of Wisconsin, Madison]], allows free access to many modern solvers. The structure of a deterministic equivalent is particularly amenable to apply decomposition methods,<ref>{{cite book|first2=Alexander|last2=Shapiro|last1=Ruszczyński|first1=Andrzej|title=Stochastic Programming|publisher=[[Elsevier]]|year=2003|isbn=978-0444508546|series=Handbooks in Operations Research and Management Science|volume=10|location=Philadelphia|pages=700|author1-link=Andrzej Piotr Ruszczyński}}</ref> such as [[Benders' decomposition]] or scenario decomposition;
# How to measure quality of the obtained solution with respect to the "true" optimum.

These questions are not independent. For example, the number of scenarios constructed will affect both the tractability of the deterministic equivalent and the quality of the obtained solutions.